基本情報技術者試験「B木とB+木」の問題
データベースの索引に用いられるB+木の、B木と比べた特徴として最も適切なものはどれか。
ア各ノードが必ず2個の子だけを持ち、木の高さが2分探索木と同一になる
イキーを葉ノードにだけ格納せず内部ノードのみに置き、葉には何も保持しない
ウ全ての実データ(キー)を葉ノードに格納し、葉同士をポインタで連結して範囲検索を効率化する
エ木を用いず配列の二分探索で代替するため、挿入・削除のたびに全体を並べ替える
正解
ウ．全ての実データ(キー)を葉ノードに格納し、葉同士をポインタで連結して範囲検索を効率化する
B+木は内部ノードを探索の道標とし、実データ(キー)を全て葉ノードに置く。さらに葉同士を連結リストでつなぐため、ある範囲のキーを葉をたどって連続取得でき範囲検索に強く、正しい。
?選択肢ごとの解説
ア ×各ノードが2個の子に限られ高さが2分探索木と同じになるのは2分木の話であり、B+木は1ノードが多数の子を持つ多分岐木でディスクアクセスを減らす。
イ ×内部ノードのみにキーを置き葉に何も持たないのは説明が逆で、B+木は実データを葉に集約する。内部はキーの分岐情報のみを持つ。
ウ ○B+木は内部ノードを探索の道標とし、実データ(キー)を全て葉ノードに置く。さらに葉同士を連結リストでつなぐため、ある範囲のキーを葉をたどって連続取得でき範囲検索に強く、正しい。
エ ×木を使わず配列の二分探索で代替するのは別手法であり、挿入削除のたびに全体を並べ替える非効率も伴うためB+木の特徴ではない。
✎くわしく
B木は内部ノードにもデータを持つのに対し、B+木はデータを葉に集約し葉を連結する。これにより範囲検索・順次走査が葉のたどりだけで済む。多分岐により木が低くなりディスクI/O回数を抑えられる点も含め、DB索引で広く採用される。
✓本番での押さえどころ
試験のコツ
『B+木=データは葉に集約+葉を連結して範囲検索が速い』『多分岐で木が低い』と特徴を結びつけて覚える。
覚え方
B+木の『+』は『葉を横に連結する線が足された』と覚え、範囲スキャンが速いことに結びつける。
よくある誤り
B木とB+木のデータ格納位置を取り違える、または2分木と混同して『子は2個』と誤る例が多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0127