BANGALORE, INDIA: In the last issue we discussed BTree and emphasised on the fact that CouchDB is nothing but a set of BTrees with a well defined interface to access remotely. In this issue, we dis cuss a few more concepts that are essential in understanding CouchDB.

Note that as I wrote in my previous article, these concepts are used in several cloud storage platforms and are one of the best known distributed computing algorithms to solve problems of different kinds. The first thing we explore is an extension of BTree, known as B+Tree. It is actually aB+Tree, not a BTree that is used in CouchDB.

The B+Tree

B+Tree is a variant of the general purpose BTree, where the data structure is modified to handle a few interesting use cases. Two important modifications are that in a B+Tree the intermediate and the root nodes hold only the key; they don't have any reference to values and all key value pairs are located in the leaf.

The root and the intermediate node acts as location finders for the search key and all values correspon ding to them are found in the keys. Second, the leaf nodes with M distinct elements are interconnected. That is there is a link list of leaf nodes and so if you are at a given leaf, you can traverse all through the rightmost node in the BTree.

These two simple modifications provide a lot of flexibilities when we look for nodes for a specific key or keys in between a specific range. The latter is explicitly known as Range Query in database systems. The leaf nodes are inter connected to each other and values are placed in the leaf node. In the root node certain elements are just pointers and their key value pairs are repeated at the leaf.

In previous examples, we searched for a single key and if it was found we either retrieved it or reported a miss. Let us to day, modify this search key criterion. Instead of a single key, let us say that we want to retrieve all values which are between 3and 5. Such queries are common in SQL where instead of a single predicate you include multiple predicate values.

In a B+Tree, such a search is trivial to solve. Here, you locate the element which is close to 3. The element with key is in the first leaf node. This leaf node is connected to the next leaf node and hence we don't need to do yet another search but instead move on linearly in the link list till we reach 5.

Click here to read more!

Click here to read more!