RDBMSのインデックスは磁気ディスク前提で考えられている

PostgreSQLやMySQLでは、インデックスを適切に設定する事で、検索速度を大幅に向上させる事ができます。
というよりも、インデックス設定が不適切だと大量のデータの検索が重すぎて使い物にならない場合すらあります。

では、インデックスを使うと検索が早くなるのは何故でしょうか？
それは、インデックスデータが「検索を前提としたデータ構造になっているから」です。

id	値
1	5
2	3
3	10
4	8

このようにランダムに並んだデータから、例えば値が10のレコードを引っ張ってくる場合、
インデックスがなければ、上から順に一つづつ全件調べていくことになります。
件数が少ない場合はすぐに処理が終わりますが、これが数百、数千と増えていくと、処理時間も単純に正比例で伸びていきます。

では、これを素早く検索するためにはどうすればよいか？
回答の一つは、「あらかじめ順序良く並べておく事」です。

id	値
2	3
1	5
4	8
3	10

このようにしておけば、二分検索等の高速なアルゴリズムを用いて検索する事ができます。

しかし、データベースの実装においては、この方法を単純に導入するのは現実的ではありません。
なぜなら、レコードを挿入するときに、例えば7という値を挿入したとすると、8以上のデータを全て後ろにずらす必要があり、データ容量が大きい場合、一つデータを挿入する度に、磁気ディスク上をデータが大移動するはめになり、途轍もなく処理に時間がかかる事でしょう。

そこで考案されたアルゴリズムが、B+木と呼ばれるものです。
これは、平衡木の一種です。平衡が保たれた木は、原理的には、データの中央から対象を探索していくという、二分検索と同様の性質を持つはずです。
平衡木は、他に赤黒木、AVL木等、いくつかのバリエーションがありますが、
B+木は、インデックスセグメントをブロック単位で分割する事で、特にディスクの回転によるシーク時間が速度に直結する磁気ディスクにデータを保存する場合に、相性の良いアルゴリズムとして考案されたもののようです。

イメージ的には、末端（葉）はブロック単位でソートされた値を持ち、単純な二分木では無い複数の枝を持つ木構造ででブロックを繋げ、仮想的に一元的にソート済みにしたデータ構造であり、シーケンシャルなアクセスと検索性能を両立したデータ構造、という感じでしょうか。（知らんけど）

しかし、現代の外部記憶装置はSSDが完全に主流となり、ディスクの物理的な回転によるシーク時間というのを考慮する必要はないため、それに特化したアルゴリズムであるB+木を採用する必要もないと考えられます。

また、最近ではメモリ容量も昔に比べて遥かに大容量になったため、インメモリで動作するデータベースもあるようです。

そうなってくると、もはやランダムアクセスである事がボトルネックにはならないと考えられるため、AVL木や赤黒木のような単純な二分木の方が速度的に有利になる可能性があります。

そこで、rustでAVL木（の独自カスタマイズ版）をクレートを作り、公開してみました。
https://crates.io/crates/avltriee

次回、当クレートの機能について紹介してみたいと思います。

（続く）