必ず受かる情報処理技術者試験

解答・解説を見る

解答：イ

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