BUILD YOUR UNDERSTANDING
情報処理技術者試験の用語集
言葉の意味を確かめて、問題への理解を一歩深めましょう。
B木
高さを抑えた探索木
B木は、一つの節に複数のキーと子への参照を持ち、平衡を保ちながらデータを探索する木構造です。データベースやファイルシステムの索引で関連する構造が使われます。二分探索木のように子を二つに限定せず、多くの分岐を持てるため、全体の高さを抑えられます。記憶装置からブロックを読む回数を少なくするという観点で有用です。
探索の考え方
節の中に並んだキーと目的の値を比較し、該当する範囲の子へ進みます。各段階で候補の範囲が狭まり、必要な枝をたどって目的のデータへ到達します。例えば区切りが20と50なら、20未満、20から50の間、50より大きい範囲というように進む先を選べます。全ての枝を端から調べる必要はありません。
追加と削除
キーが増えて節に収まらなくなったときは、分割などによって構造を調整します。削除でキーが少なくなった場合も、隣接する節との再配分や併合などを行います。この調整によって、特定の方向だけが極端に深くなることを防ぎます。単純な二分探索木では挿入順序により偏りが生じることがありますが、平衡を維持する設計では探索の長さを抑えやすくなります。
範囲検索との相性
キーの大小関係に基づいて管理するため、等しい値だけでなく、日付がある区間に含まれる行などを探す用途に適しています。B+木では葉にデータへの参照をまとめ、葉同士をつなぐ構造が使われるなど、派生方式によって詳細は異なります。「B木」という言葉だけで、全製品の内部配置が完全に同じだとは考えないようにします。
ハッシュとの比較
ハッシュ方式はキーから位置を求めるため、等値検索に向く場面があります。一方、大小順の区間をそのままたどる設計とは異なります。試験では、データ件数が増えたときの探索量、平衡、分岐数、範囲検索という観点で比較します。索引の採用は読み取りだけでなく更新や保存領域にも影響するため、木の高さが低いことだけで性能を断定しないことが重要です。
参考資料
内容確認日:2026-11-13