令和5年度 秋期 データベーススペシャリスト試験 午前Ⅱ 問4
テクノロジ／データベースB⁺木インデックスが定義されている候補キーを利用して，1 件のデータを検索するとき，データ総件数 X に対する B⁺木インデックスを格納するノードへのアクセス回数のオーダーはどれか。
出典：令和5年度 秋期 データベーススペシャリスト試験 午前Ⅱ 問4
- ア√X
- イlog X
- ウX
- エX!
正解：イ
解説
B⁺木インデックスは平衡多分木であり，各ノードが多数の枝をもつため木の高さは概ね log X（対数）のオーダーになります。候補キーによる 1 件検索では根から葉まで木の高さ分のノードをたどるだけで済むので，ノードへのアクセス回数のオーダーは O(log X) です。データ件数が増えても高さの伸びが緩やかである点が B⁺木の利点です。
選択肢ごとの解説
- ア誤り。√X のオーダーになるのは，データを √X 個ずつのブロックに分けて探索するような手法の場合です。
- イ正しい。B⁺木の高さは log X のオーダーであり，アクセス回数もそのオーダーになります。
- ウ誤り。X のオーダーになるのは，インデックスを使わず先頭から順に走査する全件探索の場合です。
- エ誤り。X! のオーダーになるのは，全順列を列挙するような組合せ的な処理の場合です。