82
97

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

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

Last updated at Posted at 2018-12-10
1 / 17

カテゴリー

スクリーンショット 2018-03-24 1.18.56.png

考慮する事項

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

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

古くから推奨されているのは、親の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)
) 
スクリーンショット 2018-03-24 2.16.03.png

参照の問題

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

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)
) 
スクリーンショット 2018-03-24 3.41.07.png

参照


-- サブツリー全体を取得するときのクエリ
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には自分自身を参照する行も追加する。

スクリーンショット 2018-03-24 15.17.47.png
スクリーンショット 2018-03-24 11.11.14.png

参照

-- 子のツリー全体を取得する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の実装によっては問題なくなることもある。
    • 経路列挙は参照や挿入・削除も容易だが、参照整合性が維持できない
    • 閉包テーブルは参照や挿入・削除も容易だが、参照整合性が維持できるが、構造が複雑でデータが増えやすい
82
97
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
82
97

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?