平成28年度 秋期 午前 問27

✓ これが正解イlogX

解説

たどる回数は木の高さで、件数の対数で増えます。

設問は、B+木インデックスが定義されている候補キーで 1 件を検索するときの、ノードへのアクセス回数のオーダを答えさせています。たどる回数は木の高さと同じなので、総件数 X を収めるのに何段必要かを数えれば足ります。一つのノードから枝が n 本出るとすると、高さ 1 では n 件、高さ 2 では n の 2 乗、高さ h では n の h 乗の件数まで届きます。つまり n の h 乗が X 以上になる最小の h が求める回数で、これが log X という形です。枝が 100 本なら、高さ 3 で 100 万件に届きます。件数が 100 倍になっても、たどる回数は 1 回増えるだけです。候補キーなので目的の 1 件は必ず一か所に決まり、葉まで下りればそこで終わります。オーダを問われたときは、係数や対数の底は答えに必要ありません。増え方の形だけを見ます。

ほかの選択肢はなぜ違うのか

• ア√X：平方根の形は、区画に分けた索引をたどるときなどに現れる増え方です。木の段数はこれよりずっとゆっくりしか伸びないので、B+木の高さを表す式にはなりません。
• ウX：先頭から順に全件を見ていくときの回数です。件数にそのまま比例して増えるので、索引を用意した意味がなくなってしまいます。
• エX!：すべての並べ方を数え上げるときに現れる式で、増え方が桁違いに激しくなります。1 件を見つけ出す手間を表すものではありません。