2009年12月16日 「実践編-14 レコード・アット・ア・タイム 法」 を読む >> 目次にもどる

 

 本編の題名を 「レコード・アット・ア・タイム (record-at-a-time) 法」 としていますが、本編で説明している技術は、従来の 「レコード・アット・ア・タイム 法」──すなわち、index-key (特に、unique-key) を使って、レコード 単位に アクセス する やりかた──ではなくて、indexing (B-tree 構造) です。

 「木 (tree)」 は、離散数学の 「グラフ (graph)」 の領域で説明されます。数学では、基本閉路をふくんでいない グラフ を 「森 (forest)」 とか 「林」 といい、連結な無閉路 グラフ を 「木」 と云います。特に、コンピュータ・サイエンス では、「木」 には 1つの 「根 (root)」 があることを前提にするので、「木」 と謂えば、ふつう、「根付き木 (rooted tree)」 のことを云います。さて、「閉路」 とか 「連結」 については数学の書物を読んでもらうとして、「木」 は有向 グラフ の特殊形であって、「根付き木」 が indexing で使われています。Indexing に流用されている 「根付き木」 の しくみ を 145ページ に単純な図で示しました。

 以下の単純な 「木」 を例にして、「検索法」 を説明します。


              r ○
              / \
             /   \
           y1 ○     ○ y2
           / \
          /   \
        x1 ○     ○ x2
 「根付き木」 では、ルート r から頂点 x1, x2, y2 への道があり、y1 は この道のうえの頂点であるとき、y1 を x1, x2 の 「祖先」 であると云い、x1, x2 は y1 の 「子孫」 であると云います。そして、特に、y1, x1 (および、y1, x2) が 「辺」 であれば、y1 を x1 (および、x2) の 「親」 と云い、x1 (および x2) を 「子」 と云います。

 「子」 を持たない頂点を 「葉 (leaf)」 と云います──この例では、x1, x2 および y2 が 「葉」 です。

 「木」 では、「子」 のあいだには、「関係」 が定められていないのですが、「子」 のあいだに 「並び」 が定められている 「木」 を 「順序木 (ordered tree)」 と云います。「木」 と云えば、ふつう──特に断りがなければ──「根付き順序木」 を指します (下図参照)。


              r ○
              / \
             /   \
           y1 ○─────○ y2
           / \
          /   \
        x1 ○─────○ x2
 さて、「根付き順序木」 において、検索の基本法には、以下の 2つが考えられます。

 (1) DFS (Depth First Search)
 (2) BFS (Breadth First Search)

 DFS は、「階」 関係の道を辿る やりかた で──たとえば、(r, y1) (y1, x1) (y1, x2) (r, y2) ──、BFS は 「次数」 の道を辿る やりかた です──たとえば、(y1, y2) (x1, x2)。

 「木」 を indexing として使ったときに弱点となるのが、「たぐる」 「揺らぐ」 という点です。この弱点を本編 (実践編-14) で述べています。そして、RDB プロダクト に搭載された indexing (CRATED INDEX) は、セット・アット・ア・タイム 法と無関係であることを本編で指摘しておきました。 □

 



  << もどる HOME すすむ >>
  目次にもどる