by Hayato Matsuura.

SQLインデックスの内部構造


「インデックスはクエリの実行を速くする」 とは、インデックスに関する説明でも、私が見た中で最も基本的なものです。 これは、インデックスの最も重要な一面をとてもうまく表していますが、残念ながら この本には不十分と言わざるを得ません。この章では、インデックスの構造について、 表面的過ぎないけれど深入りもしすぎない程度に説明していきます。これで、 この本全体を通して扱われる、SQLのパフォーマンスについて理解するのに十分な 基礎を知ることができるでしょう。

インデックスは、データベースの中で特有の構造を持ち、create index 文で作成されます。独自のディスク領域を必要とし、インデックスを張られた テーブルのデータを保持します。これはつまり、インデックスは純粋に冗長な構造で あるといえます。 インデックスを作成しても、テーブルのデータは変更されず、テーブルを参照する 新しいデータ構造が作られるだけです。データベースのインデックスは、その名の通り、 書籍の最後についている索引(インデックス)に非常に似ています。そのための場所を 必要とし、冗長で、別の場所に保存されている本当の情報を参照するだけであるという 特徴は同じです。

クラスタ化インデックス (SQL Server, MySQL/InnoDB)

SQL ServerとMySQL(InnoDBの場合)では、「インデックス」 という言葉はより広い意味で使われています。これらのデータベースにおいては、 テーブルに対して、クラスタ化インデックスと呼ばれる インデックス構造でのみアクセスします。Oracleでは、このようなテーブルを 索引構成表(IOT : Index-Organized Table)と呼びます。

第5章, 「データのクラスタリングで、その利点と欠点を含めた詳細な 説明をしています。

データベースのインデックスを検索するのは、印刷された電話帳を検索するのに にています。全ての要素が、あらかじめ決められた順番に並んでいるという コンセプトのためです。並べ替えの順番から、それぞれの要素がどこにあるのかが すぐにわかるため、順に並んでいるデータから1つの要素を探すのは、素早くかつ 簡単にできます。

とはいえ、印刷物と違って、データベースのインデックスは常に更新に さらされます。元々ある要素の前後に、追加する要素を書く場所がないという 単純な理由で、印刷物を更新がある度に書き換えるのは不可能です。印刷物の場合、 次の印刷のタイミングまで更新分のデータをためておくことにより、この問題を 回避しているわけです。SQLデータベースの場合、そんなに長く待つことはできません。 insertdeleteupdateといった文をすぐに実行し、大量のデータを動かすこと なく、インデックスの順序を保つ必要があります。

データベースは、2つのデータ構造を組み合わせてこの問題に対処しています。 それが、双方向連結リストと、検索木です。これら2つのデータ構造で、ほとんどの データベースのパフォーマンス特性の説明がついてしまいます。

目次

  1. インデックス リーフノード - 二重連結リスト

  2. 検索 ツリー(Bツリー) - バランス木

  3. 遅いインデックス パートI - インデックスを遅くする2つの原因

前へ次へ

著者について

Markus Winandの写真

Markus Winand氏は、開発者がSQLパフォーマンスを改善するお手伝いをしています。彼は、SQL Performance Explainedの 著者でもあり、出張トレーニングhttp://winand.at/での リモート講義も 行っています。

“Use The Index, Luke!” by Markus Winand is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.
法律上の通知 | 接触 | 無保証 | 商標 | Privacy | CC-BY-NC-ND 3.0 license