ツリー構造のデータをRDBで扱う

例

カテゴリー

---

考慮する事項

• ツリー全体の参照（ソート）
• ツリーの一部の参照（ソート）
• 挿入・更新
• 削除

---

データをどのように定義するか考える

古くから推奨されているのは、親のIDを定義するパターン。
隣接リストと呼ばれる。

---

• テーブル定義

create table category (
  category_id int(11) not null auto_increment,
  name varchar(40) not null,
  parent_id int(11),
  primary key (category_id),
  key parent_id_idx (parent_id)
    FOREIGN KEY (parent_id) 
    REFERENCES parent(category_id)
) 

---

参照の問題

階層が深くなると、一度のクエリで取得するのが難しくなる。

select c1.*, c2.*, c3.*
from category c1 left outer join category c2
  on c1.category_id = c2.parent_id
left outer join category c3
  on c2.category_id = c3.parent_id
where c1.category_id = 2
;

アプリで処理する場合も、データが増えるほどクエリの発行回数が増えてしまう。

select category_id from category where name = 'アパレル'; -- 5
select category_id from category where parent_id = 5; -- 7, 8
select category_id from category where parent_id = 7; -- なし
select category_id from category where parent_id = 8; -- なし

---

挿入・更新・削除

挿入・更新は容易だが、削除は末端ノード以外だと面倒になる。

insert into category values (9, 'トートバッグ', 6);
update category set parent_id = 2 where cateogory_id = 5;

-- ノードの一部分を子ノードのも含めて削除
select category_id from category where name = 'アパレル'; -- 5
select category_id from category where parent_id = 5; -- 7, 8
select category_id from category where parent_id = 7; -- なし
select category_id from category where parent_id = 8; -- なし
-- 参照整合性制約のため、子のデータから順番に削除する必要がある
delete from cateogry where category_id in (7, 8);
delete from cateogry where category_id in (5);

ただし、 on delete cascade 修飾子で自動削除も可能。

• 末端でないノードを削除。ただし、子ノードは残す

select parent_id from category where name = 'アパレル'; -- 5
select category_id from category where parent_id = 5; -- 7, 8
update category set parent_id = 2 where cateogory_id in (7, 8);
delete from category where category_id = 5;

---

隣接リストの特徴

• 階層が増えると一度のクエリで取得が困難になる
• 削除の時など、やりたいことに対して、クエリやアプリケーション側のコードが複雑になりやすい

隣接リストを用いたツリー構造は、ナイーブツリーと呼ばれるアンチパターン。（ただしDBの実装によって例外あり）

---

解決策

代わりのツリーモデルを使用する。
ただし、どの構造も隣接リストに比べると複雑なので、事前に比較検討すること。

---

経路列挙

隣接リストの親ノードの取得の問題を解決するデータモデル。
親ノードの経路（ディレクトリパス /usr/local/path/ のようなもの）を表す文字列をデータとして含める。

• テーブル定義

create table category (
  category_id int(11) not null auto_increment,
  name varchar(40) not null,
  path varchar(1000),
  primary key (category_id),
  key parent_id_idx (parent_id)
) 

---

参照

-- サブツリー全体を取得するときのクエリ
select * from category where path like '1/3/%'

-- 親のノードを取得するときのクエリ
select * from category where '1/3/5/8' like concat(path, '%')

挿入・更新・削除

-- 挿入は親のパスをコピーし、新規のノードに付与する
insert into category values (9, 'トートバッグ', '1/3/');

-- 親ノードの更新は、一度に取得せずに、先に対象を取得してからパスをアプリケーション側で作成してから更新する。
-- 一時的に整合性が取れない状態が発生してしまう。
select * from category where name = 'アパレル'; -- 5
-- パスの値はアプリ側で生成
select category_id from category where path like concat('1/3/5', '/', '%')); -- 7, 8
update category set path = '1/2/' where category_id = 5;
update category set path = '1/2/5' where category_id in (7, 8);

-- 子ノード全体の削除は参照時の検索条件がそのまま流用できる
delete from category where path like '1/3/%';

---

経路列挙のまとめ

• 子やツリーに対しての参照は容易
• 挿入・削除も難しくはないが、参照整合性を維持することができない

---

閉包テーブル

直接の親子関係だけではなく、ツリー全体のパスを別テーブルに格納する方式。

create table category (
  category_id int(11) not null auto_increment,
  name varchar(40) not null,
  primary key (category_id),
  key parent_id_idx (parent_id)
);

create table category_tree(
  category_tree_id int(11) not null auto_increment,
  ancestor_category_id int(11) not null,
  descendent_category_id int(11) not null,
  primary key tree_id,
  key ancestor_category_id_idx (ancestor_category_id),
    FOREIGN KEY (ancestor_category_id) 
    REFERENCES category(category_id),
  key descendent_category_id_idx (descendent_category_id),
    FOREIGN KEY (descendent_category_id) 
    REFERENCES category(category_id)
);

閉包テーブルでは、 category 自身にツリー構造を格納するのではなく、 category_tree にツリー情報を格納する。
また、treeには自分自身を参照する行も追加する。

---

---

参照

-- 子のツリー全体を取得するSQL
select c.* from category c inner join category_tree ct on c.category_id = ct.descendent_category_id
where ct.ancestor_category_id = 3;

-- 子のツリー全体を取得するSQL
select c.* from category c inner join category_tree ct on c.category_id = ct.ancestor_category_id
where ct.descendent_category_id = 3;

挿入

-- バッグ（category_id = 6）の子にトートバッグを挿入。
-- categoryにトートバッグを追加後、バッグの全ての親ノードにトートバッグとのひも付けと自己参照する行をcategory_treeに挿入
insert into category values (9, 'トートバッグ');
insert into category_tree (ancestor_category_id, descendent_category_id)
values select ct.ancestor_category_id, 9 -- トートバッグのid
  from category_tree ct where ct.category_id = 6 -- バッグのid
union all select 9, 9;

削除

-- 末端のノードを削除
-- 子孫のcategory_idに削除対象のcategory_idを指定して削除し、その後category自身を削除する
delete from category_tree where descendent_category_id = 4;
delete from category where category_id = 4; -- テーブルに`ON DELETE CASCADE` 指定をしておくとこの操作も不要になる

-- サブツリー全体の削除
-- 削除対象のカテゴリを子孫に持つカテゴリと、削除対象のカテゴリの子孫を子孫として参照する全ての行を削除
delete from category_tree
where descendent_category_id (
  select x.id from (
    select descendent_category_id id from category_tree where ancestor_category_id = 5) x);

---

閉包テーブルのまとめ

• 子やツリーに対しての参照は容易で、インデックスも効かせやすい
• 挿入・削除も難しくないし、参照整合性を保つこともできる
• そもそもの構造が複雑であるのと、データの容量が増えやすい

---

まとめ

• ツリー構造のデータを作る時、
  • 親のIDを持つだけの隣接リストはアンチパターンとなることがある。ただしDBの実装によっては問題なくなることもある。
  • 経路列挙は参照や挿入・削除も容易だが、参照整合性が維持できない
  • 閉包テーブルは参照や挿入・削除も容易だが、参照整合性が維持できるが、構造が複雑でデータが増えやすい