B木は自己平衡探索木で、各ノードが多くのキーを保持し、多くの子ノードを持ちます（高いファンアウト）。これにより木が浅く保たれ、ディスク読み込みの回数が最小化されます。これはまさにデータベースとファイルシステムが必要とするものです。
Binary BST over 1,000,000 keys -> height ~20 (20 disk seeks)
B-tree, 100 keys/node -> height ~3 (3 disk seeks)
Each node = one disk block/page read.
[ 17 | 35 ]
/ | \
[4|9|12] [20|28] [40|50|60]
each node packs many keys -> few levels
B+木では、すべての値は葉ノードに存在し、葉ノードはリンクされているため、範囲スキャンは葉ノードのリンクリストを辿ります。これはWHERE age BETWEEN 20 AND 40のようなクエリに理想的です。
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| 操作 | 時間 | ディスク I/O |
|---|---|---|
| 探索 | O(log n) | O(高さ) |
| 挿入 / 削除 | O(log n) | O(高さ) |
| 範囲スキャン | O(log n + k) | 順序付き葉ノード |
ディスクおよびSSDへのアクセスはメモリアクセスより桁違いに遅いため、重要な指標は比較回数ではなくI/O回数です。
高いファンアウトは木をわずか数レベルの深さに保つことでI/O回数を大幅に削減します。
これが、ほぼすべてのリレーショナルデータベースインデックス（および多くのファイルシステム）がバイナリ探索木ではなくB+木で構築されている理由です。