B Tree and B+ Tree in DBMS | Core Computer

Science
Ujjwal
Ujjwal Abhishek
Abhishek

What is a B-Tree?

B Tree is a self-balancing tree data structure. It stores and maintains data in a sorted form
where the left children of the root are smaller than the root and the right children are
larger than the root in value. It makes searching efficient and allows all operations in
logarithmic time. It allows nodes with more than two children. B-tree is used for
implementing multilevel indexing. Every node of the B-tree stores the key-value along
with the data pointer pointing to the block in the disk file containing that key.

Properties of B-Tree

• Every node has at most m children where m is the order of the B-Tree.
• A node with K children contains K-1 keys.
• Every non-leaf node except the root node must have at least ⌈m/2⌉ child nodes.
• The root must have at least 2 children if it is not the leaf node too.
• All leaves of a B-Tree stays at the same level.
 • Unlike other trees, its height increases upwards towards the root, and insertion
happens at the leaf node.
• The time complexity of all the operations of a B-Tree is O(log n), here ‘n’ is the
number of elements in the B-Tree.

Example of a B-Tree of order 4

What is a B+ Tree?

A B+ tree is similar to a B-tree, the only difference is that their leaves are linked at the
bottom. Unlike B-tree, the nodes of the B+ tree do not store keys along with the pointers
to the disk block. The internal nodes contain only keys and the leaf nodes contain the keys
along with the data pointers. All the internal nodes are present at the leaves and are
linked together and can be traversed just like a linked list.

B+ tree also removes one drawback of using B-tree. The internal nodes of the B-tree also
store keys along with data pointers which take more space and significantly reduce the
number of keys that can be stored at a node of the B-tree. Due to this the number of
levels increases and searching time also increases. Unlike this, the B+ tree can store more
keys than the B-tree of the same level because of their feature of storing pointers only at
the leaf nodes. This contributes to storing more entries at fewer levels in the B+ tree and
lessens the searching time for a key. This makes the B+ tree very efficient and very quick
in accessing the data from the disks.
Example of B+ Tree

Differences between B-Tree and B+ Tree

B-Tree B+ Tree

All internal nodes and leaf nodes Only leaf nodes contain data pointers along with
contain data pointers along with keys. keys, internal nodes contain keys only.
Duplicate keys are present in this, all internal
There are no duplicate keys.
nodes are also present at leaves.
Leaf nodes are not linked to each other. Leaf nodes are linked to each other.
Sequential access of nodes is not All nodes are present at leaves, so sequential
possible. access is possible just like a linked list.
Searching for a key is slower. Searching is faster.
For a particular number of entries, the The height of the B+ tree is lesser than B-tree
height of the B-tree is larger. for the same number of entries.
 Ujjwal Abhishek
Ujjwal is final-year CSE Undergraduate, a competitive coder, and a web developer passionate about
problem-solving and data structures and algorithms.

Practice Data Structures & Algorithms

Learning
Learning Resources
Resources
 Interview Prep Resources

Community
Community

Join our community

About FAQs Terms Privacy

hi@workat.tech

Blog
Career Advice and Roadmaps
Data Structures & Algorithms
Machine Coding Round (LLD)
System Design & Architecture
Backend Development
Frontend Development
Awesome Project Ideas
Core Computer Science
 Practice Questions
Machine Coding (LLD) Questions
System Design (HLD) Questions
Topic-wise DSA Questions
Company-wise DSA Questions
DSA Sheets (Curated Lists)
JavaScript Interview Questions
Frontend UI Machine Coding Questions

Online Compilers (IDE)

Topic-wise Problems
Dynamic Programming Interview Questions
Linked List Interview Questions
Graph Interview Questions
Backtracking Interview Questions
Arrays Interview Questions
Trees Interview Questions

Company-wise Problems
Amazon Interview Questions
Microsoft Interview Questions
Google Interview Questions
Flipkart Interview Questions
Adobe Interview Questions
Facebook Interview Questions
 DSA Sheets (Curated Lists)
Top Interview Questions
FAANG Interview Questions
Most Asked Interview Questions
6 month DSA Practice Sheet
3 month DSA Practice Sheet
Last minute DSA Practice Sheet

© 2020-2022 WORKATTECH TECHNOLOGIES PVT LTD