B-Tree

Introduction

A B-tree is an extension of the balanced binary search tree. It addresses the shortcomings of balanced BST, making it suitable for on-disk data structures.

A B-Tree is also called an m-way (or multi-way) tree. Every node in the B-tree can accommodate M-1 keys and M pointers to child nodes. These keys are called separators. A B-tree keeps the keys sorted in ascending order and allows for a binary search:

• The first child pointer in the node points to the subtree that holds keys lesser than the first key.

• The last child pointer in the node references the subtree with keys greater than or equal to the final key.

• Child pointers (other than the first and last in the node) point to the subtree holding keys between the two key ranges Key$_i$$_-$$_1$ < Keys <= Key$_i$.

The order of a B-tree is the maximum number of children a given B-tree can hold.

Every node in a B-tree belongs to one of three types:

• Root node: Top of the tree with no parent.

• Leaf nodes: Bottom of the tree with no children.

• Internal nodes: Multilayered and connect the root with the leaves.