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
- B-tree — A balanced search tree whose nodes each hold many sorted keys and have many children, so the tree is very wide and very shallow.
- index — A separate, sorted structure a database keeps alongside a table so it can find matching rows without reading them all.
- range query — A request for every item whose key lies between two bounds, such as all orders placed between 9:00 and 10:00.
Taught in
- B-Trees: The Structure Behind Every Database Index — Algorithms & Data Structures for Working Engineers