B+ tree

A B+ tree is a variant of the B-tree where all values are stored in the leaf nodes and internal nodes hold only keys used for routing. Leaf nodes are linked together in a sorted doubly linked list. This distinction has a significant practical effect: range queries traverse only the leaf layer rather than the entire tree, and all records are equidistant from the root, giving uniform access time.

internal:    [10 | 20 | 30]
              /    |    \   \
leaves:  [5,7] - [10,15] - [20,25] - [30,35,40]
          ^--- leaf nodes linked in sorted order

Because internal nodes hold no values, they are more compact and can hold more keys per node than in a B-tree. A higher branching factor means a shorter tree for the same number of records, which means fewer I/O operations to reach a leaf. For a database with millions of rows, a B+ tree of height 3 or 4 is common.

Range scans are the decisive advantage over a B-tree. To answer SELECT * FROM t WHERE key BETWEEN 20 AND 35, the tree descends to the leaf containing 20, then follows the leaf chain to collect all records up to 35 without returning to the root. In a B-tree the same query would require an in-order traversal of the tree.

B+ trees are the dominant index structure for relational databases (MySQL InnoDB, PostgreSQL, Oracle) and many filesystems. The leaf chain also supports efficient iteration over all records in key order, which is used for sort-merge joins and ordered scans.