B木と平衡探索木とは？

B木と平衡探索木とは、挿入・削除を繰り返しても木の高さが偏らないよう自動的に釣り合いを保つ探索木。AVL木や赤黒木は主記憶向けの2分木、B木・B+木は1ノードに多数のキーを持たせて木を低くしたもので、データベースの索引に使われる。探索がO(log n)で保証される仕組みとして問われる。

びーきとへいこうたんさくき

応用情報技術者試験の頻出用語／テクノロジ系

B木と平衡探索木の意味

挿入・削除を繰り返しても木の高さが偏らないよう自動的に釣り合いを保つ探索木。AVL木や赤黒木は主記憶向けの2分木、B木・B+木は1ノードに多数のキーを持たせて木を低くしたもので、データベースの索引に使われる。探索がO(log n)で保証される仕組みとして問われる。

100万件のレコードをB+木で索引化し、1ノードに100個のキーを収めるとすると木の高さは3段程度になり、ディスクアクセスは3回前後で目的のリーフに到達できる。B+木ではデータをリーフだけに置き、リーフ同士を連結するため範囲検索が順次読み出しで済む。

単純な2分探索木は平衡ではなく、昇順のデータを順に挿入すると連結リスト状に退化して探索がO(n)になる。「2分探索木だから O(log n)」は誤りで、平衡化の仕組みがあって初めて保証される。

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。