2003年 3月 1日 indexing (B ツリー 構造) >> 目次 (テーマごと)


 
 インデックス の構造として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) 揺らぐ

 レコード・アット・ア・タイム 法を使うなら、インデックス をたぐらないようして、インデックス が揺らがないようにすれば良い、ということである (後日、述べる)。



  << もどる ベーシックス すすむ >>
  データベースの基礎知識