B+ Trees
Prepared by
Biddut Kumar
Lecturer in CSE
What is B+ tree
A B+ tree is a data structure often used in the
implementation of database indexes. Each
node of the tree contains an ordered list of keys
and pointers to lower level nodes in the tree.
A B+ tree is a balanced tree in which every
path from the root of the tree to a leaf is of the
same length.
B+- Tree Characteristics
• Data records are only stored in the leaves.
• Internal nodes store just keys.
• All data is stored at the leaf nodes (leaf pages); all
other nodes (index pages) only store keys.
• All the leaf nodes are interconnected with each other
leaf nodes for faster access.
• Keys are used for directing a search to the proper leaf.
• If a target key is less than a key in an internal node,
then the pointer just to its left is followed.
• If a target key is greater or equal to the key in the
internal node, then the pointer to its right is followed.
• B+ Tree combines features of ISAM (Indexed
Sequential Access Method) and B Trees.
B+ TREE
INTERNAL NODE / INDEX node
LEAF NODES / DATA node
The linked list allows rapid traversal.
Structure of b+ tree
How to create or insert in B+:
=2,4,7,10,17,21,28
if n=4 n is the order
key=n-1=4-1=3
2
=2,4,7,10,17,21,28
2 4
=2,4,7,10,17,21,28
2 4 7
=2,4,7,10,17,21,28
2 4 7 10
=2,4,7,10,17,21,28
4 7
2 4 7 10 17
=2,4,7,10,17,21,28
4 7 10
2 4 7 10 17 21
=2,4,7,10,17,21,28
4 10 17
2 4 7 10 17 21 28
Math :
Consider a B+ tree with key size =10 bytes, block size=512 bytes, data pointer=8
bytes and block pointer=5 bytes. What is the order of leaf and non-leaf node?
Non-Leaf Node :
Suppose,
order of non-leaf node= n
Block pointer=Bp
n * Bp + (n-1)*key ≤ Block size
n*5+(n-1)*10 ≤ 512
5n+10n-10 ≤ 512
15n ≤ 512+10
n≤ 522/15
n≤ 34.8
The order of non-leaf node =34
Leaf Node :
Suppose,
order of leaf node= x
Data pointer= Dp
x*(key+Dp)+Bp ≤ Block Size
x*(10+8)+5 ≤ 512
18x+5≤ 512
18x≤ 512-5
x≤ 507/18
x≤ 28.17
The order of leaf node =28
Thank you
