B+ tree Index Files

A B⁺ tree is a balanced binary search tree that follows a multi-level index format. The leaf nodes of a B⁺ tree denote actual data pointers. B⁺ tree ensures that all leaf nodes remain at the same height, thus balanced. Additionally, the leaf nodes are linked using a link list; therefore, a B⁺ tree can support random access as well as sequential access.

Structure of B⁺ Tree

Every leaf node is at equal distance from the root node. A B⁺ tree is of the order n where nis fixed for every B⁺ tree.

Internal nodes −

• Internal (non-leaf) nodes contain at least ⌈n/2⌉ pointers, except the root node.
• At most, an internal node can contain n pointers.

Leaf nodes −

• Leaf nodes contain at least ⌈n/2⌉ record pointers and ⌈n/2⌉ key values.
• At most, a leaf node can contain n record pointers and n key values.
• Every leaf node contains one block pointer P to point to next leaf node and forms a linked list.

B⁺ Tree Insertion

• B⁺ trees are filled from bottom and each 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.
  • i^th 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

• B⁺ tree entries are deleted at the leaf nodes.
• The target entry is searched and deleted.
  • If it is an internal node, delete and replace with the entry from the left position.
• After deletion, underflow is tested,
  • If underflow occurs, distribute the entries from the nodes left to it.
• If distribution is not possible from left, then
  • Distribute from the nodes right to it.
• If distribution is not possible from left or from right, then
  • Merge the node with left and right to it.

www.techglads.com