平成28年度秋期 システムアーキテクト 午前Ⅰ 問9

索引のアクセス単位と計算量

キーの種類、記憶装置へのアクセス単位、木構造の数え方、オーダ記法を調べて準備しましょう。

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

データ件数とアクセス回数の関係を考える前に、何を1回と数え、増え方をどう表すか調べてみましょう。

索引のアクセス単位と計算量

データ件数とアクセス回数の関係を考える前に、何を1回と数え、増え方をどう表すか調べてみましょう。

確認ポイント

• 候補キー・主キー・非一意の検索キーは、どの条件で区別されますか。
• データベースのレコード・ページ・索引ノードは、それぞれどのような単位ですか。問題ではどの単位へのアクセスを数えていますか。
• 一般的な木構造の図で、全ノード数・階層数・ある経路上のノード数は、それぞれ何を数えていますか。 計算量のオーダ記法では、変数・定数倍・低次の項をどのように扱いますか。

正解

イ

解説

添付の公式解答PDF画像では，午前Ⅰ試験の問9の正解は「イ」と記載されている。B+木は葉の深さがそろった平衡木であり，候補キーによる検索では，根からキーに対応する葉へ進む。各階層で進む枝を選び，おおむね木の高さに相当する回数だけノードへアクセスする。分岐数を一定と考えると，木の高さはデータ総件数 X に対して対数的に増えるので，アクセス回数のオーダは log X となる。対数の底の違いは定数倍の違いであり，オーダには影響しない。

添付の公式解答PDF画像では，午前Ⅰ試験の問9の正解は「イ」と記載されている。B+木は葉の深さがそろった平衡木であり，候補キーによる検索では，根からキーに対応する葉へ進む。各階層で進む枝を選び，おおむね木の高さに相当する回数だけノードへアクセスする。分岐数を一定と考えると，木の高さはデータ総件数 X に対して対数的に増えるので，アクセス回数のオーダは log X となる。対数の底の違いは定数倍の違いであり，オーダには影響しない。

選択肢ア

誤り。B+木では各階層で探索対象を分岐に従って絞り込むため，アクセス回数はデータ総件数の平方根に比例するオーダにはならない。

選択肢イ（正解）

正しい。公式解答の問9はイ。B+木は平衡木であり，根から目的の葉までたどる階層数はデータ総件数 X に対して対数のオーダとなる。

選択肢ウ

誤り。データ総件数に比例するオーダは，全件を順に調べる探索などに相当する。B+木ではキーを比較して進む枝を選ぶため，全件を調べる必要はない。

選択肢エ

誤り。X!はXの階乗であり，組合せの並び順を網羅する処理などで現れる。B+木で目的のデータへ至る経路をたどる際のアクセス回数には対応しない。

学習のポイント

データ件数とアクセス回数の関係を考える前に、何を1回と数え、増え方をどう表すか調べてみましょう。