2004年 8月16日 作成 「基準編第12章 (レコード・アット・ア・タイム 法)」 を読む >> 目次に もどる
2007年 5月16日 更新  




 本稿では、レコード・アット・ア・タイム 法 -- キー (index-key) を使って、レコード 単位に アクセス すること -- を、RDB (コッド 関係 モデル) の観点に立って、見直している。検討の対象としたのは、以下の 2点である。

 (1) B-tree (Balance-tree) 構造
 (2) キー の種類 (キー の系統樹)

 
 以上の 2点に関しては、「ベーシックス」 のなかで、具体的に述べた [ 192 ページと 196 ページを参照されたい ]。本稿は、以下の 2点を確認するために執筆した。

 (1) indexing は、コッド 関係 モデル とは無関係である。
    プロダクト としての RDB が、バージョンアップ のなかで、上積みした技法である

 (2) B-tree 構造には、パフォーマンス を落とす弱点として、以下の 2つがある。
    - たぐる (アクセス・パス を、順次、通る)
    - 揺らぐ (ブロック が割れたら、再編成される)

 
 (1) は、小生が 「INDEX-only」 を考え出す契機となった。すなわち、RDB は、セット・アット・ア・タイム 法を基本技法としているが、レコード・アット・ア・タイム 法が上積みされたので、レコード・アット・ア・タイム 法を セット・アット・ア・タイム 法のように使うことを考えたのである。

 (2) B-tree の 「たぐる」 構造は、(「INDEX-only」 のなかで、) 「ヌル・キー (null-key)」 を使う契機となった。つまり、B-tree 構造の階数を排除する技法を考えた--ただし、ヌル・キー を、B-tree 構造のなかから排除しない プロダクト もあるので、注意されたい。

 
 RDB が 「驚異的な」 高 パフォーマンス を実現する手段として、「INDEX-only」 と 「ヌル・キー (null-keys)」 を使う理由を記述したのが本稿である。 □

 

[ 補遺 ] (2007年 5月16日)

 indexing については、もっと詳細に記述しようと思えば、記述できるのですが、本稿では、B-tree の特徴点を まとめるだけにしました。というのは、レコード・アット・ア・タイム 法を述べるのが本書の狙いではなかったから。本書では、レコード・アット・ア・タイム 法は、あくまで、セット・アット・ア・タイム 法と対比して、セット系の弱点を補強するために indexing を (「索引き」 としての使ってきた従来の やりかた を離れて) view のように使う やりかた を述べる前提部にしました。indexing に関する基本的な技術を学習するには、以下の書物を読んで下さい。

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

 B-tree のなかで indexing を効率的に使う コツ は--常識で考えれば、直ぐに わかることなのですが--「たぐらない」 「ゆらがない」 ようにすれば良い、ということです。

 





  << もどる HOME すすむ >>
  「論理データベース論考」を読む