Mugdha

Sep 15, 2022

BTree

What is a BTree?

BTrees are tree structures that are self-balancing. Designed for storing large amounts of data, they are meant for fast querying and retrieval. BTrees are similar to binary search trees. Both BTree and Binary Search Trees are a type of n-way search tree but still, Binary Search Tree is considered a particular type of BTree. In a node, BTrees can have many key/value pairs sorted in ascending order on the basis of keys. This key/value pair is called a payload. The value in the payload is also known as 'data' or 'satellite data'. When it comes to databases, a key could be the primary key or index column in the row and the value could be the actual row record or a reference to it. Apart from the payload, the references to the children also are kept by the nodes. Each node usually requires a disk page and because of this, the child references usually refer to the page ID where the child node is stored in secondary storage. Similar to all other search trees, BTrees are organized. Therefore, the keys in a sub-tree must be larger than the keys in its left sub-tree.

Properties:

A tree is called a BTree if:

i) In a BTree of order n, the nodes have a maximum of n children.

ii) If the root is not a leaf, it has at least two child nodes.

iii) A node, if a non-leaf node with k child nodes, has k-1 keys.

iv) All leaves appear on the same level.

Building a BTree:

Let's see how to add items into the tree and also keep it balanced as we add those.

Step 1: The first item we add will take the place of the root of the tree because we are starting from an empty tree. Now the root has the key/value pair. Here, key=1 but the value is depicted by a star to indicate that it is the reference to a record. This root node also includes pointers to its left and right children represented by rectangles which are there to the left and right of the key. This node has no children, so we can leave those pointers empty for now.

Step 2: The order of this tree is 3. Thus there can only be up to 2 keys in it. The payload with key 2 can be added to the root node in ascending order.

Step 3: Now, to insert 3, but to keep keep the tree balanced and to satisfy all the conditions of a BTree, a split operation is required to be performed. To determine how to split the node, we pick the middle key. Here, in this case, we need to consider keys already present in the node along with the key to be newly inserted.

Step 4: Here, 2 is the middle key that can be chosen to split the node which means that values to the left of this key will be inserted into the left sub-tree, and, values to the right in the right sub-tree and 2 will become the new root node. This splitting operation is performed every time the number of keys in a node is about to exceed its capacity, to keep the tree self-balancing.

Step 4: Now, insert 4. We know that in a BTree values lesser than the root belong to the left sub-tree, while those greater than the root belong to the right sub-tree. So, we can simply add 4 alongside 3 in ascending order.

Step 5: Now, the right sub-tree is full. Time to perform the splitting operation again to insert 5. So that key 3 is moved to the left sub-tree and 5 is moved to the right sub-tree leaving 4 to be moved to the root node alongside key 2, we need to split the node.

Step 6: Because of this, space gets created in the right sub-tree to insert 6.

Step 7: Now, we need to insert 7. But the rightmost sub-tree has reached its full capacity which means another split operation is required. But now, the root node has also reached its full capacity, so, it also needs a split operation. This is done in two steps. First, let's split keys 5 and 6 so that 5 is on the left, to be inserted key 7 is on the right and so that key 6 is promoted. Now to promote key 6 the root note requires to be split such that key 4 becomes the new root and keys 2 and 6 are the parent nodes of the left and right sub-trees.

Steps 8, 9 & 10: We continue adding keys 8, 9, and 10 until we get the final tree.

Searching in a BTree(Java Code):

BTrees provide logarithmic time complexity O(log(n)) for insertion, deletion, and look-ups(search) operations making them so advantageous and helpful.

class BTree {

public BNode root;

public int min_degree;

BTree(int min_degree){

this.root=null;

this.min_degree=min_degree;

}

}

class BNode {

int [] keys;

int min_degree;

int current_no_of_keys;

BNode [] child_pointers;

boolean leaf;

BNode(int min_degree, boolean leaf){

this.min_degree=min_degree;

this.leaf=leaf;

this.current_no_of_keys=new int[2 * min_degree -1];

this.child_pointers=new BNode[2*min_degree];

this.n=0;

}

public void traversal() {

int j=0

for(j=0;j<this.n;j++){

if(this.leaf == false){

child_pointers[j].traversal();

}

System.out.print(keys[j] + " ");

}

if (leaf == false)

child_pointers[j].traversal();

}

BNode search(int k){

int j=0;

while(j<n && k>keys[j])

j++;

if(keys[j]==k)

return this;

if(leaf==true)

return null;

this.child_pointers[j].search(k);

}

}