平成28年度 秋期 応用情報技術者 問27

正解 イ

B+木は常に平衡した多分木なので、根から葉までの段数はデータ件数の対数に比例し、アクセス回数はlogXのオーダです。

B+木は、各ノードが多数の子をもつ平衡木です。挿入や削除のたびに平衡が保たれるので、根から葉までの深さはどの葉でも同じです。1ノードの子の数をmとすると、木の高さはおよそlogmXになります。1件の検索では根から葉まで1段に1ノードずつたどるので、アクセス回数はlogXのオーダです。

ア：√Xは、データを√X個ずつのブロックに分けて探すような方法のオーダです。B+木の段数は対数で増えるので、√Xにはなりません。

ウ：Xのオーダは、インデックスを使わずに先頭から順に調べる線形探索の場合です。

エ：X!は、全ての並べ方を調べる場合などに現れるオーダです。1件の検索でこれほど増えることはありません。

出典：平成28年度 秋期 応用情報技術者試験 問27