A tree is a data structure that organizes key/value pairs into branches based on some ordering criteria. Each node then branches further down into lower nodes, and the entire structure resembles a tree, hence the name. There are many different kinds of trees, such as AVL, B, B++, Red-Black trees, etc. They generally differ in the way the tree is maintained, and the way data in it is connected, but most of those widely used today generally provide O(log(N)) access. That means in a tree holding N nodes, you need to access about log(N) of them to find any given key. So, for example, if you have 1,000,000 keys/value pairs, it will take about 20 key comparisons to find any of them (since 2^20 is approximately 1M). As an example of a tree structure, consider this: In this tree, keys "3", "4", "5", "6", "7", "8" and "9" are stored. An arrow to the left points to a lesser key, while an arrow to the right points to a greater one. You can see how it takes at most three key comparisons to find any of the keys since the tree is 3-level deep. Also, this is a binary tree, as each node has two children nodes branching from it (left and right). A tree can have multiple keys per node (typically B-variations), and those are generally well suited for storing data on disk, where access to any data is done in large blocks; such trees work well in memory as well. However, binary trees are also well suited for in-memory access, if not even more so. Vely uses a modified AVL binary tree that also provides some benefits of various "B" trees, specifically fast-range searches; additionally, such benefits are optional, so you have more options in order to make a tree structure fit your exact needs. A tree above is a balanced one, which means that the heights of each node's children do not differ by more than one (in this case, they are exactly the same). A balanced tree, just like its name suggests, looks "balanced" when shown in its graphical form like it is here. In order to achieve this kind of balance, a tree needs to be maintained with each insert and delete. For instance, if you were to insert keys above in increasing order, your tree may initially look like this, simply because each insertion goes to the right because each next key is greater: This binary tree effectively degenerates into a sorted list, as each node is followed by another to the right due to each being greater than the previous. Searching a tree like this is O(N), meaning you may have to traverse all nodes in the worst cases to reach a key/value pair. To balance a tree, connections between the nodes are re-arranged. This is a relatively fast operation since it doesn't involve copying keys nor values; instead, only the direction where a left or right connection goes from a node is changed. For instance: In this case, the tree was rotated to the left around the element with the key of "6". Now, if you right-rotate the left branch around key "4", and if you left-rotate the right branch around key "8", you will get the original balanced tree. In practicality, these rotations happen when each element is inserted or deleted and not after you already have a number of key/value pairs in the tree. The above is just to illustrate what could happen if rotations like the above weren't applied and the effect they have in order to balance the tree. Note that trees can be balanced in different ways; in this case, what you're balancing is the height of the tree from any given node. is a binary tree where the difference between a sub-tree on the right and on the left is at most 1. Vely's tree adds (optionally) a linked list that connects all nodes in order from minimum to maximum key; this capability is important because it allows very fast range searches, which means starting from a given key and moving to the next lower or greater key until some condition is met. Without this, each next range key would take O(log(N)) access time; with this feature, it's O(1), i.e., the fastest possible access with just a single hop. That's why a Vely tree is a "hybrid" AVL/B tree because its features are found in both varieties; it also makes it high-performance and well-suited for in-memory databases or cache. AVL tree AVL/B tree cache server application In this example, you will create a cache server that uses fast tree-based data access in order to insert, update, and search key/value pairs. Create a new "tree" application first in a new directory (you can name it anything you like): mkdir -p tree
cd tree The command is a Vely program manager, and it will create a new application (see ) named "tree": vf how-vely-works sudo vf -i -u $(whoami) tree To get Vim highlighting of Vely syntax: vv -m Create a source code file "treesrv.vely": vi treesrv.vely And copy and paste this to it: %% /treesrv
    out-header default

    do-once
    new-tree define t process-scope
    end-do-once

    // Get input parameters
    task-param op
    input-param key
    input-param data

    if-task "add" // Add data to tree
        // Make a copy of key,data so they are Vely-allocated
        copy-string key to define c_key
        copy-string data to define c_data
        write-tree t key c_key value c_data status define st
        if (st == VV_ERR_EXIST) {
            delete-mem c_key
            delete-mem c_data
        }
        @Added [<<p-out key>>]
    else-task "delete" // Delete data and obtain the value deleted
        delete-tree t key (key) value define val old-key define okey status define st
        if (st == VV_ERR_EXIST) {
            @Not found [<<p-out key>>]
        } else {
            // If found, then delete key and value
            @Deleted [<<p-out val>>]
            delete-mem val
            delete-mem okey
        }
    else-task "query" // Query tree based on key value
        read-tree t key (key) value define val status define st
        if (st == VV_ERR_EXIST) {
            @Not found, queried [<<p-out key>>]
        } else {
            @Value [<<p-out val>>]
        }
    end-task
