データ構造とアルゴリズム
データベースやファイルシステムの索引に、二分探索木ではなくB木(B+木を含む)がよく使われる主な理由はどれか。
- A1つの節に多数のキーを持たせて木を低くし、節を1回読むたびに範囲を大きく絞れるので、ディスクなどのブロックの読み出し回数を減らせるから
- B節ごとにキーを1つしか持たないので、比較の回数が二分探索木より少なくなるから
- C挿入しても形を整える必要がないので、実装が二分探索木より簡単だから
答えと解説を見る
正解：A. 1つの節に多数のキーを持たせて木を低くし、節を1回読むたびに範囲を大きく絞れるので、ディスクなどのブロックの読み出し回数を減らせるから
ディスクやSSDは、1バイトでも数KBのブロック単位で読むので、読み出しの回数を減らすことが大切です。B木は1つの節(1ブロック)に数百個のキーを持たせ、節を1回読むごとに数百通りに枝分かれできるので、例えば1億件でも高さ3〜4段で目的のデータに届きます。挿入や削除で節があふれたら分割し、少なくなったら併合して、すべての葉の深さを同じに保ちます。二分探索木では1億件なら少なくとも27段ほどになり、段ごとに別のブロックを読むと遅くなります。
- A. 正しい。枝分かれを多くして木を低くし、ブロックの読み出し回数を減らします。
- B. 1つの節に多数のキーを持つのがB木の特徴です。
- C. B木も節の分割や併合で形を整え、すべての葉の深さを同じに保ちます。