隣接リストモデル
+ 「隣接リストモデル」は、従来のモデルの中で最も単純な構造でデザインされたモデルです。
モデルデザイン
以下のツリー構造データを「隣接リストモデル」で表してみましょう。図中の [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 |
隣接リストモデルでは、階層構造カラムとして「親ノードの id を格納するためのカラム」が追加されます。 root ノードには親ノードがないため、 null を格納します。
| id | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| name | A | B | C | D | E | F | G | H | I |
| tree_parent | null | 1 | 1 | 2 | 2 | 3 | 3 | 7 | 7 |
CREATE TABLE `adjacency_list_models` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(225) DEFAULT NULL,
`tree_parent` int(11) DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `parent_index` (`tree_parent`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;
INSERT INTO `adjacency_list_models`
(`id`, `name`, `tree_parent`)
VALUES
(1, 'A', NULL), (2, 'B', 1), (3, 'C', 1),
(4, 'D', 2), (5, 'E', 2), (6, 'F', 3),
(7, 'G', 3), (8, 'H', 7), (9, 'I', 7);