B-tree B-träd
Balanserat sökträd designat för blockbaserad lagring — varje nod motsvarar en disksida och rymmer hundratals nycklar, så ett uppslag tar bara 3–4 disk-I/O även för miljardrads-tabeller.
Bayer & McCreight (1972). Default-indextyp i nästan alla relationsdatabaser (Postgres, MySQL/InnoDB, SQL Server, SQLite). Variant B+-tree lagrar bara data i löv och länkar löven så range scans blir sekventiella. Bra för OLTP där du gör många riktade läsningar/skrivningar.
Förlorar mot LSM-träd vid skrivtunga workloads (writes-amplifierar via random I/O) — därför att RocksDB, Cassandra och Scylla väljer LSM.