Designing Data-Intensive Applicationsより、インデックスにまつわる箇所の読書ノートをまとめた。いくつか重要なデータ構造が登場しているが、個別の語彙やアルゴリズムについて深く検討まではしていない。概念を把握する前に、概念の存在をまずは認識した形である。詳細は詳細として、いつか必要が出たときに再訪する。
インデックスとは
n件のレコードから任意のレコードを検索するとき、基本的には O(n) の計算量が想定される。インデックスとは、その計算量を改善するに導入される補助的なデータ構造である。書き込みのたびにインデックスの更新も行わなければならないためインデックスを持つことは必然的に書き込みオーバーヘッドを伴う。
つまり次のようなシンプルなトレードオフとして整理できる。
- 優れたインデックスは読み取りを高速化する
- あらゆるインデックスは書き込みを低速化する
B-tree と LSM-tree
PostgreSQL や MySQL (InnoDB) においてインデックスというと、基本的には B-tree のことを指す。他方でトランザクションログのように大量に書き込まれるデータの扱いに長けた、 LSM-tree というデータ構造もある。
B-tree と LSM-tree はおおむね対照的な特性を持つ。簡単に列挙すると、次のようになる。
LSM-tree
pro
- 高い書き込みスループットを持つ
- 圧縮効率がよく、ディスクを効率的に利用できる
con
- ログをマージするバックグラウンド処理がパフォーマンスに影響を与える
- 平均的にはある程度均等なレスポンスタイムであるが
- 高いパーセンタイルほどレスポンスタイムが悪くなる
- データベースが大きくなるほどリソース効率が下がるリスクが高まる
- 書き込み流入量がバックグラウンド処理の速度を超えるとみるみるうちにディスクが溢れてしまう
- 書き込み量がボトルネックになる場合何らかの方法で外部から書き込みをスロットルする必要がある
B-Tree
pro
- トランザクションのための強力なロック性能を持つ
- 任意のキーはインデックス上で常にひとつしか存在しないことが保証されているため
- 時の審判を経ていくつもの改良も行われているからデータ構造としての信頼性はとても高い
con
- ページへの書き込み、ページ分割時の、変更ログの書き込みなどとかく書き込みコストが高い
- フラグメンテーションの問題がつきまとう
マルチカラムインデックスと R-tree
B-Tree と LSM-tree はいずれも単一のキーを値にマッピングするデータ構造であり、複数カラムを効率的にインデックスすることは苦手である。複数カラムを結合して単一のキーとして扱うことはできるが、結合順序に依存することは避けられない。これはつまり、電話帳の索引が姓→名の順で検索しやすくても、名→姓で引くことはできないようなものである。
経緯度データに代表される多次元データを効率よくインデックスするには R-tree のようなまた異なるデータ構造が利用される。
全文検索とあいまい検索
同意語、ミススペル、コロケーションなどを含めたファジーなインデックスを実現するには、また別のテクニックが要求される。 Elasticsearch のエンジンである Lucene は検索語句を入力として受け取り、 レーベンシュタイン距離 に基づいて検索を行う。 Lucene 自体が 有限オートマトン として動作するよう設計されているのである。
すべてをメモリに記憶する
ここまで扱ったトピックは、いずれもディスクに永続化されたデータを効率的に検索するためのものであった。メモリの生産コストが下がったことで、メモリ上で動作するストレージも登場してきている。
インメモリデータベースは伝統的なデータベースよりも速く動作するとされる。よくある誤謬であるが、これはディスクシークやI/Oが省略できるぶん高速であるというよりもむしろ、メモリとディスクの間でデータのエンコード/デコードが不要であるため高速化できているのである。
例えば redis は優先度付きキューやセットを実装しているように、インメモリデータベースはディスクデータベースでは不可能だったデータ構造も実現できる。またデータの読み書きはメモリ上で行いつつも、データの永続化のためにディスクへの書き出しもサポートするプロダクトも存在している。
今後、不揮発性メモリが一般化すれば大きくパラダイムが変わるから、それも見据えてアンテナを張り、思考することが要請される。