平成30年度 春期 午前 問26
データベース
リーフノードに関する問題
関係データベースのテーブルにレコードを 1 件追加したところ，インデックスとして使う，図の B⁺木のリーフノード C がノード C1 と C2 に分割された。ノード分割後の B⁺木構造はどれか。ここで，矢印はノードへのポインタとする。また，中間ノード A には十分な空きがあるものとする。
〔図〕分割前の B⁺木
（枠と矢印の絵）
上位から A へ向かう矢印が 1 本入る。
A
／│＼
B C D ← 中間ノード A から 3 本の矢印がそれぞれ B・C・D へ
リーフは B ⇔ C ⇔ D の順に並び、隣どうしが両向きの矢印で結ばれている。- アA から B・C1・D の 3 本の矢印。リーフは B ⇔ C1 ⇔ C2 ⇔ D の順に結ばれている。
- イA から B・C1・C2・D の 4 本の矢印。リーフは B ⇔ C1 ⇔ C2 ⇔ D の順に結ばれている。
- ウA から B・C1・D・C2 の 4 本の矢印。リーフは B ⇔ C1 ⇔ D ⇔ C2 の順に結ばれている。
- エA から B・C1・D の 3 本の矢印。C2 は C1 の下にぶら下がり，C1 ⇔ C2 が両向きの矢印で結ばれている。
答えと解説を見る
✓ これが正解イA から B・C1・C2・D の 4 本の矢印。リーフは B ⇔ C1 ⇔ C2 ⇔ D の順に結ばれている。
解説
割れたら親は両方を指します。
設問は、リーフノードが二つに分割された後の木の形を選ばせています。軸になるのは二つの決まりだけで、矢印をすべて追う必要はありません。一つ目は、葉がすべて同じ深さにそろうことです。中間ノードのすぐ下の一段に葉が横並びになり、どの葉へも同じ段数で降りられます。二つ目は、葉がキーの順に横へ並び、隣どうしがポインタで結ばれることです。これがあるおかげで、範囲を指定した検索のときに木を上から降り直さず、葉の列を横へたどるだけで済みます。そこで分割された二つの葉を元の位置に当てはめると、並びは左の葉、分割でできた前半、分割でできた後半、右の葉の順になります。親は分割でできた二つのどちらへも降りられなければならないので、出ていく矢印は三本から四本へ増えます。この二つを当てれば、形を選ぶ問はその場で決まります。
ほかの選択肢はなぜ違うのか
- アA から B・C1・D の 3 本の矢印…：親から出る矢印が三本のままで、分割して生まれた後半の葉を指していません。横の連結だけでは上から降りられず、索引として使えなくなります。
- ウA から B・C1・D・C2 の 4 本…：横の並びが右端の葉をまたいだ順序になっています。キーの順に並ぶという決まりが破れるので、範囲を指定した検索で横へたどれません。
- エA から B・C1・D の 3 本の矢印…：分割して生まれた葉が、もう一方の葉の下にぶら下がっています。葉の深さがそろうという決まりに反するため、形として成り立ちません。
この問題の用語
- 関係データベースデータを表の形で持ち、表どうしを結びつけて扱う、最も広く使われているデータベース。データの定義や操作にはSQLを使います。
出典：平成30年度 春期 応用情報技術者試験 午前 問26（改変：原典の図表をテキストに書き起こした）
同じ用語が出る問題
- 令和7年度 秋期 午前 問28：ビューに関する記述（関係データベース）
- 令和7年度 春期 午前 問25：多重度に関する問題（関係データベース）
- 令和5年度 春期 午前 問30：参照制約に関する問題（関係データベース）
- 令和5年度 春期 午前 問26（関係データベース）
- 令和3年度 春期 午前 問28：NoSQLに関する問題（関係データベース）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）