読者です 読者をやめる 読者になる 読者になる

by shigemk2

当面は技術的なことしか書かない

インデックスで高速アクセスを実現する

読書ノート

DBへの高速アクセスを実現するキーとなるのがインデックスである。

全件検索は大量データに向かない

1件1件虱潰しにデータを検索していく方法は線形検索と呼ばれ、
検索にかかる時間は文書のサイズに比例する(O(N)の計算量)

ユーザ情報を固定長で管理する

各データを100バイトだかで区切って管理すれば、100バイト目、200バイト目…でうまく検索できそうではある。

しかし、

  • 100バイトで区切ってすべてのデータが収まるのか
  • 各データが100バイトを越えないようチェックしないといけない
  • 余分なデータが大量に発生する

というデメリットがあるのでこれもしんどい。

インデックス構造を導入する

インデックスとは「各ユーザIDごとにファイル上の開始位置を記録したファイル」のこと。10万3000くらいの魔導書を記憶してる某シスターではない。

インデックス→ユーザ管理情報ファイルの順にアクセスしないといけないから2段階のアクセスが必要になる欠点はあるが、
検索が劇的に早くなる。

ハッシュインデックス

インデックスは「キー値、バイト位置」だけでは、日付、文字列などのさまざまデータ型に対応できない。
そのため、実際のデータベースにおける実装では、キー値をそのまま管理するのではなく、キー値をハッシュ関数にかけて
そのハッシュ値と値のペアを持つ、という構造が好んで使われる。

これをハッシュインデックスという。(理論上の計算量はO(1))

しかし、異なるキー値なのにハッシュ値が同じになったというケースが出てくる。これを「ハッシュの衝突」という。
また、ハッシュインデックスでは、範囲検索やソートには対応しづらい。

B+Treeインデックス

B-Tree インデックス - オラクル・Oracleをマスターするための基本と仕組み

木構造になったインデックスで、ルートブロック、ブランチブロックで大まかなIDを格納して
篩い分けし、リーフブロックから実際のIDを取得するアルゴリズム。

二分木と違いこちらは多分木と呼ばれ、
枝分かれ本数を多くすることで階層の段数を減らしてアクセス回数を少なくする。

RDBMSにおける事実上の標準となっている。

RDBMSではどのように最適化を実現してるのか

  • 一意性の保証
  • マルチカラムインデックス (ユーザIDと最終更新日の両方で絞り込む、など)
  • インデックスだけを読む検索
  • インデックスマージ 1回の検索で2個以上のインデックスを同時に使い、それぞれの結果から対象のレコードを取り出す

更新コスト削減のために

インデックスの欠点として、検索性能が上がる反面更新性能が落ちるというデメリットがある。

そこで、更新された情報をメモリや専用ファイルなどに一時的に記録しておいて、
あとでまとめて一気にリーフブロックを更新する方法がある。この方法を取っているDBがMySQL(InnoDB)である。

ランダムアクセスは遅い

データベースでは耐障害性を確保するために更新したデータをディスクに書かなえればならない。
またメモリに収まらない規模のデータを扱うことがほとんどでメモリに載っていないデータを読むためには
ディスクからの読み込みが発生する。これらはランダムアクセスになる。

まとめ

インデックスは検索速度を速くするが、データを余計に持つためデータサイズが増えるし、
インデックスを更新するために余計な処理が必要になる。

遮二無二インデックスをつけても意味がないので、事前の設計が必要になる。