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

【正解】イ

B⁺木は、一つのノードから複数の子ノードへ枝分かれする平衡木です。どの葉までたどっても木の深さがほぼ同じになるように保たれています。1ノード当たりの分岐数をmとすると、深さが1増えるごとに格納可能なキー数はおおむねm倍になり、深さhで扱える件数は約mのh乗です。したがって、X≒mのh乗からh≒logₘXとなります。候補キーは値が一意なので、ルートから目的の葉まで一つの経路をたどれば1件を特定でき、ノードへのアクセス回数はO（log X）です。このため、イが正解です。

アの√Xは誤りです。平方根に比例するアクセス回数は、B⁺木の段階的な絞込みを表すオーダーではありません。

ウのXは誤りです。これは全件を先頭から順に調べる線形探索、すなわち表の全走査に相当するオーダーです。B⁺木を候補キー検索に利用すれば全件走査は不要です。

エのX!は誤りです。階乗時間はX個の要素の全ての並べ方を調べるような組合せ探索で現れるものであり、索引検索とは関係しません。

【ポイント】 B⁺木の検索、挿入、削除の基本的な計算量はO（log X）です。 対数の底は分岐数で決まりますが、オーダー表記では底を省略できます。 等価検索だけでなく範囲検索にも適した索引です。