Index Theory

データベースのインデックスは奥が深い。深すぎて、たまに底が見えない。

B-treeは定番だ。ほとんどのRDBMSがデフォルトで使う。バランスの取れた木構造で、範囲検索にも等価検索にも効く。万能選手だが、万能ゆえに最適ではない場面も多い。

Bitmapインデックスは毛色が違う。カーディナリティの低いカラム、たとえば性別や都道府県のような値の種類が少ないカラムに効く。ビット演算でAND/ORを高速に処理できる。OLAPには最高だが、更新が多いOLTPには向かない。ロックの粒度が粗くて、同時書き込みで死ぬ。

そしてこのBitmapインデックス、Oracleが特許を持っていた時期がある。PostgreSQLやMySQLが同じ実装をできなかった理由のひとつだ。技術的にできないのではなく、法的にできなかった。データベースの実装差異は、アルゴリズムの優劣だけでは語れない。

ファンクションインデックスもOracleが先行した機能だ。UPPER(name) のような式に対してインデックスを貼れる。PostgreSQLは後追いで実装したが、MySQLは長らく対応せず、Generated Columnという迂回路を用意した。同じ課題に対して、アプローチがまるで違う。

転置インデックスは全文検索の世界だ。わたしがMygramDBを作ったのもこの領域で、MySQLのFULLTEXTインデックスがあまりにも遅かったからだ。B-treeで全文検索をやろうとするのは、フォークでスープを飲むようなものだ。道具が違う。

結局のところ、インデックスの選択はトレードオフだ。読み取り速度、書き込みコスト、ストレージ容量、ロックの粒度。何を優先するかでベストな選択は変わる。そしてどのRDBMSを使っているかで、選択肢そのものが変わる。同じテーブルについているのに、カトラリーが違う。