The Cusp of Helix

Fertile Forest Model
[第二章: 従来のモデル]

入れ子集合モデル

各ノードを円と考えたとき、円と円を入れ子にすることで親子関係を表現するモデルです。 2004年にアメリカの Joe Celko 氏によって提唱されました。多くのフレームワークに於いて、「ツリー構造データを扱うモデル」として入れ子集合モデルが活用されています。 (2024年 04月時点)

モデルデザイン

以下のツリー構造データを「入れ子集合モデル」で表してみましょう。図中の [A] ~ [I] はノードを示します。

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

各ノードの左右に、以下のように連番を振ります。この左右の数字を格納するカラムが、入れ子集合モデルに於ける階層構造カラムになります。

                    [1 A 18]
                       |
               +-------+--------+
               |                |
            [2 B 7]          [8 C 17]
               |                |
           +---+---+       +----+----+
           |       |       |         |
        [3 D 4] [5 E 6] [9 F 10] [11 G 16]
                                     |
                                +----+----+
                                |         |
                            [12 H 13] [14 I 15]

連番の規則

root ノードから開始して以下の手順を繰り返すことで、上図のように附番できます。

  1. 現在のノードの左に番号が振られてないなら、左に附番する。
  2. 現在のノードに「附番されてない子ノード」がある場合、その中で一番左の子ノードへ移動。その後、手順一に戻る。
  3. 附番されてない子ノードがない場合、現在のノードの右に附番して親ノードに移動。その後、手順一に戻る。
  4. 親ノードがない場合は終了。

ノードの入れ子は、下図のように示されます。附番した数字が、左から昇順で並んでいます。

[A] 1
[B] 2
[D] 3 - 4
[E] 5 - 6
7
[C] 8
[F] 9 - 10
[G] 11
[H] 12 - 13
[I] 14 - 15
16
17
18

各ノードの左右の数字は、親ノードの左右の範囲に含まれるのが分かるでしょうか。例えば、 [G] の左右の数字は (11, 16) なので、 [G] の子ノードである [H] と [I] の左右の数字は (11, 16) の範囲に入っています。これにより、 [H] と [I] は [G] の子孫ノードであると判定できます。

ノードに関する最小限の情報として、各ノードの id とノード名だけのテーブルを考えます。このテーブルには階層構造カラムがないので、ツリー構造データを保存して復元することはできません。

id1234 56789
nameABCD EFGHI

テーブルに「左右の番号を格納するカラム」をふたつ追加します。このカラムを「左右カラム」と呼ぶことにします。左右カラムは、階層構造カラムと検索効率カラムとして機能します。

id123 456789
nameABC DEFGHI
tree_left 1 2 8 3 5 9 11 12 14
tree_right 18 7 17 4 6 10 16 13 15
CREATE TABLE `nested_set_models` ( `id` int(11) NOT NULL AUTO_INCREMENT, `name` varchar(225) DEFAULT NULL, `tree_left` int(11) NOT NULL, `tree_right` int(11) NOT NULL, PRIMARY KEY (`id`), KEY `left_index` (`tree_left`) ) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8; INSERT INTO `nested_set_models` (`id`, `name`, `tree_left`, `tree_right`) VALUES (1, 'A', 1, 18), (2, 'B', 2, 7), (3, 'C', 8, 17), (4, 'D', 3, 4), (5, 'E', 5, 6), (6, 'F', 9, 10), (7, 'G', 11, 16), (8, 'H', 12, 13), (9, 'I', 14, 15);