令和5年度 秋期 午前Ⅱ 問4

✓ これが正解イlog X

解説

B+木の検索で触るノード数は木の高さに比例し、log X のオーダーです。

B+木は、各ノードが多数のキーとポインタを持つ平衡木で、根から葉までの段数がどの葉でも同じになるように保たれます。1件を検索するときは根から葉まで1段ずつたどるので、アクセスするノード数は木の高さに比例します。1ノードあたりの分岐数を m とすると、高さは件数 X に対しておよそ log_m X で増えるので、オーダーは log X です。たとえば分岐数が100なら、100万件でも3段か4段程度で葉に届きます。見分ける軸は、件数が増えたときに段数がどう伸びるかです。平衡木の探索は対数オーダーと覚えておくと、件数そのものに比例する値などを外せます。

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

• ア√X：√X は、件数の平方根に比例して手間が増えることを表します。データを平方根個ずつのかたまりに分けて探すような方法の手間であり、平衡木を根から葉まで1段ずつたどる B+木の検索とは増え方が違います。
• ウX：X は、件数に比例して手間が増えることを表し、データを先頭から一件ずつ調べる線形探索の手間に当たります。インデックスを使わずに全件を走査するときの増え方であり、B+木で1件を探す場合には当たりません。
• エX!：X! は件数の階乗で、並べ方をすべて試すような処理で現れる、極端に急な増え方です。B+木の検索は根から葉までの段数だけノードをたどるので、このような増え方にはなりません。