B+木インデックスが定義されている候補キーを利用して，1件のデータを検索するとき，データ総件数Xに対するB+木インデックスを格納するノードへのアクセス回数のオーダを表す式はどれか。
正答2
解説
正解は2です。
B+木は、すべてのデータへのポインタを葉に持ち、根から葉までの高さが常にそろう平衡木です。
1件の検索では、根から葉まで1段ずつたどるので、アクセス回数は木の高さに比例します。
【選択肢別解説】
1：× sqrt(X)は、データを√X個ずつのブロックに分けて探す方法などのオーダです。
B+木の探索の回数ではありません。
2：○ 1節点からm本の枝が出るとき、木の高さはおよそlog_m Xになります。
対数の底は定数倍の違いにすぎないので、オーダはlogXです。
3：× Xは、先頭から順に調べる線形探索のオーダです。
インデックスを使わない全件検索に当たります。
4：× X!は、全要素の並べ方を調べるような処理のオーダです。
検索の回数としては極端に大きく、該当しません。
【ポイント】
B+木インデックスは、データ件数が10倍になっても、アクセス回数は少し増えるだけです。
範囲検索では、葉同士をつなぐポインタをたどれる点もB+木の特徴です。