B+ Tree


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

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
    • Merge to the left and right of the node.

You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More

Enable Notifications    OK No thanks