基本情報技術者試験「インデックス」の問題
関係データベースで広く用いられるB木(B-tree)インデックスの特徴として最も適切なものはどれか。
ア木を平衡に保ち探索・挿入・削除を対数時間で行える
イキーをハッシュ化し範囲検索を最も得意とする
ウ全行を先頭から順に走査して目的行に到達する
エ更新のたびに全索引を再構築し整合を取る方式である
正解
ア．木を平衡に保ち探索・挿入・削除を対数時間で行える
B木は各ノードが複数のキーを持ち、挿入・削除時に分割や併合で高さを均衡に保つ平衡木である。これにより探索・挿入・削除を木の高さに比例するO(log n)で行えるため正しい。
?選択肢ごとの解説
ア ○B木は各ノードが複数のキーを持ち、挿入・削除時に分割や併合で高さを均衡に保つ平衡木である。これにより探索・挿入・削除を木の高さに比例するO(log n)で行えるため正しい。
イ ×キーをハッシュ化するのはハッシュインデックスの特徴で等値検索に強い反面、範囲検索は苦手であり説明が逆である。
ウ ×先頭から順に全行を走査するのは索引を使わない全表走査(フルスキャン)であり、B木による高速探索とは異なる。
エ ×更新のたびに全索引を再構築する方式ではなく、B木は局所的なノード分割・併合で増分的に整合を保つ。
✎くわしく
B木は1ノードに多数のキーを詰めることで木を低く保ち、ディスクI/O回数を抑える。常に平衡が保たれるため最悪計算量も対数時間。等値検索だけでなく範囲検索(BETWEEN等)にも順序が活かせる点でハッシュ索引と差別化される。
✓本番での押さえどころ
試験のコツ
『B木=平衡・対数時間・範囲検索可』『ハッシュ=等値特化・範囲弱い』の対比で選択肢を判定する。
覚え方
B木は『枝分かれの浅い太い木』。少ない段数で目的に届く=対数時間、と高さの低さで覚える。
よくある誤り
B木索引とハッシュ索引の得意分野を取り違える誤りが多い。範囲検索ならB木、等値の高速一致ならハッシュと整理する。
データベースの他の問題
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0059