---
title: RDBでのツリー表現入門2024
tags:  #rdb #sql #モデリング #テーブル設計 #ツリー #mysql  
author: [Kent OHASHI](https://www.docswell.com/user/lagenorhynque)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/GJWDRW5K72.jpg?width=480
description: RDBでツリー構造を表現するための典型的なモデルについて学ぼう! cf. 2020年版(in Opt Technologies): https://www.docswell.com/s/lagenorhynque/KW1WYP-introduction-to-tree-representations-in-rdb
published: July 26, 24
canonical: https://www.docswell.com/s/lagenorhynque/K4V3WW-introduction-to-tree-representations-in-rdb-2024
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/GJWDRW5K72.jpg)

RDBでのツリー表現入門2024
#NextbeatTechBar
1


# Page. 2

![Page Image](https://bcdn.docswell.com/page/4EZGR5NNJ3.jpg)

🐬
lagénorhynque カマイルカ
株式会社スマートラウンドのプロダクトエンジニア
主要技術スタック: Kotlin/Ktor + PostgreSQL
関数型言語/関数型プログラミングが好き
仕事や趣味でClojure, Scala, Haskellなどに長く
触れてきた
RDB/SQLが好き
プログラミングを始めて最初に好きになった言語
がSQLだった
2


# Page. 3

![Page Image](https://bcdn.docswell.com/page/Y76YR989EV.jpg)

0. 事前準備
1. 隣接リスト(adjacency list)
2. 経路列挙(path enumeration)
3. 入れ子集合(nested sets)
4. 閉包テーブル(closure table)
3


# Page. 4

![Page Image](https://bcdn.docswell.com/page/G75G8N9D74.jpg)

0. 事前準備
4


# Page. 5

![Page Image](https://bcdn.docswell.com/page/9J2YK55MJR.jpg)

サンプルコード
lagenorhynque/tree-representations-in-rdb
# 実験環境の準備
docker compose up -d
make migrate
ローカルDB: MySQL 8.4
compose.yaml
5


# Page. 6

![Page Image](https://bcdn.docswell.com/page/DEYGNKKPEM.jpg)

ツリーの本体データ用テーブル department
CREATE TABLE `department` (
`department_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
`name` varchar(100) NOT NULL,
PRIMARY KEY (`department_id`)
);
6


# Page. 7

![Page Image](https://bcdn.docswell.com/page/VJNGXRRM78.jpg)

department の初期データ
7


# Page. 8

![Page Image](https://bcdn.docswell.com/page/YE9W8MMWE3.jpg)

表現したいツリー
8


# Page. 9

![Page Image](https://bcdn.docswell.com/page/GE8N8LLR7D.jpg)

1. 隣接リスト(adjacency list)
9


# Page. 10

![Page Image](https://bcdn.docswell.com/page/LELPRLL27R.jpg)

「隣接リスト」モデル
10


# Page. 11

![Page Image](https://bcdn.docswell.com/page/4JM4RMM97W.jpg)

ツリー管理用のテーブル
CREATE TABLE `department_adjacency_list` (
`department_id` int(10) unsigned NOT NULL,
`parent_id` int(10) unsigned DEFAULT NULL,
PRIMARY KEY (`department_id`),
FOREIGN KEY (`department_id`)
REFERENCES `department` (`department_id`)
ON DELETE CASCADE ON UPDATE RESTRICT,
FOREIGN KEY (`parent_id`)
REFERENCES `department` (`department_id`)
ON DELETE CASCADE ON UPDATE RESTRICT
);
parent_id: 親ノード
本体データ用テーブルに含めても良い
11


# Page. 12

![Page Image](https://bcdn.docswell.com/page/PJRWRVV979.jpg)

department_adjacency_list の初期データ
12


# Page. 13

![Page Image](https://bcdn.docswell.com/page/PEXPRZZ37X.jpg)

すべてのノードとその階層情報の取得
WITH RECURSIVE department_tree AS (
SELECT d.*, dal.parent_id, 0 distance
FROM department d
JOIN department_adjacency_list dal USING (department_id)
WHERE dal.parent_id IS NULL
UNION ALL
SELECT d.*, dal.parent_id, dt.distance + 1
FROM department d
JOIN department_adjacency_list dal USING (department_id)
JOIN department_tree dt ON dal.parent_id =
dt.department_id
)
SELECT *
FROM department_tree;
distance: ルートノードからの距離
cf. MySQL :: MySQL 8.4 Reference Manual :: 15.2.20
WITH (Common Table Expressions)
13


# Page. 14

![Page Image](https://bcdn.docswell.com/page/3EKDR88NJD.jpg)

14


# Page. 15

![Page Image](https://bcdn.docswell.com/page/L73R822ZJ5.jpg)

特定のノードからの子孫ノードの取得
WITH RECURSIVE department_tree AS (
SELECT d.*, dal.parent_id, 0 distance
FROM department d
JOIN department_adjacency_list dal USING (department_id)
WHERE d.department_id = 10
UNION ALL
SELECT d.*, dal.parent_id, dt.distance + 1
FROM department d
JOIN department_adjacency_list dal USING (department_id)
JOIN department_tree dt ON dal.parent_id =
dt.department_id
)
SELECT *
FROM department_tree;
distance: ノード 10 からの距離
15


# Page. 16

![Page Image](https://bcdn.docswell.com/page/87DYMZZ47G.jpg)

16


# Page. 17

![Page Image](https://bcdn.docswell.com/page/VJP6RDDVE8.jpg)

特定のノードの子ノードの取得
SELECT d.*
FROM department d
JOIN department_adjacency_list dal USING (department_id)
WHERE dal.parent_id = 10;
17


# Page. 18

![Page Image](https://bcdn.docswell.com/page/2EV3R11R7Q.jpg)

18


# Page. 19

![Page Image](https://bcdn.docswell.com/page/57G3M226JL.jpg)

特定のノードの親ノードの取得
SELECT d.*
FROM department d
JOIN department_adjacency_list dal
ON d.department_id = dal.parent_id
WHERE dal.department_id = 10;
19


# Page. 20

![Page Image](https://bcdn.docswell.com/page/4EQ5RPP2JP.jpg)

20


# Page. 21

![Page Image](https://bcdn.docswell.com/page/KJ498YYP71.jpg)

PROS
モデルとして単純(良くも悪くもナイーブ)
直近の親/子ノードに対するアクセスが容易
挿入操作が容易
参照整合性が保証できる
21


# Page. 22

![Page Image](https://bcdn.docswell.com/page/LE1K266XJG.jpg)

CONS
再帰CTE (recursive common table expressions)が
使えないと任意階層に対するクエリが困難
削除操作が煩雑
parent_id で NULL が現れてしまう
ルートノード管理用のテーブルを用意することで
回避可能
22


# Page. 23

![Page Image](https://bcdn.docswell.com/page/GEWDRWWKJ2.jpg)

2. 経路列挙(path enumeration)
a.k.a. 経路実体化(materialized path)
23


# Page. 24

![Page Image](https://bcdn.docswell.com/page/47ZGR55NE3.jpg)

「経路列挙」モデル
24


# Page. 25

![Page Image](https://bcdn.docswell.com/page/YJ6YR9997V.jpg)

ツリー管理用のテーブル
CREATE TABLE `department_path_enumeration` (
`department_id` int(10) unsigned NOT NULL,
`path` varchar(1000) NOT NULL,
PRIMARY KEY (`department_id`),
FOREIGN KEY (`department_id`)
REFERENCES `department` (`department_id`)
ON DELETE CASCADE ON UPDATE RESTRICT
);
path: 先祖からそのノードまでの経路(パス)
本体データ用テーブルに含めても良い
25


# Page. 26

![Page Image](https://bcdn.docswell.com/page/GJ5G8NNDJ4.jpg)

department_path_enumeration の初期データ
26


# Page. 27

![Page Image](https://bcdn.docswell.com/page/9E2YK58MER.jpg)

すべてのノードとその階層情報の取得
SELECT d.*, dpe.path,
CHAR_LENGTH(dpe.path) - CHAR_LENGTH(REPLACE(dpe.path, &#039;/&#039;,
&#039;&#039;)) - 1 depth
FROM department d
JOIN department_path_enumeration dpe USING (department_id);
depth: ルートノードからの距離
27


# Page. 28

![Page Image](https://bcdn.docswell.com/page/D7YGNK6P7M.jpg)

28


# Page. 29

![Page Image](https://bcdn.docswell.com/page/VENGXRZMJ8.jpg)

特定のノードからの子孫ノードの取得
SELECT d.*, dpe.path,
CHAR_LENGTH(dpe.path) - CHAR_LENGTH(REPLACE(dpe.path, &#039;/&#039;,
&#039;&#039;)) - 1 depth
FROM department d
JOIN department_path_enumeration dpe USING (department_id)
WHERE dpe.path LIKE CONCAT((
SELECT path
FROM department_path_enumeration
WHERE department_id = 10
), &#039;%&#039;);
depth: ルートノードからの距離
29


# Page. 30

![Page Image](https://bcdn.docswell.com/page/Y79W8MZW73.jpg)

30


# Page. 31

![Page Image](https://bcdn.docswell.com/page/G78N8L1RJD.jpg)

特定のノードの子ノードの取得
SELECT d.*
FROM department d
JOIN department_path_enumeration dpe USING (department_id)
WHERE dpe.path REGEXP CONCAT((
SELECT path
FROM department_path_enumeration
WHERE department_id = 10
), &#039;\\d+/$&#039;);
31


# Page. 32

![Page Image](https://bcdn.docswell.com/page/L7LPRLQ2JR.jpg)

32


# Page. 33

![Page Image](https://bcdn.docswell.com/page/4EM4RM19JW.jpg)

特定のノードの親ノードの取得
SELECT d.*
FROM department d
JOIN department_path_enumeration dpe USING (department_id)
WHERE dpe.path = (
SELECT CASE WHEN path = CONCAT(department_id, &#039;/&#039;) THEN
NULL
ELSE
REGEXP_REPLACE(path, &#039;^(.+/)\\d+/$&#039;, &#039;$1&#039;)
END
FROM department_path_enumeration
WHERE department_id = 10
);
33


# Page. 34

![Page Image](https://bcdn.docswell.com/page/PERWRVL9J9.jpg)

34


# Page. 35

![Page Image](https://bcdn.docswell.com/page/P7XPRZW3JX.jpg)

PROS
子孫/先祖ノードに対するアクセスが容易
更新系操作が容易
35


# Page. 36

![Page Image](https://bcdn.docswell.com/page/37KDR8VNED.jpg)

CONS
パス文字列をアプリケーションコードで管理しなけ
ればならない
正規化されていない(第1正規形でさえない)
参照整合性が保証できない
36


# Page. 37

![Page Image](https://bcdn.docswell.com/page/LJ3R82MZE5.jpg)

3. 入れ子集合(nested sets)
cf. 入れ子区間(nested intervals)
37


# Page. 38

![Page Image](https://bcdn.docswell.com/page/8JDYMZ64JG.jpg)

「入れ子集合」モデル
38


# Page. 39

![Page Image](https://bcdn.docswell.com/page/VEP6RDYV78.jpg)

ツリー管理用のテーブル
CREATE TABLE `department_nested_sets` (
`department_id` int(10) unsigned NOT NULL,
`left` int(11) NOT NULL,
`right` int(11) NOT NULL,
`depth` int(10) unsigned NOT NULL,
PRIMARY KEY (`department_id`),
FOREIGN KEY (`department_id`)
REFERENCES `department` (`department_id`)
ON DELETE CASCADE ON UPDATE RESTRICT
);
left, right: 数直線上の左右の点を表す
depth: ルートノードからの距離(必須ではない)
本体データ用テーブルに含めても良い
39


# Page. 40

![Page Image](https://bcdn.docswell.com/page/27V3R1GRJQ.jpg)

department_nested_sets の初期データ
40


# Page. 41

![Page Image](https://bcdn.docswell.com/page/5JG3M286EL.jpg)

すべてのノードとその階層情報の取得
SELECT d.*, dns.left, dns.right, dns.depth
FROM department d
JOIN department_nested_sets dns USING (department_id);
41


# Page. 42

![Page Image](https://bcdn.docswell.com/page/47Q5RP92EP.jpg)

42


# Page. 43

![Page Image](https://bcdn.docswell.com/page/KE498YXPJ1.jpg)

特定のノードからの子孫ノードの取得
SELECT d.*, dns.left, dns.right, dns.depth
FROM department d
JOIN department_nested_sets dns USING (department_id)
JOIN department_nested_sets dns2 ON dns.left BETWEEN
dns2.left AND dns2.right
WHERE dns2.department_id = 10;
43


# Page. 44

![Page Image](https://bcdn.docswell.com/page/L71K26NXEG.jpg)

44


# Page. 45

![Page Image](https://bcdn.docswell.com/page/G7WDRW4KE2.jpg)

特定のノードの子ノードの取得
SELECT d.*
FROM department d
JOIN department_nested_sets dns USING (department_id)
JOIN department_nested_sets dns2 ON dns.left BETWEEN
dns2.left AND dns2.right
WHERE dns2.department_id = 10
AND dns.depth = (
SELECT depth
FROM department_nested_sets
WHERE department_id = 10
) + 1;
45


# Page. 46

![Page Image](https://bcdn.docswell.com/page/4JZGR52N73.jpg)

46


# Page. 47

![Page Image](https://bcdn.docswell.com/page/YE6YR9V9JV.jpg)

特定のノードの親ノードの取得
SELECT d.*
FROM department d
JOIN department_nested_sets dns USING (department_id)
JOIN department_nested_sets dns2 ON dns2.left BETWEEN
dns.left AND dns.right
WHERE dns2.department_id = 10
AND dns.depth + 1 = (
SELECT depth
FROM department_nested_sets
WHERE department_id = 10
);
47


# Page. 48

![Page Image](https://bcdn.docswell.com/page/GE5G8NDDE4.jpg)

48


# Page. 49

![Page Image](https://bcdn.docswell.com/page/972YK8MM7R.jpg)

PROS
子孫/先祖ノードに対するアクセスが容易
削除操作が容易
49


# Page. 50

![Page Image](https://bcdn.docswell.com/page/DJYGN6XPJM.jpg)

CONS
左右の点の値をアプリケーションコードで管理しな
ければならない
正規化されていない(第1正規形でさえない)
挿入操作が非常に煩雑でコストも高い
「入れ子区間」では改善される
参照整合性が保証できない
50


# Page. 51

![Page Image](https://bcdn.docswell.com/page/V7NGXZ1ME8.jpg)

4. 閉包テーブル(closure table)
51


# Page. 52

![Page Image](https://bcdn.docswell.com/page/YJ9W8Z5WJ3.jpg)

「閉包テーブル」モデル
52


# Page. 53

![Page Image](https://bcdn.docswell.com/page/GJ8N81YRED.jpg)

ツリー管理用のテーブル
CREATE TABLE `department_closure_table` (
`ancestor` int(10) unsigned NOT NULL,
`descendant` int(10) unsigned NOT NULL,
`path_length` int(10) unsigned NOT NULL,
PRIMARY KEY (`ancestor`, `descendant`),
FOREIGN KEY (`ancestor`)
REFERENCES `department` (`department_id`)
ON DELETE CASCADE ON UPDATE RESTRICT,
FOREIGN KEY (`descendant`)
REFERENCES `department` (`department_id`)
ON DELETE CASCADE ON UPDATE RESTRICT
);
ancestor, descendant: 先祖/子孫関係にあるノ
ードの組
path_length: ancestor から descendant まで
の距離(必須ではない)
53


# Page. 54

![Page Image](https://bcdn.docswell.com/page/LJLPRQ42ER.jpg)

department_closure_table の初期データ
54


# Page. 55

![Page Image](https://bcdn.docswell.com/page/47M4R1K9EW.jpg)

すべてのノードとその階層情報の取得
SELECT d.*, COUNT(*) - 1 depth
FROM department d
JOIN department_closure_table dct
ON d.department_id = dct.descendant
GROUP BY dct.descendant;
depth: ルートノードからの距離
MAX(dct.path_length) でも求められる
55


# Page. 56

![Page Image](https://bcdn.docswell.com/page/P7RWRLX9E9.jpg)

56


# Page. 57

![Page Image](https://bcdn.docswell.com/page/PJXPRW63EX.jpg)

特定のノードからの子孫ノードの取得
SELECT d.*, dct.path_length distance, dct2.depth
FROM department d
JOIN department_closure_table dct
ON d.department_id = dct.descendant
JOIN (
SELECT descendant, COUNT(*) - 1 depth
FROM department_closure_table
GROUP BY descendant
) dct2
ON d.department_id = dct2.descendant
WHERE dct.ancestor = 10;
distance: ノード 10 からの距離
depth: ルートノードからの距離
57


# Page. 58

![Page Image](https://bcdn.docswell.com/page/3JKDRV1N7D.jpg)

58


# Page. 59

![Page Image](https://bcdn.docswell.com/page/LE3R8MQZ75.jpg)

特定のノードの子ノードの取得
SELECT d.*
FROM department d
JOIN department_closure_table dct
ON d.department_id = dct.descendant
WHERE dct.ancestor = 10
AND dct.path_length = 1;
59


# Page. 60

![Page Image](https://bcdn.docswell.com/page/8EDYM694EG.jpg)

60


# Page. 61

![Page Image](https://bcdn.docswell.com/page/V7P6RYZVJ8.jpg)

特定のノードの親ノードの取得
SELECT d.*
FROM department d
JOIN department_closure_table dct
ON d.department_id = dct.ancestor
WHERE dct.descendant = 10
AND dct.path_length = 1;
61


# Page. 62

![Page Image](https://bcdn.docswell.com/page/2JV3RGWREQ.jpg)

62


# Page. 63

![Page Image](https://bcdn.docswell.com/page/5EG3M8D67L.jpg)

PROS
子孫/先祖ノードに対するアクセスが容易
更新系操作が容易
参照整合性が保証できる
63


# Page. 64

![Page Image](https://bcdn.docswell.com/page/4JQ5R9127P.jpg)

CONS
他のモデルよりも保持すべきデータが多くなる
64


# Page. 65

![Page Image](https://bcdn.docswell.com/page/K7498XRPE1.jpg)

まとめ
「閉包テーブル」は総合的に優れている
「隣接リスト」は最も素朴(ナイーブ)な設計だがデ
メリットもいくつかある
「経路列挙」
「入れ子集合」は参照整合性が保証で
きない(RDBの強みが犠牲になる)
65


# Page. 66

![Page Image](https://bcdn.docswell.com/page/LJ1K2NQX7G.jpg)

Further Reading
『SQLアンチパターン』
2章 ナイーブツリー（素朴な木）
『理論から学ぶデータベース実践入門』
第10章
グラフに立ち向かう
ツリー（木）
10.4
『Effective SQL』
第10章 階層的なデータ構造
66


# Page. 67

![Page Image](https://bcdn.docswell.com/page/GJWDR4MK72.jpg)

『達人に学ぶDB設計 徹底指南書』
第9章
う
一歩進んだ論理設計 ～SQLで木構造を扱
『プログラマのためのSQLグラフ原論』
What are the options for storing hierarchical data
in a relational database? - Stack Overflow
67


