閉包テーブル（closure table）でツリー構造を表現する

公開日 2022.2.26
更新日 2022.2.28

カテゴリ：MySQL
タグ：MySQL,RDBMS

「SQL アンチパターン」という書籍を読んでいて、ナイーブツリー（素朴な木）という、ツリー構造（再帰的な階層構造）の表現について書かれた章があり面白かったので試してみました。

隣接リスト（adjacency list）
閉包テーブル（closure table）
ツリー構造のしやすさ

隣接リスト（adjacency list）

よくある（んだけどツラいよねっていう）パターンとして「隣接リスト」というものが紹介されていました。これは、コメントのテーブルに親を識別するための parent_id をカラムに追加するというものです。

DDL

create table comments
(
    comment_id   bigint unsigned auto_increment primary key,
    parent_id    bigint unsigned null,
    bug_id       bigint unsigned not null,
    author       bigint unsigned not null,
    comment_date datetime        not null,
    comment      text            not null,
    constraint comments_author_foreign
foreign key (author) references accounts (account_id),
    constraint comments_bug_id_foreign
foreign key (bug_id) references bugs (bug_id),
    constraint comments_parent_id_foreign
foreign key (parent_id) references comments (comment_id)
)

たしかにお手軽な方法ですが SELECT がつらい。

自身のコメントと、子を 1 件だけ使いたいのであれば join しても取り回しはできます。

-- コメントと直近の子を取得
SELECT
    c1.*,
    c2.*
FROM comments  c1
LEFT JOIN comments c2 ON c1.parent_id=c2.comment_id;

ですが、階層構造が無制限であることを考えると join が増えるだけでなく、その結合数を制御することは困難です。

-- この流れで直近の子から更に子を取ろうとすると JOIN が増えていく
SELECT 
    c1.*,
    c2.*,
    c3.*
FROM comments  c1
LEFT JOIN comments c2 ON c1.parent_id=c2.comment_id
LEFT JOIN comments c3 ON c2.parent_id=c3.comment_id;

併せて結合は列が増えるので取り回しの効率も悪く、結局該当コメントを全件、行として取ってくるという選択に落ち着くことになりそうです。（そして comments テーブルに parent_id がある意味とは..という気持ちになる）

-- 該当バグのコメントを全て取得
SELECT
    *
FROM comments
WHERE bug_id = 1;

ちなみに、INSERT は簡単。そして子孫関係の更新も簡単。parent_id を更新すれば良いので、コメントの付け替えは容易です。

ただ、書籍にも書いてありましたが、私は隣接リストの最大に辛い点は削除だなと思いました。

外部キー制約を設定しているので、好き勝手にコメントを削除することができません。少なくとも削除したいコメントの子孫として紐付いているコメントは全て削除する必要があり、しかも制約のおかげで最下層から順に削除していかなければなりません。

もし指定のコメントだけを削除したい場合は、削除したいコメントの子の parent_id を別のコメントに紐付けてからでないと指定のコメントのみを削除できません。（指定のコメントだけを削除して、その子らを昇格させたい場合は親の comment_id に付け替えれば良いので問題は無い。）

色々とツラいのは体験できました。

閉包テーブル（closure table）

書籍では隣接リストに変わるパターンの提案として、3 つのパターンが示されていました。その中で個人的に最もしっくりきたのは「閉包テーブル」です。

閉包テーブルは、comments テーブルには子孫関係の情報を持たせず、子孫関係の情報は別のテーブルに持たせます。

DDL

create table comments
(
    comment_id   bigint unsigned auto_increment
        primary key,
    bug_id       bigint unsigned not null,
    author       bigint unsigned not null,
    comment_date datetime        not null,
    comment      text            not null,
    constraint comments_author_foreign
        foreign key (author) references accounts (account_id),
    constraint comments_bug_id_foreign
        foreign key (bug_id) references bugs (bug_id)
);

-- comments の子孫関係を表現する
create table tree_paths
(
    ancestor   bigint unsigned not null,
    descendant bigint unsigned not null,
    primary key (ancestor, descendant),
    constraint tree_paths_ancestor_foreign
        foreign key (ancestor) references comments (comment_id),
    constraint tree_paths_descendant_foreign
        foreign key (descendant) references comments (comment_id)
);

それぞれのコメントレコードに関して、その親と子の関係を収録しているのが tree_paths のレコードです。

