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

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

解答：イ

＜解説＞

B ^＋木はB 木を改良したもので，記憶領域を効率的に使用するために葉以外は各ノードへのポインタだけを格納し，データは葉のノードに格納します。ポ インタを順番にたどることで，一定の範囲内のデータを取り出すことが容易に なる。B ^＋木を利用したインデックスを，B ^＋木インデックスという。
B ^＋木では，1 件のデータの検索時に，根からスタートしてポインタをたどり，最終的にデータを格納する葉に到着します。根から葉までに経由するノード数
＝木の深さがデータ検索時のノードへのアクセス回数となる。
B ^＋木において，葉以外のノードが最大N 個の子ノードをもち，木の深さを d とするとき，データの総件数Xは
X＝ N^d
で表される。d はN を底とするXの対数であるため，
d ＝ log_NX
となる。