B木 — Termwire

ディスク上のデータを効率よく検索できるように設計された、バランスの取れた木構造。

2分探索木を発展させ、1つのノードに複数のデータを持たせることで、木の高さを低く抑えたまま大量のデータを扱える構造を持つ。ディスクへのアクセス回数を減らせるため、データベースのインデックスによく使われる。

ほとんどのリレーショナルデータベースが、インデックスの内部構造としてこのB木、あるいはその改良版を採用している。