令和5年度 秋期 データベーススペシャリスト試験 午前Ⅱ試験 問4

令和5年度 秋期 データベーススペシャリスト試験 午前Ⅱ試験 問4を解いてみましょう。

答えは 「イ」です。

B⁺木インデックスの検索は、根から始めて、葉までポインタをたどっていきます。葉に到達するまでに経由するノード数は、B⁺木の深さになります。

B⁺木の深さは、データ総件数Xと、B⁺木の次数bによって決まります。次数bが固定されている場合、深さは次式で表されます。

h = log_b X

したがって、データ総件数Xに対するB⁺木インデックスを格納するノードへのアクセス回数のオーダは、log Xとなります。

なお、B⁺木インデックスの深さは、データ総件数が少ない場合は浅く、データ総件数が多い場合は深くなります。そのため、X!のような、Xに比例しないオーダはありえません。