EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login

B Tree in Data Structure

By Priya PedamkarPriya Pedamkar

Home » Data Science » Data Science Tutorials » Data Structures Tutorial » B Tree in Data Structure

b tree in data structure

Introduction to B Tree in Data Structure

B-Tree is a data structure that stores data and allows operations such as searching, insertion, and deletion systematically. There are certain aspects associated with B-Tree, which deal with the tree in its balanced form. So, for having the balanced tree, there should be n/2 keys in each node, n being the B-Tree order. The other considerations are as follows.

  • All leaf nodes must be present at the same level.
  • There can be at maximum n – 1 key for all nodes.
  • There are at least two children for the root.
  • n is the maximum number of children, and k is the number of keys that each node can contain.
  • There are at least n/2 children and at most n non-empty children.
  • The tree gets divided so that values in the left subtree shall be less than the value in the right subtree.

B-Tree Visual Representation

A sample visual representation of B-Tree is as shown below. It is a balanced tree that follows all the constraints which are associated with the concept.

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

B Tree in Data Structure - 11

In the above B-Tree, all the leaf nodes are at the same level. The number of keys in non-leaf nodes is less than that of in the children nodes.

How does B-Tree Data Structure Works?

Let’s understand the working of B-Tree through insertion and deletion operations. There are two cases associated with the insertion of a key in B-Tree. These are, first that node is not full, and secondly, the node is already full. Insertion of a key happens in the node if it’s a leaf node that is not full. In case the node is full, then the node is split at the median into two nodes, the level remaining the same, and a level ups the median element.

1. Insertion Operation

We will see how insertion happens into a B-Tree for a set of 6, 10, 5, 8, 2, 4, 9, 7, 1, and 5.5.

  • The first Element Inserted is 6.

first Element

  • Next Element to be Inserted is 10. It is greater than 6, and so will go to the right of it as shown below.

Inserted is 10

  • 5 is less than 6, so it goes to the left of the tree, as shown below.

left of the tree

  • Now, before the next element is inserted, it is checked if the tree is full. As the tree is now full, so a new empty node is allocated. This node is made the root, while the former root is split, with 6 put into the new root. So, when 8 gets inserted into the tree, the arrangement becomes as shown below.

new root

  • The next element to be inserted is 2. It will go in the left subtree before 5. The arrangement now looks like as shown below.

left subtree

  • Now, the next element to be inserted is 4. It goes into the left subtree as it is less than 6. It occupies the middle position in the node as shown by the following B- tree arrangement.

B Tree in Data Structure - 6

  • The next step is essential. We now have 9 and 7 as the next two elements to be inserted into the B-Tree. As the node is full in this case, it is split, and the middle child is brought into the root. We get the B-Tree arrangement as can be seen below. Here, 9 went into the root, while 7 joined 8, with 10 going into a separate node.

B Tree in Data Structure - 7

  • The last two elements that we have are 1 and 5.5. 1 will go into the left subtree with 2, 4, and 5. The tree is split, and the middle child is sent up the root. Now, we have 5 and 5.5 in a separate node. The B-Tree arrangement looks like, as shown below.

B Tree in Data Structure - 8

2. Deletion from B-Tree

While performing the deletion from B-Tree, a traversal through the tree happens. After reaching the concerned node two cases may occur, the first node is the lead node, and the second node is the non-leaf node. We shall see how deletion happens in B-Tree through the following example.

Popular Course in this category
All in One Data Science Bundle (360+ Courses, 50+ projects)360+ Online Courses | 1500+ Hours | Verifiable Certificates | Lifetime Access
4.7 (3,220 ratings)
Course Price

View Course

Related Courses
Oracle DBA Database Management System Training (2 Courses)SQL Training Program (7 Courses, 8+ Projects)
  • Let’s consider that we intend to delete 5 from the above B-Tree arrangement 5 is present in the leaf node, so it will be deleted, giving the B-Tree arrangement below.

B Tree in Data Structure - 9

  • Now, what if we delete a non-leaf node. 4 is a non-leaf node. We shall delete it. Once 4 is deleted, we get the arrangement as shown below.

B Tree in Data Structure - 10

  • So, we find 5.5 and 9 going up by one level. 5.5 goes into the node having 1 and 2. 9, on the other hand, goes into the root node along with 6.

Advantages of B-Tree

Below are the advantages of B-Tree:

  • B-Tree facilitates ordered sequential access, and so it works effectively as compared to a hash table.
  • It allows iterations over items in a much similar way as what is supported by a binary tree. The iterations arrange the items in the proper order (ascending or descending) as required.
  • The tree can have millions of items stored in it, and through its flat structure, it facilitates easy and efficient traversal through the data.
  • When there are millions of records, then deleting a record from a table can turn out to be expensive, because the table may need to be rewritten. However, if B-Tree is used to handle sequential access to the table, or if the entire data is stored in B-Tree nodes, then deletion operation can be made simpler.

Conclusion

B-Tree is a data structure that efficiently assists in data operations, including insertion, deletion, and traversal. The usefulness of data structure is evident not in small applications but is impactful in real-world situations involving huge datasets.

Recommended Articles

This is a guide to B Tree in Data Structure. Here we discuss data operations including insertion, deletion, and traversal with advantages. You can also go through our other related articles to learn more –

  1. What is Data Structure?
  2. Types of Trees in Data Structure
  3. Data Structure Interview Questions
  4. Data Science Applications
  5. Working of Stack in Data Structure

All in One Data Science Bundle (360+ Courses, 50+ projects)

360+ Online Courses

50+ projects

1500+ Hours

Verifiable Certificates

Lifetime Access

Learn More

1 Shares
Share
Tweet
Share
Primary Sidebar
Data Structures Tutorial
  • Basics
    • What is Data Structure
    • Heap Data Structure
    • Types of Trees in Data Structure
    • AVL Tree in Data Structure
    • B Tree in Data Structure
    • B+ Tree in Data Structure
    • DFS Algorithm
    • BFS Algorithm
    • Arrays in Data Structure
    • Graph in Data Structure
    • Graph Representation
    • Breadth First Search
    • Depth Limited Search
    • Searching in Data Structure
    • Linear Search in Data Structure
    • Linked List in Data Structure
    • Doubly linked list in Data Structure
    • Circular Linked List in Data Structure
    • Pointers in Data Structure
    • Types of Graph in Data Structure
    • Bubble Sort in Data Structure
    • Quick Sort in Data Structure
    • Merge Sort in Data Structure
    • Selection Sort in Data Structure
    • Insertion Sort in Data Structure
    • Stack in Data Structure
    • Queue in Data Structure
    • Asymptotic Analysis
    • Kruskal’s Algorithm
    • Prim’s Algorithm
    • BFS VS DFS
    • BCNF
    • Data Structure Interview Questions
    • Data Structures & Algorithms Interview

Related Courses

All in One Data Science Course

Oracle DBA Course

SQL Certification Course

Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

© 2020 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA Login

Forgot Password?

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you
Book Your One Instructor : One Learner Free Class

Let’s Get Started

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

Special Offer - All in One Data Science Course Learn More