経路列挙モデル
「経路列挙モデル」は、「隣接リストモデル」では取得しにくかった部分木や祖先ノードなどの関係ノードを検索しやすくなるようにデザインされたモデルです。各ノードに「 root ノードからの経路」を保存するカラムを設けてツリー構造データを格納して、親子関係を包括的に管理します。「経路実体化モデル (Materialized Path Model) 」とも呼ばれます。
モデルデザイン
以下のツリー構造データを「経路列挙モデル」で表してみましょう。図中の [A] ~ [I] はノードを示します。
[A]-+-[B]-+-[D]
| |
| +-[E]
|
+-[C]-+-[F]
|
+-[G]-+-[H]
|
+-[I]
ノードに関する最小限の情報として、各ノードの id とノード名だけのテーブルを考えます。このテーブルには階層構造カラムがないので、ツリー構造データを保存して復元することはできません。
| id | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| name | A | B | C | D | E | F | G | H | I |
経路列挙モデルでは、階層構造を構築するために「 root ノードからの経路を格納するカラム」が追加されます。経路カラムには、 root ノードからそのノードまでの id を記号で連結した文字列が保存されます。この例では、記号として「/（スラッシュ）」を使っています。
| id | name | tree_path |
|---|---|---|
| 1 | A | 1/ |
| 2 | B | 1/2/ |
| 3 | C | 1/3/ |
| 4 | D | 1/2/4/ |
| 5 | E | 1/2/5/ |
| 6 | F | 1/3/6/ |
| 7 | G | 1/3/7/ |
| 8 | H | 1/3/7/8/ |
| 9 | I | 1/3/7/9/ |
ツリー構造データのために追加されるのは見かけ上１カラムだけですが、ひとつのカラムに複数のデータを格納しています。階層の深さによって延べカラム数が変動すると考えます。
CREATE TABLE `path_enumeration_models` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(225) DEFAULT NULL,
`tree_path` varchar(225) DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `path_index` (`tree_path`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;
INSERT INTO `path_enumeration_models`
(`id`, `name`, `tree_path`)
VALUES
(1, 'A', '1/' ), (2, 'B', '1/2/' ), (3, 'C', '1/3/' ),
(4, 'D', '1/2/4/'), (5, 'E', '1/2/5/' ), (6, 'F', '1/3/6/' ),
(7, 'G', '1/3/7/'), (8, 'H', '1/3/7/8/'), (9, 'I', '1/3/7/9/');