修了試験 2017-12-10実施分 基本情報技術者試験 問27

解説

正解は2です。 B^+木は、データが格納された葉までの深さがすべて等しい平衡木で、1つの節に多数のキーと枝をもちます。 検索は根から葉に向かって1段ずつ節をたどるので、アクセス回数は木の高さに比例します。 木の高さはデータ件数Xの対数に比例するので、アクセス回数のオーダはlogXです。 【選択肢別解説】 1：× √Xは、データを√X個ずつのグループに分けて探す方法などで現れるオーダです。 B^+木の検索はこれより少ない回数で済みます。 2：○ B^+木は平衡木なので、高さはlogXに比例します。 1件の検索で根から葉までたどる節の数もlogXのオーダになります。 3：× Xは、データを先頭から順に調べる線形探索のオーダです。 インデックスを使わない全件走査に相当します。 4：× X!は、全ての並べ方を調べるような場合に現れる、非常に大きなオーダです。 検索のアクセス回数としては当てはまりません。 【ポイント】 1つの節がm本の枝をもつ木では、高さはおよそlog_mXになります。 B^+木はmが大きいので木が低く、ディスクへのアクセス回数を少なく抑えられます。