B+木インデックスの探索回数

応用情報技術者平成28年秋期 午前27

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

１、B＋木の例

B+木インデックスでは探索範囲を1／nに狭めながら検索していきますが、B+木の深さはどの葉でも一定であるため、どの値を探索する場合でもほぼ同じアクセス回数になります。この深さは各節点が持つエントリ数(次数)で決まり、深さがh 、次数がbであるB+木における葉の最大数(X)は次の式で表せます。

　b^h＝X (上の例でいえば3^3＝27)

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

　h＝logb^X

参照：
https://www.ap-siken.com/kakomon/28_aki/q27.html