SQLとインデックス
インデックスとは、大雑把にいうと、インデックスの構文で指定した
カラムの値(の重複を省いてソートして格納した配列の値)をキー、
キーの値と同一の値を持つ行に対するポインタ(アドレス)全て(の配列)
をデータとした1:nの(キーの昇順にソートされた)連想配列のようなモノ
です。キーは昇順にソートされた形で保存されていますが、データは
ソートされていません。
(ORACLEではROWID、PostgreSQLではOIDという形でテーブルの行に
対するポインタへのアクセス手段を用意しています。)
多くのDBでは、インデックスにBツリーと
呼ばれる構造を採用しています。
インデックスの構文で指定したカラムの型が数値型の場合、
ノードの深さが１(?)なので、インデックスの構造は上記の連想配列と
同じ構造になります、文字列型の場合、インデックスの構造はノード
の深さが文字列の長さによって可変するBツリーになります。
Bツリーのノードが深くなればなるほど、ツリー内の探索に時間が
掛かるようになり、インデックスを貼ることによるメリットが弱まる
ので、インデックス内のBツリーのノードが浅くなるような形で
インデックスを作成する必要があります。
インデックスはテーブルに対して、行の新規追加、インデックスで
キーとなっているカラムの値の変更を含む行の更新、行の削除が
あった場合、(整合性を保つため)書き換えられます。
テーブルAのカラムBが3である集合のみを抽出するSQL
select * from A where B = 3
をRDBMSに送信したとき、SQL実行エンジン(含SQLパーサ)は
カラムBに対してインデックスが貼られていない場合、テーブルAに
対してシーケンシャルにアクセスしカラムBが3である行を探します
(全件アクセスを回避するために、テーブルAに対してシーケンシャル
にアクセスする前に、メモリ上に展開されたテーブルAデータのカラム
Bの値の昇順？によるソート処理が行われます)、カラムBに対して
インデックスが貼られている場合、インデックス内のデータ構造から
カラムBが3である行全てを取得します。
大規模テーブルに対してSELECT文を発行する場合、事前に発行する
SELECT文にマッチしたインデックスを貼っておく必要があります。
インデックスを張っているテーブルを更新すると同時に、そのテーブル
に紐づくインデックス全ての更新が行われるため、インデックスを張って
いない場合に較べてテーブルの更新処理に時間が掛かります。
必要のないインデックスを張らないことが肝要です。
インデックスが、RDBMS上では、空気のような存在ではなく、コストの
掛かる実体を持つ存在であることを認識しておく必要があります。
select * from A where B = 3
の「B = 3」はテーブルAの部分集合を切り出すための式です。
SQLのwhere句は、集合を絞り込む(部分集合を切り出す)ための式と
絞り込んだ集合(切り出した部分集合)に対する集合演算を行う
「AND、OR」で構成されています。
SQLのwhere句で使用可能な式にはインデックスにアクセスする式と
インデックスにアクセスしない式があります、インデックスにアクセス
しない式の場合、テーブルにシーケンシャルにアクセスし、条件に合致
する行を抽出します.
SQLのwhere句を記述するとき、インデックスにアクセスする式で
なるべく記述し、どうしてもインデックスにアクセスしない式でしか
記述できない場合にはテーブルにシーケンシャルにアクセスする回数
を減らす工夫をする必要があります。
書きかけ、推敲中...。
[蛇足]
インデックスとは何かを机上のみで理解したつもりに
なっているだけで実際には理解していない人間が案外多い、
無意味なインデックスが張られたDBをたまに見かける。
RDBMAとSQLに関する専門的な書にも、インデックスとは
何かの明解な記述をしているモノはほとんどありません。
本によってはインデックスを本の索引に例えたり、図書館の
図書カードに例えていたりしますが、これらの記述では
インデックスを的確には表現できていないと感じます。
テーブルを図書館の本棚に例えるなら、インデックスはアドレスの
集合を返すので、本の位置を返す図書の検索端末のほうがまだ近い
気がします。図書カードは利用者からみると本棚の一部ですが、
インデックスはテーブルの一部ではなくテーブルとは別に存在
するので。
