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.
In more detail
A B-tree of minimum degree t keeps between t minus one and 2t minus one keys in each node (the root may hold fewer) and up to 2t children. Each node is sized to one disk block, so every level costs one disk read, and a fan-out in the hundreds or thousands keeps even billions of keys within three or four levels. Inserts split full nodes on the way down, so all leaves stay at the same depth.
Related terms
- minimum degree — The parameter t of a B-tree that sets how full its nodes are: at least t minus one and at most 2t minus one keys, except at the root.
- fan-out — The number of children each node of a tree can have.
- node split — The B-tree operation that breaks a full node into two half-full nodes and moves its middle key up into the parent.
- 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.
- index — A separate, sorted structure a database keeps alongside a table so it can find matching rows without reading them all.
- disk block — The fixed-size unit, typically a few kilobytes, in which data is read from and written to disk.
Taught in
- AVL Trees: Rotations That Keep The Guarantee — Algorithms & Data Structures for Working Engineers
- B-Trees: The Structure Behind Every Database Index — Algorithms & Data Structures for Working Engineers