%% Note that the source file name ("treesrv.vely") should match the request name, which is "treesrv". If you're using hyphens (which are useful for web applications), just substitute them with an underscore. The fact that a request is implemented in a file with the same name helps keep your applications neat, tidy, and easy to peruse. In the statement, a is created with a process scope; that means all the data in this tree will be kept for as long as the process lives. Normally, all memory used by a request in Vely is released at the end of the request. The memory for a new tree here will remain throughout all requests this process will serve. The reason for the do-once statement is because you only need to create the tree once for the life of the process. do-once new-tree There are 3 input parameters: "op,” "key," and "data.” Note that "op" is declared as a (which is a special kind of ) because it determines what task (i.e., "op"eration) is being done. The other two, "key" and "data," are used as input parameter values for these tasks. task-param input-param If the task is "add," a new key/data pair is added to the tree using statement. Note that copies of "key" and "data" input parameters are created because write-tree expects (and the memory from isn't). write-tree allocated memory input-param If the task is "delete," a tree node with "key" is deleted. If the task is "query," a value from the node with "key" is returned. This code is a tree-based cache-server that maintains key/value pairs in memory and allows adding, deleting, and querying. Make an executable program Now, make a native executable: vv -q Run as application server "Application server" means a daemon, a resident server process that remains in memory and can serve many requests very fast. Here's how you do that: vf -w 1 tree The above will start an application server process to serve incoming requests. Using server from the command line Testing your server from the command line is easy: vv -r --req="/treesrv/op/add/key/1/data/one" --exec --server --silent-header --app="/tree" Note the "--server" option. It says to contact a server and execute the same request as before. A process you started is staying resident in memory and serving the incoming requests. This way, your server can serve a large number of concurrent requests because it handles each operation very fast. Again, you can see what's going on behind the scenes by omitting "--exec": vv -r --req="/treesrv/op/add/key/1/data/one" --server --silent-header --app="/tree" The result was: export CONTENT_TYPE=
export CONTENT_LENGTH=
export VV_SILENT_HEADER=yes
export REQUEST_METHOD=GET
export SCRIPT_NAME="/tree"
export PATH_INFO="/treesrv/op/add/key/1/data/one"
export QUERY_STRING=""
cgi-fcgi -connect /var/lib/vv/tree/sock/sock  /treesrv Here, a "cgi-fcgi" client program will contact the server you started, get a response, and print it out. You can make your own client application by using ; this way, you can do whatever you want with the response, and you can do so in a multi-threaded application since Vely's FastCGI API is MT-safe. FastCGI-API Test with 100 keys This is a bash test script to insert 100 keys into your cache server, query them to make sure they are there, delete them, and then query again to verify they're all gone. Create "test_tree" file: vi test_tree And copy/paste the following: #Restart tree server for this test
vf -m restart tree

