前回から間が空いてしまいましたが，ペースを上げての第4回です。前回からの続きでインデックスを扱います。その中でも特に，手品の種の部分にあたるインデックスのアルゴリズムに焦点を当てます。難しい話になるのではと心配されるかもしれませんが，大丈夫です。ここではアルゴリズムの特徴と特性を理解していただくのが目的で，その詳細についての難しい話はありません。ここで読んでいる皆さんはDBMSの開発者ではなく使用者でしょうから，特徴・特性をふまえてどのような使い方をするべきかを学んでください。
利用されるアルゴリズム
まずは，実際にどのようなアルゴリズムがどのくらい使われているか，というのを以下に示します。
この図はあくまでもイメージです。しかし，B-Treeのみが圧倒的に使われているというのは本当に現実です。確かに，インデックス作成時に標準のままアルゴリズムをなにも指定しない場合，B-Treeで作られる場合が多いという面はあります。しかし，それ以上にこのインデックスは普遍的に使われるだけの良さを持っています。そこで，今回はまずB-Treeの特徴について説明します。これさえ分かれば世の中の99%のインデックスは理解したも同然です。
B-Tree
B-Treeインデックスは，その名のとおりB-Tree（B木）というアルゴリズムやその派生を使って実装されたインデックスです。Treeという名称に違わずツリー型の構造を持ったアルゴリズムです。ツリー型では，検索を逐次ではなく木構造をたどることで高速に出来るという特徴があります。
しかしながら，B-Treeそのものは非常に複雑なので，ここでは同じ木構造を持ち，同じように検索に用いられるものの中で，シンプルな二分探索木でその特性を説明しましょう。
