A B+ tree follows a multi-level index format and is a balanced binary search tree. A B+ tree’s leaf nodes denote actual data pointers. The B+ tree ensures that all leaf nodes stay balanced at the same height. In addition, a link list connects the leaf nodes; a B+ tree can therefore allow both random access and sequential access.
Structure of B+ Tree
Structure of B+ Tree
Each node on the leaf is the same distance from the root node. For any B+ tree, a B+ tree is of the order n where n is fixed.
Internal nodes −
Internal (non-leaf) nodes, except the root node, contain at least of [ n/2 ] pointers
At most, n pointers may contain an internal nod
Leaf nodes −
At least [ n/2 ] record pointers and [n/2] key values are stored in Leaf nodes.
At most, n record pointers and n key values will contain a leaf node.
Each node of the leaf contains a block pointer P to point to the next node of the leaf and forms a linked list.
B+ Tree Insertion
From the bottom, B+ trees are filled and every entry is done at the leaf node.
If a leaf node overflows −
Split node into two parts.
Partition at i = ⌊(m+1)/2⌋.
First i entries are stored in one node.
Rest of the entries (i+1 onwards) are moved to a new node.
ith key is duplicated at the parent of the leaf.
if a non-leaf node overflows −
Split node into two parts.
Partition the node at i = ⌈(m+1)/2⌉.
Entries up to i are kept in one node.
Rest of the entries are moved to a new node.
B+ Tree Deletion
At the leaf nodes, B+ tree entries are deleted.
The entry for the goal is searched and deleted.
If it is an internal node, delete it from the left position and replace it with an entry.
The underflow is tested after deletion,
If there is an underflow, allocate the entries from the nodes left over.
If distribution from the left is not possible, then
Distributing right to it from the nodes.
If distribution from the left or from the right is not feasible, then
Hey there, My name is Anup Maurya. I was born with love with programming and worked with TCS. One of best global (IT) services and consulting company as System Administrator . I also love graphics designing. It's my pleasure to have you here.