#Add 100 key/data pairs. Key value is 0,1,2... and data values are "data_0", "data_1", "data_2" etc.
for i in {1..100}; do
   if [ "$(curl -s "http://localhost/tree/treesrv/op/add/key/$i/data/data_$i")" != "Added [$i]" ]; then
       echo "Error adding key [$i]"
       exit -1
   fi
done

echo "Keys added"

#Query all 100 keys and check that values retrieved are the correct ones.
for i in {1..100}; do
   if [ "$(curl -s "http://localhost/tree/treesrv/op/query/key/$i")" != "Value [data_$i]" ]; then
       echo "Error querying key [$i]"
       exit -1
   fi
done

echo "Keys queried"

#Delete all 100 keys
ERR="0"
for i in {1..100}; do
   if [ "$(curl -s "http://localhost/tree/treesrv/op/delete/key/$i")" != "Deleted [data_$i]" ]; then
       echo "Error deleting key [$i]"
       exit -1
   fi
done

echo "Keys deleted"

#Query all 100 keys and check that values retrieved are the correct ones.
for i in {1..100}; do
   if [ "$(curl -s "http://localhost/tree/treesrv/op/query/key/$i")" != "Not found, queried [$i]" ]; then
       echo "Error querying key [$i] after deletion."
       exit -1
   fi
done

echo "Keys queried"

echo "Tree server test successful" Make sure it's executable: chmod +x test_tree And now run it: ./test_tree The result is this: Keys added
Keys queried
Keys deleted
Keys queried
Tree server test successful Run as a web application Of course, your application server will probably serve web requests. Check out on how to connect the Apache web server to your application server or the same for Nginx: . is supported widely among web servers, so you can use pretty much any web server of your choice. connect-apache-unix-socket connect-nginx-unix-socket FastCGI Here's a brief intro for Apache: Setup web server This shows how to connect your application listening on a Unix socket (started with ) to the Apache web server. vf :
To setup Apache as a reverse proxy and connect your application to it, you need to enable FastCGI proxy support, which generally means "proxy" and "proxy_fcgi" modules - this is done : Step 1 only once For Debian (like Ubuntu) and OpenSUSE systems, you need to enable proxy and proxy_fcgi modules: sudo a2enmod proxy
sudo a2enmod proxy_fcgi For Fedora systems (or others like Archlinux) enable proxy and proxy_fcgi modules by adding (or uncommenting) LoadModule directives in the Apache configuration file - the default location of this file on Linux depends on the distribution. For Fedora (such as RedHat), Archlinux: sudo vi /etc/httpd/conf/httpd.conf For OpenSUSE: sudo vi /etc/apache2/httpd.conf Add this to the end of the file: LoadModule proxy_module modules/mod_proxy.so
LoadModule proxy_fcgi_module modules/mod_proxy_fcgi.so :
Edit the Apache configuration file: Step 2 For Debian (such as Ubuntu): sudo vi /etc/apache2/apache2.conf for Fedora (such as RedHat), Archlinux: sudo vi /etc/httpd/conf/httpd.conf and for OpenSUSE: sudo vi /etc/apache2/httpd.conf Add this to the end of file ("/tree" is the application path (see ) and "tree" is your application name): request-URL ProxyPass "/tree" unix:///var/lib/vv/tree/sock/sock|fcgi://localhost/tree :
Finally, restart Apache. On Debian systems (like Ubuntu) or OpenSUSE: Step 3 sudo systemctl restart apache2 On Fedora systems (like RedHat) and Arch Linux: sudo systemctl restart httpd Note: you must not have any other URL resource that starts with "/tree" (such as for example "/tree.html" or "/tree_something" etc.) as the web server will attempt to pass them as a reverse proxy request, and they will likely not work. If you need to, you can change the application path to be different from "/tree", see . request-URL Access the application server from the browser Use the following URL(s) to access your application server from a client-like browser (see ). Use actual IP or web address instead of 127.0.0.1 if different. request-URL # Call your application server to add a key 
http://127.0.0.1/tree/treesrv/op/add/key/1/data/one

# Call your application server to query a key 
http://127.0.0.1/tree/treesrv/op/query/key/1

# Call your application server to delete a key 
http://127.0.0.1/tree/treesrv/op/delete/key/1 Note: if your server is on the Internet and it has a firewall, you may need to allow HTTP traffic - see , , etc. ufw firewall-cmd The result is: Also published . here

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

Tree Data Structures For Faster Data Access: Balancing, Benefits, and Implementation in Vely

Too Long; Didn't Read

@vely

Credibility

RELATED STORIES