Database Index (インデックス)

Tags:

インデックス(index)とは

  • テーブルに対する動作速度を高めるデータ構造を指す。
  • インデックスは、テーブル内の 1 つのカラム、または複数のカラムを使って作成できる。
  • 高速な検索動作だけでなく、レコードアクセスに関連する効率的な並び順付けの基盤も提供する。
  • インデックスとは、追加の書き込み処理と保存領域を利用して、データベーステーブルの検索速度を向上させるためのデータ構造である。
  • もし本の中で目的の内容を探すとしたら、本のすべてのページを探すには長い時間がかかる。そのため本の著者は本の先頭または末尾に索引を追加するが、データベースの index は本の索引と同じである。
  • データベースでも、テーブルのすべてのデータを検索すると時間がかかるため、データとデータの位置を含むデータ構造を作成し、高速に照会できるようにしている。
  • index を適用していないカラムを照会すると、全体を探索する Full Scan が実行される。Full Scan は全体を比較しながら探索するため速度が低下する。

データベースでデータを検索する 2 つの方法

  • FTS(Full Table Scan)
    • テーブルを最初から最後まで検索する方法である。
  • Index Scan
    • インデックスを検索し、該当データのテーブルへアクセスする方法である。

インデックスのデータ構造

  • ハッシュテーブル

    • カラム値から生成されたハッシュを基にインデックスを実装する。
    • 時間計算量が O(1) であるため検索が非常に速い。
    • 不等号（<, >）のような連続データに対する順次検索はできない。

  • B+Tree

    • 子ノードが 2 つ以上ある B-Tree を改善したデータ構造である。
    • BTree のリーフノードを LinkedList で接続し、順次検索を容易にした。
    • ハッシュテーブルより悪い O(log2n) の時間計算量を持つが、ハッシュテーブルより一般的に使用される。