はじめに
第1回はデータベースの汎用性を実現する実装の全体像について見ていきました。データベースには膨大な量のデータから、クエリー言語で指定された条件のデータをごく短時間で返すことが求められます。巨大なデータの集合の中から条件に合致するデータの位置を特定するにはどのような実装が必要でしょうか。
そこで鍵となるのが、今回のテーマである索引です。索引は、データの位置を高速に特定するために最もよく使われている実装です。しかし、索引を作成することにはトレードオフがあります。索引があることで余計に処理時間が増加してしまう場合があります。また、1つのクエリーが1つまたはごく少数のデータにアクセスする場合と、大量のデータにアクセスする場合で最適なアルゴリズムとデータ構造は異なります。順を追ってみていきましょう。
なお、本連載で例として挙げるデータベースはオラクルが提供しているものが多いですが、オラクル製品を使っていない方にも参考にしていただけるように解説していきます。
対象読者
この連載では以下の読者を想定しています。
- データ資産を活用する、新しいアプリケーションの構想や設計を担われる方
- データ基盤の運用を担われている方や、今後検討される方
- 新たに開発するアプリケーションの、最適なデータベースをお探しの方
- 目的別データベースから、価値ある情報を素早く引き出す検討をされている方
索引（インデックス）
ある値がデータベースのどこに存在するかを短時間で特定するのに使用されている実装が索引（インデックス）です。その基本的なアイデアは物理的な書籍の索引と同様で、データの値とデータ本体へのポインタの組です。たとえばリレーショナル・モデルではデータの本体は表という形式ですが、索引は列の値とその値を持っている行アドレスへのポインタの組です。
索引は表の特定の列を指定して作成します。すると、索引はその列の全行の値を持っている写像になります。クエリーがある値を指定して検索をかけた時、索引が保持する値の中からクエリーに合致する値を特定するために索引ブロックを全件探索するわけではありません。実は、索引の実装にはさまざまな派生形があり[*1]、少ないアクセスで特定できます。表や索引はストレージ上ではデータ・ブロックやページと呼ばれる複数の行が入った単位に分割されて格納されており、一般的には4KBや8KBといったサイズが使われます。クエリーの処理時間は何ブロックにアクセスしたかと大きな相関があります。1行を特定するのに、表ブロックを全て探索するよりも索引ブロックをたどって表ブロックにアクセスするほうがはるかに小さな回数のアクセスですみます。これが索引による処理時間短縮の効果であり、データベースのチューニングで索引が検討される場合が多い理由でもあります。
[*1] 索引のデータ構造は平衡木（Oracle DatabaseのB*-Tree）やハッシュ・バケット（Oracle TimesTenのハッシュ索引）などになっており、線形O(N)よりもはるかに小さなオーダーの計算量であるO(logN)やO(1)で値を特定できます。
