The Cusp of Helix

Fertile Forest Model
[第一章: RDB に於けるツリー構造データ]

モデルの役割

ツリー構造データは「階層構造データ」とも呼ばれます。ツリー構造データを RDB で扱うモデルの役割は、次の二項に要約されます。

  1. ツリー構造データを RDB テーブルに格納する。
  2. 任意のノードについて、関連ノードを効率的に取得するクエリを記述する。

(1) ツリー構造データを RDB テーブルに格納する

ひとつめの項目「ツリー構造データを RDB テーブルに格納する」という機能をモデルが有しているかどうかの基準は、次のように定義できます。

保存した全ノードの情報から、元の階層構造を復元できること。

データベースに保存されたツリー構造データから元のツリー構造が復元できないのでは、保存したとは言えません。改めて記述する必要もないほど基本的な事なので、ここに異論を挟む人はいないでしょう。

(2) 関連ノードを効率的に取得するクエリを記述する

データベースを利用する場合、一般的には検索される前提でデータを保存します。ツリー構造データをデータベースに保存すれば、各ノードから「部分木」「親ノード」「子ノード」「祖先ノード」「子孫ノード」などの「関連ノード集合」が検索できると考えるのが自然な考え方です。これらの関連ノードを効率よく取得するための検索クエリが書ける事は、ツリー構造データを扱うモデルの重要な役割です。

下図で、 [A], [B], [C], ... はノードを表します。

              [A]
               |
           +---+---+
           |       |
          [B]     [C]
           |       |
         +-+-+   +-+-+
         |   |   |   |
        [D] [E] [F] [G]
                     |
                   +-+-+
                   |   |
                  [H] [I]

[C] の部分木を人が目視で検索する場合、ツリー構造図上で [C] から下方に伸びる枝を辿って全ノードをピックアップします。この例では、 [C] の部分木の集合は次のようになります。

          [C]
           |
         +-+-+
         |   |
        [F] [G]
             |
           +-+-+
           |   |
          [H] [I]

線を辿るのは規則的な作業なので、「ツリー構造データをデータベースに入れれば関連ノードを簡単に検索できるようになるはずだ」と、誰もがそう考えるでしょう。

ツリー構造データでは、以下のような集合が頻繁に検索されます。先程の図における例を記載しました。

基点ノード 関係 ノード集合
[B]親ノード[A]
[B]子ノード[D] [E]
[H]先祖ノード[A] [C] [G]
[C]子孫ノード[F] [G] [H] [I]
[C]部分木[C] [F] [G] [H] [I]

この項目で肝となるのは「効率的に」というフレーズです。効率が不要であるならデータベースの検索クエリを工夫する必要もありません。全ノードを取得してから、条件に見合うかどうかを各ノードについてプログラム言語で調べればいいだけです。

しかし、ノードが数億あるようなツリー構造データで毎回全ノードを取得するのは現実的ではありません。処理する際に大量のメモリと実行時間が必要になるでしょう。ノード総数が数億で検索したいノードが数個しかないなら、絞り込む条件を指定して高速に取得できるにシステムを設計するのが普通です。