この記事は
インデックス自体の構造について、そしてインデックスをどのようなデータ構造で保有していくかについてまとめていこうと思う。
図を描くスキルがなかったのでテキストオンリーです。
インデックス自体の構造体
後述するが、本章は一般的なB+Treeを用いているとする。
クラスター化インデックス
プライマリキーによるB+Treeのリーフノードに実データが含まれる。
データは「タプル単位でまるごと+メタ情報」というのが多そう。
プライマリキー値によるソートが掛かった状態で検索が行われるので、検索が高速であることが利点。
加えてリーフノードには実データが収められていることから、一次検索でデータのフェッチまで完了するのが魅力。
innoDBやSQL-Server等多くのRDBで採用されているインデックス構造。
非クラスター化インデックス
セカンダリインデックスとも呼ばれる。
任意のインデックスキーのリーフノードに二次検索用のハンドラが収められている。
このハンドラには下記のようなパターンがある。
- プライマリキー値
- レコード場所情報（ファイルid、ページ番号、ページ内行番号）
- ヒープに対するポインター
複合インデックス
非クラスター化インデックスと同様の概念。
複数のインデックスキー値によるB+Treeであることが差異である。
リーフノードには同様に二次検索用のハンドラが収まる。
B+Tree自体は最初のインデックスキーに基づいて構築されるので、複合インデックスを使った検索を行うためには最初のインデックスキーを検索条件に含める必要がある。
カバリングインデックス
複合インデックスの亜種にあたる。
複数のインデックスキー値によるB+Treeであることは同様だが、リーフノードに収まるのは（対象カラムの）実データである。
実際に利用するのが一部のカラムだけなら、あらかじめインデックスに実値として持たせることで、二次検索を発生させないというアイデア。
じゃあどうやって上記のようなインデックスを保有するの？
基本的にインデックスについてググると上記のような情報が真っ先に出てくるわけだが、ほとんどの説明がB+Treeを前提としている。主要なRDBがB+Treeを採用しているからであろうが。
しかし実際にはB+Tree以外の構造を利用しているRDBも存在しているわけで、そこら辺も調べてみた。
B+Tree
大人気B+Tree。
リーフノードが1レコードに対応しているものもあれば、複数のレコードを含むページに対応しているものも有る。ここらへんは各プロダクトによりまちまちっぽいが、大半はページを返して、線形サーチしていくのが一般的かと。
等値検索・シーケンシャル検索にも対応しており、性能も悪くないので人気っぽい。
ハッシュテーブル
大規模データに対応できる質の高いhasherがあれば一次検索で実データにたどり着ける。
あくまでhasherに依存するが、データ量が増えても理論上性能劣化しない。
ただし等値検索にしか対応できないため、あまり採用されない。
はずだが、RDBのバックエンドにKVストアを使ってるやつとかも有るので、何か進化があるのかもしれない。
範囲表
実表をチャンクという単位で区切り、各チャンクを更にセグメントという単位で区切っていく。
インデックスされる実データをソートして、各セグメントに割り振り、各セグメントは各チャンクに割り振られることになる。
チャンクとセグメントはメタ情報としてインデックスされる実データの最小値と最大値を保有する。
一次検索ではチャンクを舐めて、該当するチャンク内のセグメントを舐めて、その後実表の対応箇所を舐めるというアイデア。
シーケンシャル検索には向きそうだが、B+Treeでいい気もする。
性能がどれくらい変わるのか調べてみたい。
感想
基本的に計算量の話でしか無いことが実感できてよかった。
計算量の最適化が図られていればデータ構造はなんでもいいっぽいので、上記例が絶対というわけではなさそう。