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

【解説】

B⁺木（Bプラス木）は，データを効率的に格納・検索するために使用されるデータ構造であり，高さが均一に保たれるよう設計されています。検索に必要なアクセス回数のオーダーは，次の通りです。

1. B⁺木の高さは，データ総件数Xに対しておおよそ log X のオーダーとなります（実際にはlogの底はノードの分岐数ですが，オーダーとしてはlog Xで表現されます）。

2. 各ノードに格納されるデータは部分的に順序付けされており，必要なデータに辿り着くために，根から葉までの経路をたどります。

3. そのため，データ検索時のノードアクセス回数も log X に比例します。

各選択肢の評価

• ア: √X
  誤り。データ件数の平方根は，B⁺木の検索性能とは関係がありません。
• イ: log X
  正しい。B⁺木インデックスの検索性能は，データ総件数に対して対数的なオーダーとなります。
• ウ: X
  誤り。これは全件検索（線形検索）のオーダーであり，B⁺木を利用する場合の効率とは大きく異なります。
• エ: X!
  誤り。階乗は検索アルゴリズムの効率としては適用されません。