階層構造の最上階、最も親のコメントに関しては自身が子孫のどちらにも自身を指定しているようなレコードになっています。

こちらも INSERT は簡単。子孫関係の更新も、対象コメントの親や子は簡単に判別できるので、こちらもコメントの付け替えは容易です。

隣接リストでツラみポイントであったコメントの削除はどうかというと、tree_path から該当のレコードを削除すればその子孫も含め構造から切り離されるため、制約を受けることなく容易に行うことができました。さらに切り離したコメント以下の子孫関係や、コメントレコード自体も全て残るため、その後の処遇も柔軟に行えそうです。

コメントの削除時に子孫のコメントたちを昇格させるのも簡単で、子レコードの親カラムの値を変更してあげるだけです。

set @DELETE_COMMENT_ID = 4;
select @ANCESTOR := `ancestor` as `id` from `tree_paths` where `descendant` = @DELETE_COMMENT_ID;

-- 削除対象のコメントの子らを一段上へ昇格させる
update tree_paths
set ancestor = @ANCESTOR
where ancestor = @DELETE_COMMENT_ID
and descendant in (
select x.id from (
select descendant as id from tree_paths where ancestor = @DELETE_COMMENT_ID
    ) as x
);

-- 削除対象コメントの関係を削除
delete from tree_paths
where ancestor = @ANCESTOR
and descendant = @DELETE_COMMENT_ID;

扱いやすさもそうですが、テーブルの表現として、コメントそのものとそれらの関係性が分離されているのはとてもシンプルで良いなと思いました。

ツリー構造のしやすさ

最後に、折角ツリー構造の話なので階層構造も作ってみます。

閉包テーブルと PHP を使ってツリー構造にしてみます。

select
    comments.comment_id,
    comments.comment,
    comments.comment_date,
    accounts.account_name,
    tree_paths.ancestor,
    tree_paths.descendant
from comments
inner join tree_paths on comments.comment_id = tree_paths.descendant
inner join accounts on comments.author = accounts.account_id
where comments.bug_id = 1;

この結果が array in stdClass で返ってくるとして、再帰関数を噛ませて階層構造を作ります。

/** @var object[] $commentList */
$addChild = function (array $comments, array &$treeData) use ($commentList, &$addChild)  {
/** @var object $comment */
    foreach ($comments as $comment) {
$treeData[$comment->comment_id] = (array)$comment;

        $children = array_filter(
$commentList,
            fn (object $item) => $item->ancestor === $comment->comment_id && $item->ancestor !== $item->descendant
        );

        if (empty($children)) {
continue;
        }

$treeData[$comment->comment_id]['child'] = [];
        $addChild($children, $treeData[$comment->comment_id]['child']);
    }
$treeData = array_values($treeData);
};

// 起点となる最上階のコメント
$parentItems = array_filter($commentList, fn (object $comment) => $comment->ancestor === $comment->descendant);

$treeData = [];
// 子孫を付与
$addChild($parentItems, $treeData);

return $treeData;

RDB への問い合わせ結果は行列の表なのでツリー構造にすること自体はアプリケーション（プログラム）側で行う想定のため、そこのコストに関しては隣接リストだろうが閉包テーブルだろうがあまり変わらないかなとは思いました。

まとめ

書籍では隣接リストに変わるパターンとして「経路列挙（Path Enumeration）」「入れ子集合（Nested Set）」「閉包テーブル（closure table）」の 3 つのパターンが紹介されていました。

隣接リストを含め、全部でこの 4 パターンの良いところやツラい点、良いけどトレードオフになる点などが紹介されていたので、書籍の中でも閉包テーブルはエレガントだとしていたのはありつつも、どれを選択するかは実現するものと照らし合わせてメンテナンスしやすいものを適材適所判断していければ良いなと感じました。（まあでも個人の見解では優勝は閉包テーブルかな）

「SQL アンチパターン」という書籍では沢山のアンチパターンとその解決策が紹介されていて読んでいてとても勉強になるしテーブル設計上の視野を広げてくれる良書だと思うので、これからもいつでも手に取れるところに置いておきたいと思います。

閉包テーブル（closure table）でツリー構造を表現する

Contents

隣接リスト（adjacency list）

閉包テーブル（closure table）

ツリー構造のしやすさ

まとめ

Author