平成30年度春期応用情報技術者試験午前問26

Question

関係データベースのテーブルにレコードを1件追加したところ，インデックスとして使う，図のB⁺木のリーフノードCがノードC1とC2に分割された。ノード分割後のB⁺木構造はどれか。ここで，矢印はノードへのポインタとする。また，中間ノードAには十分な空きがあるものとする。

問題の図

キーボード：1〜4 で解答　→ 次の問題　← 前の問題

出典：平成30年度春期応用情報技術者試験午前問26

Answer 1

正解と解説を見る

正解：イ

B⁺木では，全てのリーフノードが同じ深さにあり，リーフノード同士はキーの順にポインタで連結されています（範囲検索のため）。

リーフノードCがC1とC2に分割されると，

親の中間ノードAに，新しいノードC2へのポインタ（とキー）が追加されます（Aには十分な空きがあるので，Aは分割されません）。
リーフノードの連結は，キー順を保つように B ⇔ C1 ⇔ C2 ⇔ D となります。
ア: AからC2へのポインタがない構造
誤り。中間ノードAからC2へのポインタがないため，C2のキーをAから検索できません。
イ: AからB，C1，C2，Dへのポインタがあり，リーフがB⇔C1⇔C2⇔Dと連結された構造
正しい。AからC2へのポインタが追加され，リーフノードがキー順に B ⇔ C1 ⇔ C2 ⇔ D と連結されています。
ウ: リーフの連結順がB⇔C1⇔D⇔C2となっている構造
誤り。Cを分割したC1とC2はキーの順で隣り合うはずなので，C1とC2の間にDが入るのは誤りです。
エ: C2がC1の下にぶら下がった構造
誤り。B⁺木では全てのリーフノードが同じ深さにあるので，C2がC1の下の階層に置かれることはありません。

イ: AからB，C1，C2，Dへのポインタがあり，リーフがB⇔C1⇔C2⇔Dと連結された構造

平成30年度 春期 応用情報技術者試験 午前 問26