What is B-tree & B+ tree in DBMS?

Before you read this you can read this post Database Indexing makes DB Query faster

In this post we will go through B-tree & B+ tree, how these fit in DBMS.

B-tree and B+ tree both use for indexing of data. In order to make database query faster.

B-tree

A B-tree is a M-way tree with two unique properties, i) balanced, & ii) every leaf node is at same depth.

Unlike Binary Search Tree, B-tree can store large number of keys in a single node. This is why we use B-tree instead of traditional Binary Search Tree.

As the table grows, the index table also grows. In that case the query time can be increased (first checks index table then actual database table). The main purpose of B-tree is to efficiently split index table or to maintain sparse index so we don’t need to query a big index table.

For example, we have (index) keys 10, 15, 20, 25, 30, 35, 40, 45, 50 and each key points to a particular data,

The first three keys 10 15 20 store in first node,

Each node cannot take more than 3 keys, so for the next key 25 there will be two new nodes created,

We created two new nodes, once on the root and pushed 20 to that root and another on the right and pushed 25. And for 30 and 35,

For key 40,

We move 35 to root and created a new node which contains 40 as key. So for 45 and 50,

This is the actual how the insertion works in B-tree. The time complexity for that is O(log n).

So you can see B-tree is same as Binary Search Tree but each node can take more keys and balanced.

Each key which is an index points to a particular block of data in the table.

Now our indexes have their own block or node. The search complexity is O(log n) which is great for finding a key that points to a particular block of data, now our search query can be improved for huge amount of data.

B+ Tree

B+ tree is same as B-tree but in B+ tree the leaf nodes contain a copy of the root key.

In the picture you can see leaf nodes contain a copy of root key (20, 35).

Lets flip the tree with the database table so that we can understand easily,