SC情報処理安全確保支援士試験 午前Ⅰ

平成28年度秋期 情報処理安全確保支援士 午前Ⅰ 問9

問題文と選択肢を読んで答えを考えてから、下の「正解と解説を見る」で確認しましょう。

問題

B+木インデックスが定義されている候補キーを利用して,1件のデータを検索するとき,データ総件数Xに対するB+木インデックスを格納するノードへのアクセス回数のオーダを表す式はどれか。

選択肢

  1. ア
    √X
  2. イ
    log X
  3. ウ
    X
  4. エ
    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による補助生成を含む場合があります。公式の問題冊子・解答例・採点講評を優先し、誤りは確認後に訂正します。運営・編集方針