B-tree
ブロック単位のストレージ向けに設計された平衡探索木。各ノードがディスクの1ページに対応して数百のキーを持つので、数十億行のテーブルでも検索は3～4回のディスクI/Oで済む。
1972年にBayerとMcCreightが考案した。ほぼすべてのリレーショナルデータベース（Postgres、MySQL/InnoDB、SQL Server、SQLite）で標準のインデックス型になっている。変種のB+木はデータを葉にだけ置き、葉同士をつなぐので、範囲スキャンが順次アクセスになる。点読み込みや点書き込みが多いOLTPに向く。
書き込みの多い負荷ではLSM木に劣る（ランダムI/Oで書き込みが増幅される）。RocksDB、Cassandra、ScyllaがLSMを選ぶのはそのためだ。