c program for b plus tree implementation

Suppose a B-tree has n elements and M is the maximum number of children a node can have. If the number of keys in the root is too high, then we make the middle key to be the new root of the whole tree and connect it to the node it was in before. Afterwards we look for and fix these problems: If the number of keys is too high(greater than t - 1) then we move the middle key to the nodes parent. Insertįirst we search and find out to which node the key should belong to and we insert it into it. In the end, recursively print the rightmost child.

We start from the leftmost child, recursively print the leftmost child, then repeat the same process for remaining children and keys. Traversal is also similar to Inorder traversal of Binary Tree. If we reach a leaf node and don’t find k in the leaf node, we return NULL. Otherwise we recur down to the appropriate child (The child which is just before the first greater key) of the node. For every visited non-leaf node, if the node has key, we simply return the node. We start from root and recursively traverse down. Search is similar to search in Binary Search Tree.

Like other balanced Binary Search Trees, time complexity to search, insert and delete is O(Log(n)).

Binary Search Trees grow downward and also shrink from downward.

B-Tree grows and shrinks from root which is unlike Binary Search Tree.

The child between two keys k1 and k2 contains all keys in range from k1 and k2.

All keys of a node are sorted in increasing order.

Number of children of a node is equal to the number of keys in it plus 1.

All nodes (including root) may contain at most 2t – 1 keys.Every node except root must contain at least t-1 keys.The value of t depends upon disk block size. A B-Tree is defined by the term minimum degree ‘t’.Since h is low for B-Tree, total disk accesses for most of the operations are reduced significantly compared to balanced Binary Search Trees like AVL Tree, Red Black Tree, etc. Generally, a B-Tree node size is kept equal to the disk block size. Height of B-Trees is kept low by putting maximum possible keys in a B-Tree node. Most of the tree operations (search, insert, delete, max, min, etc) require O(h) disk accesses where h is height of the tree.

The main idea of using B-Trees is to reduce the number of disk accesses. Disk access time is very high compared to main memory access time. When the number of keys is high, the data is read from disk in the form of blocks. To understand use of B-Trees, we must think of huge amount of data that cannot fit in main memory. In most of the other self-balancing search trees (like AVL and Red Black Trees), it is assumed that everything is in main memory.

C program for b plus tree implementation