平成28年度春期 データベーススペシャリスト 午前Ⅱ 問2

階層構造をそろえて考える

段数やノード数をそのまま計算に入れる前に、各用語がどの範囲を指すか、同じ基準で数えられているかを整理します。図の読み方と前提の対応を確認し、数量の意味を混同しないことが大切です。

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

確認する観点を、階層の数え方とノードのまとまり方の対応関係に絞ります。図中の一段が何を表し、容量を考える対象がどこまで含むのかを、問題文の定義と照らして整理してください。

視点

階層を持つ構造では、段・まとまり・格納対象などの言葉が、図全体と部分のどちらを指すかで意味が変わります。まず用語の範囲をそろえ、各段で数えている対象が同じ単位かを確認してから、与えられた条件同士の対応を整理します。

確認ポイント

• 段数の起点と終点が、図や説明のどこに対応しているか。
• ノード数が全体・各段・一部のいずれを指すか。
• 容量を考える対象の範囲と、数える単位が一致しているか。

正解

イ

解説

ルートの最大レコード数は2k個で、最大分岐数は2k＋1です。2段目以降では段が一つ増えるごとにノード数が2k＋1倍になるため、各段の最大レコード数を合計すると、全体は等比数列の和になり、(2k＋1)ⁿ－1となります。

理由

1段目のルートは最大2k個のレコードをもちます。ルートからの最大分岐数は、レコード数に1を加えた2k＋1です。したがって、各段の最大レコード数は、2k、2k(2k＋1)、…、2k(2k＋1)ⁿ⁻¹となります。これらを合計すると、2k×{(2k＋1)ⁿ－1}/((2k＋1)－1)＝(2k＋1)ⁿ－1レコードです。

比較

選択肢は、段数nを最後の段まで反映しているか、最大分岐数を正しく使っているかで判断します。最大分岐数は2k＋1であり、k＋1ではありません。また、対象は1段目からn段目までの全レコードなので、途中の段を含めた合計である必要があります。

選択肢ア

これは不正解だよ。式の指数がn−1であり、1段目からn段目までを対象とする条件に対して、最後の段までの増加を一段分反映できていません。さらに、この式だけでは各段の最大レコード数を合計した結果にならず、最大容量の条件と一致しません。

選択肢イ（正解）

これは正解だよ。ルートの最大レコード数は2k個、最大分岐数は2k＋1です。各段のレコード数を1段目からn段目まで合計すると、等比数列の和より2k×{(2k＋1)ⁿ−1}/(2k)＝(2k＋1)ⁿ−1レコードとなります。

選択肢ウ

これは不正解だよ。指数n−1であるため、1段目からn段目までの段数条件と一致しません。加えて、式の底がk＋1となっていますが、最大分岐数はルートの最大レコード数2kに1を加えた2k＋1です。したがって、ノード数の増加条件が異なります。

選択肢エ

これは不正解だよ。指数はnですが、式の底がk＋1となっています。B木で次の段へ分岐できる最大数は、最大レコード数2kに1を加えた2k＋1であり、k＋1ではありません。そのため、段ごとのノード数と総レコード数の増加を正しく表していません。

学習のポイント

B木の最大分岐数と段ごとのレコード数を、等比数列の和として整理する方法を学びます。