B+ tree

A B-tree variant in which internal nodes hold only keys for routing and every record sits in the leaves, which are linked in order.

In more detail

Keeping only keys in internal nodes packs more of them per disk block, raising fan-out. Linked leaves make range scans a simple walk along the bottom level. Most relational database indexes and many filesystems use B+ trees.

Related terms

Taught in

References