動機
この記事はインデックスの仕組みについての内容になります。
普段アプリケーションエンジニアとして、テーブルの設計やインデックスを追加したりはしていますが、パフォーマンス上効率よく利用できるように改めて仕組みから自分の理解を整理することにしました。
それなりに詳しい方からすると基本的な内容ですが、一旦自分の認識を共有することでフィードバックがもらえればと思っています。
今回は、主に以下のような方を対象に書いています。
- なぜインデックスがレコードの取得に利用されているか理解したい
- B Treeがインデックスにどう応用されているのか理解したい
- インデックスが効かないパターン（インデックス列への否定の条件は効かないなど）をただ暗記しているだけになっている
Disk-Based DBMSの特徴
Database management system（DBMS）は、外部から送信されたクエリを元に記憶装置に蓄えられたデータに参照、更新などの操作をするミドルウェアです。
具体的なアーキテクチャについてはここでは触れません。
DBMSは、主なデータをRAM（random access memory）上に保持するもの（In-memory DBMS）と、磁気ディスク（以下、単にディスクと呼びます）上に保持するもの（Disk-based DBMS）に分類されます。
In-memory DBMSはRAM上にほとんどのデータを保持し、ログや復旧用のデータをディスクに保持します。
RAMはディスクよりもアクセスに要する時間が少なく済むのに対して、ビット当たりの価格が高いです。また揮発性、つまり電気の供給が停止するとデータが失われるという性質を持つ記憶媒体です。
もちろん、予備電源やディスクへのバックアップなどでデータを保持する仕組みはありますが、ディスクの方が耐久性があるので、コストの観点も含めて大量のデータを保持する場合はDisk-based DBMSが用いられます。
ディスクの構造
記憶媒体としてのディスクは、プラッタと呼ばれる円盤状の磁性媒体上に記憶をします。
そして、プラッタは、トラックというプラッタ面上の同心円状の領域で論理的に分割されており、さらに中心から放射線上にセクタ（512バイト程度）という領域に分割されます。
また、同一半径にある各プラッタ面のトラックの集合はシリンダと呼ばれます。
通常、数枚のプラッタが中心の軸の周りを高速で回転し、各面に対してアームに付属しているヘッドが読み書きを行います。具体的には、以下の手順で指定のアドレスから連続したセクタが読み取られます。
- アームを移動してヘッドを該当するセクタの所属するトラックに位置付ける
- 先頭セクタが回転してヘッドの下に来るのを待つ
- 先頭セクタから始まる指定された数のセクタを読み、その内容を主記憶へ移動する
手順1の時間をシーク時間、2の時間を回転待ち時間、3の時間を転送時間と呼びます。
通常、ディスクは毎分5400~15000回転（RPM: rotations per minute）し、7200PRMの場合は、一回転に8.33ミリ秒が必要になります。1
また、平均回転待ち時間はディスクの半回転分となります。例えば、シーク時間が7200RPMの場合は、0.5回転/7200RPM = 4.1ミリ秒くらいになります。
一方で、主記憶として使われるダイナミックRAM（DRAM）は2012年時点では35ナノ秒前後でアクセスできるので、6桁も遅いことになります。2
オペレーティングシステムによる抽象化
ディスクを使ったデバイスは、データを読み取る位置を指定し連続したいくつかのセクタをまとめたブロックという単位でデータにアクセスするため、ブロックデバイスと呼ばれます。したがって、ブロックデバイスからあるデータを読み取った時にはそれを含むブロック全体が既に読み取られていることになります。
そして、オペレーティングシステムは、ブロックデバイスごとの差異を抽象化してファイルに対するopen, read, writeなどのシステムコールを使えるようにします。3
それを実現するには、デバイスドライバがブロックデバイスごとの振る舞いを抽象化したインターフェースをファイルシステムに提供します。
また、上述のようにディスクは機械的な動作をデータの転送に要し、速度は主記憶よりもかなり遅くなるので、できるだけ少ない回数で必要最低限のブロックでデータにアクセスすることが重要になります。
インデックスの役割と構成
概要
データベースシステムは複数のフィールド値を持ったレコードをテーブルの中で保存します。
そして、できるだけ少ない回数で、テーブル全てを探索しなくて対象のレコードにアクセスできるようにするために、インデックスを利用します。ここのインデックスの説明は、こちらの資料を主に参考にしました。
インデックスは、レコードのいくつかのフィールド値を表すキーと、その位置を特定するためのポインタ（そのレコードがあるブロックの先頭の位置など）を持ちます。
そしてインデックスファイルはインデックスを含んだファイルで、データファイルはレコードを保持しています。
したがって、あるキーを持つレコードの探索は、インデックスを探索して、そのキーとそれと対応するレコードへのポインタを見つけ、データファイルの中にある対象のレコードを特定します。
インデックスとレコードの関係
インデックスファイルにおけるインデックスの並び順とレコードとの対応関係にはいくつか種類があります。
まず、インデックスがレコードごとに対応しているものをdense index、レコードが含まれるブロック（の先頭など）へ対応しているものをsparse indexと呼びます。
dense indexはレコードごとにインデックスを用意する必要があるので、その分インデックスファイルが大きくなりまが、探索を早くできます。
一方で、sparse indexはブロックを代表する値をキーにして一つのインデックスを構成するので、その分インデックスファイルは小さくすみます。しかし、ブロックを特定してからさらにそのブロック内で対象のキーを持つレコードがあるか探索する必要があります。
プライマリーインデックス
プライマリーインデックスは、以下の条件を満たすインデックスです。
- インデックスのキーの順番にレコードも並んでいる
- 全てのレコードが固有のキーを持っている
A primary index is an index specified on the ordering key field of a sorted file of records. If the records are sorted not on the key field but on a non-key field, an index can still be built that is called a clustering index. The difference lies in the fact that different records have different values in the key field, but for a non-key field, some records may share the same value.
プライマリーインデックスが、sparse indexの場合は、対象のキー（K）を持つレコードを探すために、K(i) <= K < K(i+1)となるようなi番目のインデックスのキーK(i)に対応するポインターP(i)からブロックを特定することができます。これは、キーの順番でレコードが並んでいるのでキーの値の範囲から特定できるためです。
クラスタリングインデックス
レコードごとに固有でない値つまり複数のレコードで共有される値を持つキーで、レコードが並べられているインデックスをクラスタリングインデックスといいます。
If records of a file are physically ordered on a non-key field which may not have a unique value for each record, that field is called the clustering field. Based on the clustering field values, a clustering index can be built to speed up retrieval of records that have the same value for the clustering field.
クラスタリングインデックスは、同じ値のキーを持つレコードのまとまりの最初のレコードなどを指します。
実装上は、レコードの並び替えにかかるコストを下げるために、ブロックあたりに一つの値のレコードを配置し、sparse indexのような対応関係にすることもできます。
セカンダリーインデックス
レコードは何かしらの順番で並べられているので、少なくとも一つのプライマリーインデックスかクラスタリングインデックスを持つことになります。その順番を決めるキー以外のインデックスがセカンダリーインデックスになります。
つまり、セカンダリーインデックスは、レコードを並べていないキーを持つインデックスです。
その場合は、ブロックごとに同じキーを持つレコードがまとまっていないのでdense indexになります。
同じ値のキーが複数のレコードで共有されている場合のために、主に以下の二つのインデックスからのレコードの参照の仕方があります。
- 同じ値のキーだがそれぞれ異なるレコードを参照するポインタを持つインデックスを複数用意する
- 同じキーを持つレコードへのポインタの配列へのポインタとキーを持つインデックスをそれぞれのキーごとに用意する
また、直接レコードを参照するのではなく対応するプライマリーインデックスを参照して、そこから間接的にレコードを参照する方法もあります。そうすることで、経由する分ディスクへのアクセス回数は増えますがレコードのポインタが更新された時にセカンダリーインデックスの更新を避けることができます。
どうやらMySQLのInnoDBではこの方式のようです。
クラスタ化されたインデックス以外のインデックスは、すべてセカンダリインデックスと呼ばれます。
InnoDB では、セカンダリインデックス内の各レコードに、行の主キーカラム、およびセカンダリインデックスに指定されたカラムが含まれます。InnoDB では、クラスタ化されたインデックス内で行を検索する際に、この主キー値が使用されます。
これらのようにセカンダリーインデックスは、dense indexなのでsparse indexと比べてインデックスの数は大きくなり、同じ値のキーを持つレコードがある分さらに複数のブロックにアクセスする必要があります。
なのでプライマリーインデックスと比べて探索により時間がかかります。
マルチレベルインデックス
インデックスを利用することでレコードを取得するためのディスクへのアクセスに必要な回数を減らせることはわかりましたが、インデックスファイル自体もディスクに保存する必要があります。レコードが大きくなればその分インデックスも大きくなるので一つのブロックやメモリ上に収まり切らなくなります。
それを解決するために、インデックスへのインデックスのような木構造を利用して、ブロックに占めるインデックスのまとまり（節）からできるだけ少ない回数で目的のインデックスをディスクから見つけるようにします。この木構造の構築は、子を持つ節がただ一つになるまで続けられます。このようなインデックスをマルチレベルインデックス（multilevel indexes）と呼びます。4
B+Treeのインデックスへの利用
マルチレベルインデックスには、BTreeの改良版のB+Treeが利用されています。
BTree自体は多くの書籍や記事で説明されているので、ここでの説明は簡単に済まします。
インデックスへのBTreeの応用に関しては、Database Internalsが大変参考になりました。
B+Treeは以下の特徴を持ちます。
- 全ての葉までの深さは同じで、木の高さは一定
- 根は木が空でなければ少なくとも1つのキーを持つ
- 内部節はキーと子へのポインタをそれぞれN~2N, N+1~2N+1個持つ
- 内部節のキーは昇順にソートされている
- キーK1とK2の間にあるポインタが指す子の部分木の任意のキーKはK1 <= K < K2
- 葉はキーと値（レコードまたはそれへのポインタ）を持つ
また範囲検索に対応するために、葉は昇順に連結されることもあります。
なぜB+Treeがマルチレベルインデックスとして利用されることが多いのかというと、主に以下の理由があるからです。5
- 平衡木（各部分木同士の高さの差が1以下）である
- ファンアウトが大きいので高さが小さくなる
- ファンアウトが大きいので一つの節（つまり連続したブロック）に複数のキーとポインタを格納できる
平衡木でないと、Binary Search Treeのように挿入の順序によっては線形に探索する必要が生じます。つまり計算量がO(N)になります。B+Treeはバランスするように常に調整されているのでそういった場合を避けることができます。
また、節が参照する子の数をファンアウト（fan-out）と呼びます。
ファンアウトが大きいと、階層を経るごとに節の数が増えるので高さが小さくなります。
根は少なくとも2個の子を持ち、次の深さ（深さ2）ではその2個の節がそれぞれ少なくともN+1個の子を持ち、次の深さ（深さ3）ではその2*(N+1)個の節がそれぞれ少なくともN+1個の子を持つといった具合で、深さhでは、少なくとも2*(N+1)^(h-1)個の子を持つことになります。そして、高さが低くなると、その分探索の計算量も減ります。
さらに、一つの節は複数のブロックで構成されており、そこに複数のキーとポインタを格納できるので、キーを辿るたびに何度もディスクへアクセスすることを避けられます。
B+Treeの節の構成
B+Treeの節は複数の連続するブロックをまとめたPageという単位で扱われます。
内部節のPageにはキーとポインタの組み合わせが保持され、葉にはキーとレコード（またはそれへのポインタ）が保持されることになります。
複数の可変長のレコードをブロックに収めるには、それぞれのブロックにおける開始の位置（オフセット）とサイズを管理する必要になります。
それを実現するために、Slotted Pageという手法があります。これはPageをHeader, Pointerの配列, Cellの配列の構成に分けます。Cellの配列にはレコードがPageの右端から左へ追加されたもので、Pointerの配列でそれぞれのレコードへの参照を保持します。Header, Pointerは左端に位置するので、空きスペースはPointerの配列とCellの配列の間になります。6
B+Treeの場合、Page内のレコードはキー順に並ぶ必要がありますが、この仕組みを利用することでPointerを並び替えるだけで、実際のレコードは空きスペースに順次追加するだけで済みます。
内部節はキーと子へのポインタを持つのでCellはポインタになります。その場合、キーとポインタが1対1の関係になりますが、K個のキーとK+1個のポインタを持つので、実装上は最後のK+1個目のポインタに対応するようにK+1個目のキーを用意したり、特別にそのポインタだけを管理したりします。
余談
今回の記事を書くにあたって改めてBTreeについて復習しました。
以前学んだ時はただの一つのアルゴリズムという認識だったのですが、改めてインデックスに利用されていることを意識すると以下のようなルールに納得感を持つことができてよかったです。
- レコードの変更に応じてインデックスを更新するコストがかかる（だから無駄なインデックスは作るべきではない）
- 選択率の高い列にインデックスを付ける
- インデックス列に否定（
<>など）の条件を使っても効かない - インデックス列に直接演算（
where col_1 * 1.1 > 100など）を行うと効かない - インデックス列に前方一致以外のLIKE句を使っても効かない
- 複合インデックスはそのプレフィックスのインデックスを兼ねる
- 複合インデックスは選択率の高い順に指定する
またデータベースの仕組みを調べるとデータ構造とアルゴリズムやOSへの理解が問われ、改めて基礎の大切さを実感しました。