平成30年度春期 情報処理安全確保支援士 午前Ⅰ 問8

B+木のリーフ分割は「案内板」と「横のつながり」を更新するよ

B+木でリーフがいっぱいになって分割されると、親ノードには新しくできたリーフへ進むための子ポインタが追加されるよ。さらに、リーフ同士は本のページを順番にめくれるように、`B→C1→C2→D` の順でつながり直されるんだ。

この問題で問われていること

B木とB+木の違いを押さえつつ、リーフを分けたときに親ノードへ新しい子ポインタが増えること、そしてリーフ同士の順方向リンクも正しい順番に保たれることを理解しよう。

B+ Tree Leaf Split

after a B+ tree leaf split、 the parent points to both new leaves and leaf links remain ordered

parent children: B、 C1、 C2、 D\nleaf chain: B -> C1 -> C2 -> D

確認ポイント

• 親が 3 子のままではありません。
• リーフ順リンクを壊さない。
• 正答はイの構造です。

正解

イ

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア

これは不正解だよ。AからC2へ直接行くポインタがないので、C2だけ親から直接たどれない形になっているよ。駅の案内板にC2行きだけ書かれていなくて、別の場所を経由しないと行けないようなものだね。B+木は葉までの距離をそろえる必要があるから、この形は間違いだよ。

選択肢イ（正解）

これは正解だよ。CがC1とC2に分かれた後、親ノードAからB、C1、C2、Dへ同じ深さでたどれて、葉ノード同士もB、C1、C2、Dの順につながっているよ。図書館の索引で、棚の順番も案内板からの行き方もきれいにそろっている状態だから、B+木として正しいんだ。

選択肢ウ

これは不正解だよ。CがC1とC2に分かれたなら、葉ノードの並びはB、C1、C2、Dの順になるはずだよ。本棚で『Bの次にC、その次にD』と並べるところを、C2をDの後ろに置いてしまったようなものだね。順番が崩れるので間違いだよ。

選択肢エ

これは不正解だよ。B+木では、根からどの葉ノードに行くにも同じ段数で着く必要があるんだ。マンションの各部屋に同じ廊下ルートで行けるようにしておく感じだね。この図だとC2だけC1の下にぶら下がっていて、C2へ行く道のりだけ長くなるから、B+木のルールに合わないよ。