B Tree: An Efficient Data Structure

B-tree in Data Structures

B-Trees, an extension of binary search trees (BST) designed for systems that read and write big blocks of data, were created in 1972 by Rudolf Bayer and Ed McCreight. They reduce the amount of disk accesses, which makes them especially helpful in file systems and databases.

In data structures that preserve sorted data and enable searches, sequential access, insertions, and deletions in logarithmic time, B-Trees are a kind of self-balancing search tree. In this Data Structures Tutorial, we will explore more about B-Tree which will include an Introduction to B-Trees and properties of B-Tree, etc.

B-Tree Time Complexity

Understanding the time complexity of a B-Tree's operations is important for figuring out its efficiency:

• For Searching : O(log n)
• For the inserting order: O(log n)
• For deletion: O(log n)

The balanced structure of the tree guarantees that the height of the tree increases logarithmically with the number of members, which accounts for the logarithmic time complexity.

Properties of the B-Tree

B-Trees have a number of significant characteristics.

• In a B-Tree, each node has a maximum of m children.
• With the exception of the root and leaf nodes, every node in a B-tree has at least m/2 children.
• There must be two or more nodes in the root nodes.
• Every leaf node needs to be at the same level.
• Each node must have m/2 nodes, however, it is not required that each node have the same number of children.

The graphic below depicts a B tree of order 4:

Why B-Tree Data Structure is Necessary?

B-Trees are necessary in the following situations:

• Data must be efficiently retrieved and stored in large quantities.
• Reducing disk I/O operations is necessary.
• Record deletions and insertions are frequently done dynamically.
• Sustaining an equilibrium framework is essential to guarantee steady performance.

Interesting B-Tree facts

• Ideal for storage on a disk: Because B-Trees reduce disk reads and write, they are perfect for file system and database implementations.
• Widely used in databases: The majority of relational databases in use today are B-Trees or their derivatives, such as B+ trees.
• Flexible order: A B-Tree (m)'s order can be changed to balance disk and memory use.

B-Tree Operations

1. Search Operation

Algorithm for Searching For an Element in a B-Tree

• Step 1: Assume the root node first.
• Step 2: Apply binary search to the current node's keys.
• Step 3: Return the node if the key can be located.
• Step 4: Return null if the current node is a leaf and the key cannot be located.
• Step 5: If the current node is not a leaf and the key is not found, search the relevant child subtree recursively.

Example

Binary search tree and B tree searching are comparable. For instance, let's say we look for item 27 in the B Tree that follows. The steps involved will resemble this:

• Compare root node 65 with item 27. Proceed to the sub-tree on the left since 27< 65.
• As 22<27<39, navigate the right sub-tree of 22;
• if 27>35, proceed to the right. Check 27.
• match found; please proceed.

The height of a B tree affects what can be found within it. Any element in a B tree can be searched using the search method in O(log n) time.

2. Insertion Operation

• Add the new element to the elements' increasing sequence.
• Divide the node at the median into two nodes.
• Move the median element to the level of its parent node.
• The same procedures should be used to split the parent node if it also contains m-1 keys.

Example

1. Insert node 9 into the B Tree of order 5 as seen in the image below.

2. Insert 9 since it will be placed to the right of 5.

3. The node now has five keys, which is more than the previous value of (5 -1 = 4). Consequently, push the node up to its parent node, which is displayed as follows, and divide it from the median, or 9.

3. Deletion Operation

Additionally, deletion takes place at the leaf nodes. There are two types of nodes that can be deleted: internal and leaf nodes. The following algorithm must be used to remove a node from a B tree.

• Find the Leaf node.
• Remove the desired key from the node if there are more than m/2 keys in the leaf node.
• Take the element from either the left sibling or the eighth to complete the keys if the leaf node is missing any m/2 keys.
• 1. Move the largest element of the left sibling up to its parent and the intervening element down to the node where the key is erased if the left sibling has more than m/2 elements.
• 2. Push the smallest element of the right sibling up to the parent and shift the intervening element down to the node where the key is erased if the right sibling has more than m/2 elements.

• Create a new leaf node by connecting two leaf nodes and the parent node's intervening element if neither of the siblings contains more than m/2 elements.
• Implement the aforementioned procedure on the parent as well if there are less than m/2 nodes remaining.

Example

1. In the B Tree of order 5, as depicted in the following picture, remove node 43.

2. The right child of element 30 contains 43. Remove it.

3. There are now just 55 items remaining in the node; a B tree of position 5 requires a minimum of 2 elements to exist. It is less than that, and since the elements in its left and right sub-trees are likewise insufficient, combine it with 30, the parent's left sibling and intervening element.

This is the last B tree displayed.

The Applications of B-Trees

B-Trees are often used in:

1. Database Indexing: B-Trees helps with fast searches, insertions, removals, and updates in database indexing.
2. File systems: B-trees are commonly used in file systems to hold directory information.
3. Multilevel indexing: B-trees are used to organize multi-level indices in huge datasets.

Example of B-Tree in Data Structure

Think about a B-Tree of order 3, where each node can have a maximum of two keys and three children. The following illustrates how to add keys 10, 20, 5, 6, 12, 30, 7, and 17 to a B-Tree that is initially empty:

Insert 10: [10]
Insert 20: [10, 20]
Insert 5: [5, 10, 20]
Insert 6: Split into [[5], 6, [10, 20]]
Insert 12: [[5], 6, [10, 12, 20]]
Insert 30: [[5], 6, [10, 12, 20, 30]]
Insert 7: [[5], 6, [7, 10, 12, 20, 30]]
Insert 17: Split into [[5, 6], 10, [12, 17, 20, 30]]    

Advantages of B-Trees

Disadvantages of B-Trees

Conclusion