特徴

リレーショナルデータベースでツリー構造のテーブルを表現するための方法の一つ。
ツリー構造とは階層構造になっているもので、リレーショナルデータベースで表そうとすると検索や更新の処理が複雑になったりパフォーマンスが悪化しやすくなる。

経路列挙モデルでは階層をノードまでのパスとして保存することでデータを表現する。(例: /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    |
+----+--------+-------------+

マッスル・メモリー

筋肉エンジニアのブログ

【DB, MySQL】経路列挙モデルを用いたテーブル

特徴