B Tree: An Efficient Data Structure

B Tree: An Efficient Data Structure

10 Jun 2024
Beginner
92 Views
12 min read
Learn via Video Course & by Doing Hands-on Labs

Data Structures & Algorithms Free Course

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:

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

Any property of B Tree, such as the minimal number of children a node can have, may be violated while carrying out certain operations on B Tree. The tree may divide or unite in order to preserve B Tree's characteristics. Let's elaborate on the operations of B-Tree.

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.

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

The leaf node level is where insertions are made. To add an item to the B Tree, you have to conform to the following algorithm.
1. Locate the suitable leaf node where the node can be added by traversing the B Tree.
2. Insert the element in increasing order if the leaf node contains fewer than m-1 keys.
3. If not, proceed to the next step if the leaf node has m-1 keys.
  • 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.

 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.

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.

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.

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.

 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.

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

1. Logarithmic depth: It is maintained through a balanced framework.
2. Fewer disks: Its accesses are required for efficient disk use.
3. Dynamic resizing: Manages insertions and deletions effectively.
4. Sequential access: Range queries are possible because keys are kept in sorted order.

Disadvantages of B-Trees

1. Complex implementation: Compared to more straightforward structures like binary search trees, B-Trees require more work to implement.
2. Node splitting/merging overhead: Because node splitting and merging are required, insertions and deletions may be costly.
3. Space overhead: Internal nodes require additional room for keys and pointers.
Conclusion
B-trees are strong data structures that offer scalable and effective methods for handling big collections. They are essential in file systems and databases because of their balanced nature, which guarantees consistent performance. To test your practical understanding of these two techniques, enroll in our Best Data Structures And Algorithms Course.
Similar Articles on Data Structures
Queue in Data Structures
Priority Queue in Data Structures
AVL Tree in Data Structures
Trees in Data Structures
Interview Preparation
DSA Interview Questions and Answers (Freshers to Experienced)

FAQs

Q1. What is the formula for the B-tree?

The height of a B-Tree can be yielded via the following equation: h ≤ l o g m n + 1 2 , where m is the minimum degree and n is the number of keys.

Q2. What is key value in B-tree?

Keys are the values that are stored at any node.

Q3. Where are B-trees used in real life?

B-Trees are particularly well suited for storage systems that have slow, bulky data access such as hard drives, flash memory, and CD-ROMs.
Share Article

Live Classes Schedule

Our learn-by-building-project method enables you to build practical/coding experience that sticks. 95% of our learners say they have confidence and remember more when they learn by building real world projects.
Azure Developer Certification Training Jun 29 SAT, SUN
Filling Fast
07:00AM to 09:00AM (IST)
Get Details
.NET Microservices Certification Training Jun 29 SAT, SUN
Filling Fast
05:30PM to 07:30PM (IST)
Get Details
React JS Certification Training | Best React Training Course Jun 30 SAT, SUN
Filling Fast
08:30PM to 10:30PM (IST)
Get Details
ASP.NET Core Certification Training Jun 30 SAT, SUN
Filling Fast
10:00AM to 12:00PM (IST)
Get Details
Full-Stack .NET Developer Certification Training Jun 30 SAT, SUN
Filling Fast
11:00AM to 01:00PM (IST)
Get Details
Advanced Full-Stack .NET Developer Certification Training Jun 30 SAT, SUN
Filling Fast
10:00AM to 12:00PM (IST)
Get Details
Generative AI For Software Developers Jul 14 SAT, SUN
Filling Fast
08:30PM to 10:30PM (IST)
Get Details

Can't find convenient schedule? Let us know

About Author
Shailendra Chauhan (Microsoft MVP, Founder & CEO at Scholarhat by DotNetTricks)

Shailendra Chauhan is the Founder and CEO at ScholarHat by DotNetTricks which is a brand when it comes to e-Learning. He provides training and consultation over an array of technologies like Cloud, .NET, Angular, React, Node, Microservices, Containers and Mobile Apps development. He has been awarded Microsoft MVP 8th time in a row (2016-2023). He has changed many lives with his writings and unique training programs. He has a number of most sought-after books to his name which has helped job aspirants in cracking tough interviews with ease.
Accept cookies & close this