インデックス の構造としてB ツリー 構造が使われることが多い。
　B ツリー は 「Balance-Tree」 の略称である。

　B ツリー 構造の基本的な説明は、以下の文献を参照されたい。

　基本算法 2/情報構造、米田信夫・筧 捷彦 共訳、サイエンス 社
　[ KNUTH THE ART OF COMPUTER PROGRAMMING の訳 ]

　
1. B ツリー 構造の基本形

　B ツリー 構造は 「ツリー 構造」 であるから階層構造となる。
　最上位の階層 （entry-point） を 「root」 という。
　最下位の階層を 「leaf」 といい、キー 値と データ・アドレス が収められている。
　途中の階層を 「branch」 といい、「leaf」 に辿り着くための経路である。
　最下位の階層を生成してから、「アクセス の効率」 を実現するために、「branch」 構造が用意される。

　市販されている RDB のほとんどすべては、インデックス 構造として B ツリー 構造を導入している。
　B ツリー 構造が使われる理由は、「どんな ランダム・アクセス に対しても均等な レスポンス を保証する」 点にある。

　キー の値と データ・アドレス （相対 アドレス） を 「leaf」 のなかに収める形式としては以下の 2つがある。
　（1） 1つの キー の値に対して 1つの データ・アドレス を対応する。（I-SAM 式あるいは VSAM 式）
　（2） 1つの キー の値に対して複数の データ・アドレス を対応する。（inverted 式）

　この点に関しては、後日、解説する。

　B ツリー 構造では、2階層目までの階層を 「high-level index」 といい──「root」 は 0階層とされる──、3階層目から 「leaf」 までの階層を 「low-level index」 という。

　
2. B ツリー 構造の弱点とその対応策

　B ツリー 構造の特徴は、ランダム・アクセス の効率を実現する ツリー 構造である。
　ランダム・アクセス の効率を実現する やりかた であるから、逆に言えば、シーケンシャル・アクセス （順次 アクセス） 向きではない。すなわち、多量の データ を対象とした バッチ を シーケンシャル に アクセス する構造ではない。
　端的に言えば、B ツリー 構造は 「アクセス 経路を手繰 （たぐ） る」 構造であるから、シーケンシャル 向けではない。

　B ツリー 構造を シーケンシャル 用にも使うなら、「leaf」 （最下位層だけ） を GetNext するようにすればよい。
　そうすれば、「indexing」 は、シーケンシャル・アクセス でも高 レスポンス を実現できる。

　「leaf」 を GetNext するやりかたは、プロダクト ごとに違うので、それぞれの プロダクト を調べてほしい。
　GetNext コマンド を用意している プロダクト もあれば、「rows ＝」 パラメータ を最高値にすればよい プロダクト もある。

　「leaf」 のなかには、インデックス を生成したときに、スラック （slack、ゆとり、たるみ） 領域が用意される。
　スラック 領域は、1つの ブロック に対して、20％ から 30％ほどを用意することが多い。
　というのは、データ が更新 （追加と削除） されたら、キー も更新 （追加あるいは削除） されるので、キー の追加に対応するためである。

　ちなみに、データ を削除しても、キー は 「物理的には」 削除されないで、「使用対象ではない」 という FLAG が立てられる。そして、インデックス を再編成したときに、FLAG が立てられている キー を 「物理的に」 削除する。

　既存の キー の削除と新たな キー の追加が多ければ、用意されている スラック 領域が費消され、新たな キー を収める領域が涸渇することも起こる。そうなれば、ブロック （low-level index） を スプリット （split、分割） して、新たな領域を用意することになる。「low-level index」 が スプリット されたら、ときには、それに呼応して、「high-level index」 が再編成 （スプリット） されることがある。
　ブロック が再編成 （スプリット） されている途中なら、アクセス は当然ながら禁止される （「待ち」 状態となる）。

　データ の更新 （削除および追加） が多い トランザクション に対しては、インデックス の スプリット 状態を監視したほうがいい。逆に言えば、インデックス が スプリット しないような対応策を考えなければならないということである。

　さて、上述したように、B ツリー 構造の弱点は、以下の 2点として、まとめることができる。

　（1） 手繰 （たぐ） る
　（2） 揺らぐ