LoginSignup
0
0

More than 3 years have passed since last update.

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

Posted at

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

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

image.png

1、B+木の例
image.png

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

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0