なんでデータベースには B-tree が使われてるの？

ディスクベース(Disk-oriented)のデータベースのほとんどでは、多くの場合ストレージ構造として B-tree が採用されています。単純な二分探索木ではなくより複雑な B-tree が採用されるのは、なぜなのでしょうか？

それは、B-tree とハードディスクの物理的特性との相性が良いためです。

ハードディスクの特性

ハードディスクはデータの読み書き時に磁気ヘッドの移動・ディスクの回転という物理パーツの機械的な駆動を伴うため、散らばったデータに対するアクセス(ランダムアクセス)が非常に遅いという特性を持ちます。逆に言えば、連続したバイト列に順番にアクセスするシーケンシャルアクセスに関しては比較的高速です。

ハードディスクはセクタと呼ばれる 512B ~ 4kB の比較的大きな単位でデータの読み書きを行います。これは、バイト単位でのアクセスを試みるとヘッドが非常に細かい動きを繰り返すことになり、非効率なためです。ちなみに、誤り訂正もセクタ単位で行われます。

なお、ファイルシステム上ではセクタではなく、ブロックと呼ばれる単位でデータの読み書きを行います。ブロックの大きさはファイルシステムや設定によってまちまちのようですが、4kB が採用されることが多い¹ようです。セクタが物理的な最小転送単位だとしたら、ブロックは仮想的な最小単位です。

ハードディスクについて取り上げましたが、実は多くの OS でストレージデバイスの内部的なディスク構造は抽象化されています。そのため、多くの場合 SSD なども HDD 以外のストレージデバイスについてもバイト単位ではなくブロック単位で I/O が行われます。

ややこしいですが要するに、あちこち見て回ると遅い構造になってるので、一度にエイヤと多めにデータを読み書きする仕組みになっています。

B-tree はこのようなディスクの特性に最適化されたデータ構造になっていて、高速にデータを読み書きすることができます。

二分探索木を採用した場合を考えてみる

二分探索木をストレージ構造として採用し、ディスク上に保持した場合を考えてみます。すると、いくつかの問題に直面します。

第一に、ノードがランダムな順序で挿入されることです。

例えば、生年月日をキーとして社員の情報を二分探索木に格納したとします。この二分探索木から、1997 年生まれの社員を全員取得する場合を考えます。

1997 年 1 月 1 日生まれの佐藤さんの次に 1997 年 1 月 2 日生まれの鈴木くんが登録されているとして、二分探索木では、この二人が同じブロックに格納されている保証はどこにもありません。値が隣接しているデータに順番にアクセスしたいですが、ディスク上に散らばったデータひとつひとつにいちいちアクセスする必要があります。その度にディスクのシークが必要になってしまい、非常に非効率です。

第二に、ツリーが高くなってしまうことです。

二分探索木で許容される子の最大数(ファンアウト)は 2 のため、検索対象のノードにたどり着くためには O(log2N)回の比較が必要となります。比較のたびにディスクのシークが走るため、木が高ければ高いほど、時間がかかる上、セクタ上にある無駄なデータを読み込むことになってしまいます。

B-tree だとどうなるの

DB を自作しようとして調べた中でへーって思ったのでまとめました

基礎的な話だと思うけどぜんぜん知らんかった