情報セキュリティスペシャリスト 平成28年秋期 午前T 問9

午前T 問9

B+木インデックスが定義されている候補キーを利用して,1件のデータを検索するとき,データ総件数Xに対するB+木インデックスを格納するノードへのアクセス回数のオーダを表す式はどれか。
  • [この問題の出題歴]
  • 応用情報技術者
    平成28年秋期 問27と同題

分類

テクノロジ系 » データベース » トランザクション処理

正解

解説

B+木インデックスは、木の深さが一定で、節点はキー値と子部分木へのポインタをもち、葉のみが値をもつ平衡木(バランス木)を用いたインデックス法です。関係データベースのインデックス法として現在最も普及しています。データ量が増加してもパフォーマンスの低下が少なく、どのキー値に対してもランダム検索や範囲検索、挿入・更新・削除を効率よく行える特徴をもちます。
am1/27a.gif/image-size:501×244
B+木インデックスでは探索範囲を1/nに狭めながら検索していきますが、B+木の深さはどの葉でも一定であるため、どの値を探索する場合でもほぼ同じアクセス回数になります。この深さは各節点が持つエントリ数(次数)で決まり、深さがh 、次数がbであるB+木における葉の最大数(X)は次の式で表せます。

 bh=X (上の例でいえば33=27)

つまりX件のデータを探索する際のアクセス回数を示す深さhは、

 h=logbX

このため、アクセス回数のオーダはXの対数「O(logX)」になります。
© 2014-2019 情報処理安全確保支援士ドットコム All Rights Reserved.

Pagetop