特徴
リレーショナルデータベースでツリー構造のテーブルを表現するための方法の一つ。
ツリー構造とは階層構造になっているもので、リレーショナルデータベースで表そうとすると検索や更新の処理が複雑になったりパフォーマンスが悪化しやすくなる。
経路列挙モデルでは階層をノードまでのパスとして保存することでデータを表現する。(例: /1/2/3/
)
+
| id | path | name |
+
| 1 | 1/ | Books |
| 2 | 1/2/ | Programming |
| 3 | 1/2/3/ | Network |
| 4 | 1/2/4/ | Database |
| 5 | 1/2/4/5/ | MySQL |
| 6 | 1/2/4/6/ | OracleSQL |
| 11 | 1/2/4/11/ | PostgreSQL |
+
メリット
- パスとして保存されているので直感的で理解しやすい
- ノード自身のレコードに親子関係が含まれているので検索しやすい
- パスはテーブルで一意になるためユニークインデックスによる検索が可能
デメリット
- パスに主キーを使うとパスの文字列が長くなってしまう
- 更新が複雑になる
どのような場合に採用するか
更新が少なく大量のデータの高速な検索が必要な場合に採用すると良い。
データの操作
準備
create
database test_db;
use
test_db;
create table categories
(
id integer not null,
path text,
name varchar(20) not null,
primary key (id)
);
desc categories;
+
| Field | Type | Null | Key | Default | Extra |
+
| id | int | NO | PRI | NULL | |
| path | text | YES | | NULL | |
| name | varchar(20) | NO | | NULL | |
+
insert into categories
(id, path, name)
values
(1, '1/', 'Books'),
(2, '1/2/', 'Programming'),
(3, '1/2/3/', 'Network'),
(4, '1/2/4/', 'Database'),
(5, '1/2/4/5/', 'MySQL'),
(6, '1/2/4/6/', 'OracleSQL'),
(11, '1/2/4/11/', 'PostgreSQL');
select *
from categories;
+
| id | path | name |
+
| 1 | 1/ | Books |
| 2 | 1/2/ | Programming |
| 3 | 1/2/3/ | Network |
| 4 | 1/2/4/ | Database |
| 5 | 1/2/4/5/ | MySQL |
| 6 | 1/2/4/6/ | OracleSQL |
| 11 | 1/2/4/11/ | PostgreSQL |
+
ルートを求める
pathに主キーを使っている場合は区切り文字を削除した文字列とキーが同じになる条件で検索する。
この場合はpathから'/'を取り除いたものが主キーと一致するレコードを取得。
select *
from categories
where id = replace(path, '/', '');
+
| id | path | name |
+
| 1 | 1/ | Books |
+
リーフを求める
自分のpathが他で使われていないレコードがリーフに当たる。
例えば、Booksのpathは'1/'だが、これは全てのレコードで使われている。
またDatabaseの'1/2/4'もMySQLとOracleSQLで使われている。
なのでその逆の"自分のpathが使われていない"を条件する。
select *
from categories parent
where not exists(
select *
from categories children
where children.path like concat(parent.path, '_%')
);
+
| id | path | name |
+
| 3 | 1/2/3/ | Network |
| 5 | 1/2/4/5/ | MySQL |
| 6 | 1/2/4/6/ | OracleSQL |
| 11 | 1/2/4/11/ | PostgreSQL |
+
ノードの深さ求める
深さを求めるには区切り文字数を数えればよい。
区切り文字の数を数えるには、
(pathの文字列の長さ - 区切り文字を削除した文字列の長さ)
例えば、PostgreSQLの場合
1/2/4/11/の9文字から12411の5文字を引いた4文字になる。
select *,
length(path) - length(replace(path, '/', '')) as depth
from categories;
+
| id | path | name | depth |
+
| 1 | 1/ | Books | 1 |
| 2 | 1/2/ | Programming | 2 |
| 3 | 1/2/3/ | Network | 3 |
| 4 | 1/2/4/ | Database | 3 |
| 5 | 1/2/4/5/ | MySQL | 4 |
| 6 | 1/2/4/6/ | OracleSQL | 4 |
| 11 | 1/2/4/11/ | PostgreSQL | 4 |
+
ノードを追加する
リーフを追加する場合はどの親の配下につけるかさえわかればよい。
リーフではなく中間に新しいノードを追加する場合、新しく追加したノードとそのノードを除いたもので更新をかける必要がある。
name = 'Database'の下に新しいノードを追加して'Database'についていたノードを追加した子のノードにする場合、
insert into categories (id, path, name)
select 7, concat(subquery.path, '7/'), 'SQL'
from (select path from categories where name = 'Database') as subquery;
select *
from categories;
+
| id | path | name |
+
| 1 | 1/ | Books |
| 2 | 1/2/ | Programming |
| 3 | 1/2/3/ | Network |
| 4 | 1/2/4/ | Database |
| 5 | 1/2/4/5/ | MySQL |
| 6 | 1/2/4/6/ | OracleSQL |
| 7 | 1/2/4/7/ | SQL |
| 11 | 1/2/4/11/ | PostgreSQL |
+
update categories
set path = replace(path, '1/2/4/', '1/2/4/7/')
where path like '1/2/4/%'
and path <> '1/2/4/'
and path <> '1/2/4/7/';
select *
from categories;
+
| id | path | name |
+
| 1 | 1/ | Books |
| 2 | 1/2/ | Programming |
| 3 | 1/2/3/ | Network |
| 4 | 1/2/4/ | Database |
| 5 | 1/2/4/7/5/ | MySQL |
| 6 | 1/2/4/7/6/ | OracleSQL |
| 7 | 1/2/4/7/ | SQL |
| 11 | 1/2/4/7/11/ | PostgreSQL |
+
ノードを削除する
特定のノードとその配下のノードを削除する場合は特定のノードのpathをlikeの条件にして削除する。
delete
from categories
where path like '1/2/4/7/%';
select *
from categories;
+
| id | path | name |
+
| 1 | 1/ | Books |
| 2 | 1/2/ | Programming |
| 3 | 1/2/3/ | Network |
| 4 | 1/2/4/ | Database |
+