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.