Introduction to B-Tree

Inserting an element

At the leaf node level, insertions are made. The following algorithm must be followed to place an item into B Tree.

1. Navigate the B Tree until you find the suitable leaf node to insert the node.
2. If there are fewer than m-1 keys in the leaf node, insert the element in ascending order.
3. Else, it should proceed to the next step if the leaf node contains m-1 keys.
   1. In the rising sequence of elements, add the new element.
   2. In the middle, divide the node into two nodes.
   3. The median element should be pushed up to its parent node.
   4. If the parent node has the same m-1 number of keys as the child node, split it.

Example:

                                               source: staff.ustc.edu.cn

Recommended Topic - Specialization and Generalization in DBMS and  Checkpoint in DBMS.

Deleting an element

At the leaf nodes, deletion is also conducted. It can be a leaf node or an inside node that must be destroyed. To delete a node from a B tree, use the following algorithm.

1. Find the position of the leaf node.
2. If the leaf node has more than m/2 keys, delete the required key from the node.
3. If the leaf node lacks m/2 keys, fill in the gaps with the eighth or left sibling element.
   1. If the left sibling has more than m/2 elements, shift the intervening element down to the node where the key is deleted and push the largest element up to its parent.
   2. If the right sibling has more than m/2 items, shift the intervening element down to the node where the key is deleted and push the smallest element up to the parent.
4. Create a new leaf node by merging two leaf nodes and the parent node's intervening element if neither sibling has more than m/2 elements.
5. If the parent has less than m/2 nodes, repeat the operation on the parent as well.

If the node to be destroyed is an internal node, its in-order successor or predecessor should be used instead. Because the successor or predecessor will always be on the leaf node, the operation will be similar to deleting the node from the leaf node.

Example: 

                                                 source: staff.ustc.edu.cn

Applications

• Because accessing values held in a vast database saved on a disc is a very time-consuming activity, the B tree is used to index the data and enable fast access to the actual data stored on the discs.
• In the worst situation, searching an unindexed and unsorted database with n key values takes O(n) time. In the worst-case scenario, if we use B Tree to index this database, it will be searched in O(log n) time.
• A B-tree, in particular:
  • keeps keys sorted for sequential traversal and uses a hierarchical index to reduce disc reads
  • insertions and deletions are sped up by using partially filled blocks.
  • a recursive algorithm that keeps the index balanced
     

Recommended Topic, Schema in DBMS

FAQs

1. What is B-tree?
   A B-tree, is a tree data structure, that allows for logarithmic amortized searches, insertions, and removals while keeping data sorted. 
2. Where is B-tree mainly used?
   It's most typically found in database and file management systems.
3. What is the time-complexity of standard operations in B-tree?
   The time-complexity of standard operations in B-tree is as follows:

Key Takeaways

We learned that a B-tree is a tree data structure that keeps data sorted and permits logarithmic operations. We learned algorithms of standard operations for B-tree like searching, inserting, and deletion with examples, and then we learned applications of B-tree as well.
Check out this problem - Largest BST In Binary Tree

Also, try Coding Ninjas Studio to practice programming problems for your complete interview preparation.