データの保存構造

heap organized table
index organized table　
Heap organized tableは、順序のないテーブル。登録は早いが、検索は遅い。そのため、ログデータの保存など、検索の必要がない場合にしか使われない。
Index organizbd tableは、順序があるテーブル。インデックスも使えるので、一般的なアプリケーションではこちらを使用する。

インデックスの仕組み

インデックスの仕組みは、本の目次と似ている。
本から情報を探すとき、目次がないと、全てのページを見つかるまで探すことになるが、目次があれば探す範囲を少なくできる。

データベースも、インデックスを使うと、データが見つかるまでに探すデータの数を減らせる。

インデックスのアルゴリズム

btreeインデックス　

b＋treeの木構造となってる。
ルートノード、ブランチノード、リーフブロックで構成されていてる。
ルートノードは一つだけで、そこからブランチノードが生え、ブランチノードからまた別のブランチノードが生える。
最後にリーフブロックがくっつく。

実際のレコードはリーフブロックにだけあり、ルートノード、ブランチノードは他のノードへの参照と検索用のキー値をもってる。

ルートノードはだいたい真ん中くらいの値をもってて、それより小さい値は左のブランチノードへ、それより大きいものは右のブランチノードへ格納されてるので、大小比較をしていくと目的のデータが格納されてるリーフブロックに辿り着ける。

一個のデータをとるだけなら、全体のデータ数が増えても検索時間はほとんど増えない。
いわゆる、O(logN)の計算量となる。

_ bitmapインデックス
btreインデックスはカーディナリティの低いデータに向いてないが、こちらは逆にカーディナリティの低いデータに向いてる。
データをbit単位の値の配列形式で保存する。
例えば、男を1,女を0とすると、
1.男
2.男
3.女
は、110となる

オプティマイザ

ルールベースオプティマイザとコストベースオプティマイザがある。
今はほとんどコストベースオプティマイザ。
全体結果最適化を目指す。

オプティマイザの動作

1.クエリの解析
2.暫定的な実行計画の作成
3.実行計画のコストの算定
4.もっともコストの低い実行計画を選択

インデックスの戦略

複合インデックス
　インデックスを複数カラムのセットで設定しておくやり方。
　予めソートされてるのでパフォーマンスはいいが、柔軟性はない。
　順番も意味があり、最初のカラムの検索でインデックスが使用されない範囲検索などをする場合はパフォーマンスがでない。
最初のカラムだけが検索される場合はインデックスが使えるが、2番目以降のカラムだけが検索される場合は、インデックスが使用されないこともある。
マージインデックス
　個別のインデックスが設定された2つのカラムで検索するときに使われる。
　複合インデックスにしておくよりはパフォーマンスに劣ることがあるが、柔軟性があり、インデックスのサイズも小さくてすむ。
どのような複合インデックスを設定し、どこに単体のインデックスを設定するかは、カラムのカーディナリティ、アクセスの量、データの量、よく使われる検索条件を考慮して決める必要がある。

まとめ

データベースは奥が深い。