B-Tree
also: B+ tree
The wide, shallow sorted tree behind nearly every relational index — few disk reads to any row.
A B-tree keeps sorted keys in wide nodes sized to disk pages, so billions of keys sit 3–4 levels deep — a handful of page reads to find anything, and range scans come free from the sorted order. Updates happen in place, keeping reads fast and predictable, at the cost of random I/O on writes. Postgres, MySQL and SQLite indexes are B-trees; write-hungry stores pick LSM trees instead.
Worked example: a B-tree keeps data sorted in a balanced, high-fan-out tree so lookups, ranges, and inserts are O(log n) with few disk seeks — the default index for read-heavy relational databases. Gotcha: in-place page updates cause random I/O and write amplification under heavy writes, exactly where LSM trees win; B-trees favour reads and range scans, LSM favours writes.