SC情報処理安全確保支援士試験 午前Ⅰ
平成28年度秋期 情報処理安全確保支援士 午前Ⅰ 問9
問題文と選択肢を読んで答えを考えてから、下の「正解と解説を見る」で確認しましょう。
問題
選択肢
- ア√X
- イlog X
- ウX
- エX!
解き方のヒントを見る
索引のアクセス単位と計算量
キーの種類、記憶装置へのアクセス単位、木構造の数え方、オーダ記法を調べて準備しましょう。
この問題で問われていること
データ件数とアクセス回数の関係を考える前に、何を1回と数え、増え方をどう表すか調べてみましょう。
索引のアクセス単位と計算量
データ件数とアクセス回数の関係を考える前に、何を1回と数え、増え方をどう表すか調べてみましょう。
確認ポイント
- 候補キー・主キー・非一意の検索キーは、どの条件で区別されますか。
- データベースのレコード・ページ・索引ノードは、それぞれどのような単位ですか。問題ではどの単位へのアクセスを数えていますか。
- 一般的な木構造の図で、全ノード数・階層数・ある経路上のノード数は、それぞれ何を数えていますか。 計算量のオーダ記法では、変数・定数倍・低次の項をどのように扱いますか。
正解と解説を見る
正解
イ
解説
午前Ⅰ試験の問9の正解は「イ」です。B+木は葉の深さがそろった平衡木であり,候補キーによる検索では,根からキーに対応する葉へ進む。各階層で進む枝を選び,おおむね木の高さに相当する回数だけノードへアクセスする。分岐数を一定と考えると,木の高さはデータ総件数 X に対して対数的に増えるので,アクセス回数のオーダは log X となる。対数の底の違いは定数倍の違いであり,オーダには影響しない。
正答
正解はイ(log X)です。B+木は全ての葉が同じ深さにそろった平衡木で,キーの大小を比較しながら根から葉へ一方向にたどる。1ノードの分岐数を m とすると,高さ h の木が扱える件数はおよそ m^h なので,X ≈ m^h から h = log_m X となる。検索で必要なノードアクセス回数は木の高さ h に相当するので,オーダは log X です。対数の底 m は定数であり,底の違いは定数倍の差にすぎずオーダには影響しない。
誤答の理由
ア:√X は件数の平方根に比例するオーダであり,B+木の検索には当てはまらない。各階層で分岐数に応じて探索対象が大きく絞られるため,木の高さは対数的にしか増えないからです。
ウ:X は件数に比例して増えるオーダで,全件を先頭から順に調べる線形探索に相当する。B+木は比較によって進む枝を選ぶため,全件を調べる必要はない。
エ:X! は X の階乗であり,組合せの並べ方を網羅するような処理に現れる。B+木の検索は木の高さの分だけ経路をたどるだけなので,階乗のような急激な増え方とは対応しない。
整理
B+木の検索では「アクセス回数=木の高さ」と覚え,木の高さは件数に対して対数で増えると押さえる。分岐数が大きいほど木は低くなるため,ディスクへのアクセス回数が減り,データベースのインデックスに広く使われる。
選択肢ア
誤り。B+木では各階層で探索対象を分岐に従って絞り込むため,アクセス回数はデータ総件数の平方根に比例するオーダにはならない。
選択肢イ(正解)
正しい。問9の正解はイである。B+木は平衡木であり,根から目的の葉までたどる階層数はデータ総件数 X に対して対数のオーダとなる。
選択肢ウ
誤り。データ総件数に比例するオーダは,全件を順に調べる探索などに相当する。B+木ではキーを比較して進む枝を選ぶため,全件を調べる必要はない。
選択肢エ
誤り。X!はXの階乗であり,組合せの並び順を網羅する処理などで現れる。B+木で目的のデータへ至る経路をたどる際のアクセス回数には対応しない。
学習のポイント
データ件数とアクセス回数の関係を考える前に、何を1回と数え、増え方をどう表すか調べてみましょう。
解説を確認したら、演習モードや同じ分野の類題で理解を定着させましょう。
出典:独立行政法人 情報処理推進機構(IPA)平成28年度秋期 情報処理安全確保支援士試験 午前Ⅰ 問9(公式資料:問題冊子(PDF) / 解答例)
関連する過去問一覧
IPA Advancedは非公式の学習サイトです。解説にはAIによる補助生成を含む場合があります。公式の問題冊子・解答例・採点講評を優先し、誤りは確認後に訂正します。運営・編集方針