tree 구조를 mysql 에 저장하기, hierarchy, closure table 을 mysql에 저장하자

태그
Closure table
MySQL
Hierarchy
공개여부
작성일자
2020/09/24

Closure pattern

hierarchy 구조를 저장하는 방법중 그래도 꽤 괜찮은 방법이다.
핵심은 데이터는 데이터대로 저장하는데 데이터 간의 관계(vertex)를 별도의 테이블에 저장하는 방식이다.
그런데 단순히 저장만 하는 것이 아니라 모든 관계를 다 저장한다 parent → child 심지어 자기 자신까지도 저장한다.
대신 두개의 테이블이 필요하다. 다음의 나오는 코드는 SQL antipattern 의 순전한 트리 챕터를 참고했다.
CREATE TABLE Comments ( comment_id SERIAL PRIMARY KEY, author varchar(50) NOT NULL, comment TEXT NOT NULL ); insert into Comments(comment_id, path, author, comment)values(1, '1/', 'Fran', '이 버그의 원인이 뭘까?' ), (2, '1/2/', 'Ollie', '널 포인터 때문인 것 같아'),(3, '1/2/3/', 'Fran', '아니, 그건 확인해봤어.'), (4, '1/4/', 'Kukla', '입력값이 효한지 확인할 필요가 있어'),(5, '1/4/5/', 'Ollie', '그래, 그게 버그야'), (6, '1/4/6/', 'Fran', '그래, 확인하는 코드를 추가해'),(7, '1/4/6/7/', 'Kukla', '수정됐어.');
SQL
쇠파이프 에서 user 에 해당하는 테이블이고
CREATE TABLE TreePaths ( ancestor BIGINT UNSIGNED NOT NULL, descendant BIGINT UNSIGNED NOT NULL, PRIMARY KEY(ancestor, descendant), FOREIGN KEY (ancestor) REFERENCES Comments(comment_id), FOREIGN KEY (descendant) REFERENCES Comments(comment_id) ); insert into TreePaths values (1, 1), (1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(2,2),(2,3),(3,3),(4,4),(4,5),(4,6),(4,7),(5,5),(6,6),(6,7),(7,7);
SQL
mysql-closure-table-hierarchy-save.png
위의 댓글 중 4번에 해당하는 댓글들을 가져오려면 다음과 같이 질의 하면 된다.
code block 에 테스트해볼 수 있는 데이터를 넣어두었으니, 실행해보자
SELECT c.* FROM Comments AS c JOIN TreePaths AS t ON c.comment_id = t.descendant WHERE t.ancestor = 4;
SQL
mysql-closure-table-hierarchy-save2.png
6번에 해당하는 상위 댓글들을 가져오려면 다음과 같이 질의한다.
SELECT c.* FROM Comments AS c JOIN TreePaths AS t ON c.comment_id = t.ancestor WHERE t.descendant = 6;
SQL
mysql-closure-table-hierarchy-save3.png

새로운 노드 추가

1.
5의 reply 글을 작성한다 → commend id: 8
2.
8이 8을 참조하는 path 를 만들어 저장하고
3.
5를 descendant 로 참조하는 모든 행을 복사해 descandant 를 새로운 comment id 8 로 바꾸어 저장한다.
그래야 1 → 4 → 5 → 8 로 path 를 저장한다.
insert into comments(comment_id, author, commend) value (8, 'koko', 'ㅋㅋㅋㅋㅋ'); INSERT INTO TreePaths (ancestor, descendant) SELECT t.ancestor, 8 FROM TreePaths AS t WHERE t.descendant = 5 UNION ALL SELECT 8, 8;
SQL

leaf 노드 삭제

DELETE FROM TreePaths WHERE descendant = 7;
SQL
그냥 해당하는 node 의 path 를 제거한다.

중간 node 삭제

서브트리, 4번을 삭제한다고 가정하면, 4를 descendant 로 가지는 모든 path 와 4의 ancestor 모두를 제거한다.
DELETE FROM TreePaths WHERE descendant IN (SELECT descendant FROM TreePaths WHERE ancestor = 4);
SQL
위 두 과정에서 comment 자체를 삭제하는 것이 아니다. 오로지 path 만 삭제하는 것임을 유의 하자

트리 옮기기

mysql-closure-table-hierarchy-save3.jpg
1.
서브트리의 최상위 노드와 그 노드의 자손들을 참조하는 행을 삭제한다.
자신을 포함하는 참조는 삭제하지 않도록 한다.
위의 6을 자손으로 포함하는 모든 노드의 참조 제거
6의 후손을 전체 노드에서 자손으로 포함하는 모든 노드의 참조 제거
삭제 대상: (1, 6), (1, 7), (4, 6), (4, 7)
2.
새로운 위치의 조상들과 서브트리의 자손들을 붙인다.
CROSS JOIN 문법으로 카테시안 곱을 생성해 모든 노드를 만들어낸다.
생성: (1, 6), (2, 6), (3, 6), (1, 7), (2, 7), (3, 7)

삭제

DELETE FROM TreePaths WHERE descendant IN (SELECT descendant FROM TreePaths WHERE ancestor = 6) AND ancestor IN (SELECT ancestor FROM TreePaths WHERE descendant = 6 AND ancestor != descendant);
SQL

생성

INSERT INTO TreePaths (ancestor, descendant) SELECT supertree.ancestor, subtree.descendant FROM TreePaths AS supertree CROSS JOIN TreePaths AS subtree WHERE supertree.descendant = 3 AND subtree.ancestor = 6;
SQL

개선

pathlength 속성을 추가해 테이블을 개선할 수 있다. 자기 자신에 대한 pathlength 는 0, 자식은 1, 손자는 2 로 설정해둘 수 있다. 책에서는 이렇게 나왔지만, 이건 테이블에 실제 저장하는 값이 아니라 sub query 를 사용해 해결해야 하는 문제가 아닐까 싶다.
SELECT * FROM TreePaths WHERE ancestor = 4 AND path_length = 1;
SQL
이렇게 질의하면 바로 질의가 가능하다
다음 글은 hierarchy 로 검색하다 찾은 글을 이다.
Managing Hierarchical Data in MySQL 100% 그대로 번역하지 않고 이해한 것을 바탕으로 요약 하였으니 꼭 원문을 읽어보는 것을 추천한다.

계층형(hierarchical) 데이터를 mysql 에서 관리하기

mysql-closure-table-hierarchy-save4.png
SELECT * FROM category ORDER BY category_id; +-------------+----------------------+--------+ | category_id | name | parent | +-------------+----------------------+--------+ | 1 | ELECTRONICS | NULL | | 2 | TELEVISIONS | 1 | | 3 | TUBE | 2 | | 4 | LCD | 2 | | 5 | PLASMA | 2 | | 6 | PORTABLE ELECTRONICS | 1 | | 7 | MP3 PLAYERS | 6 | | 8 | FLASH | 7 | | 9 | CD PLAYERS | 6 | | 10 | 2 WAY RADIOS | 6 | +-------------+----------------------+--------+ 10 rows in set (0.00 sec)
SQL
tree 로 select 하는 방법은 self join 을 사용한다. (JPA 보단 jooq, jpql 을 사용 하는 것이 좋겠다.)
SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4 FROM category AS t1 LEFT JOIN category AS t2 ON t2.parent = t1.category_id LEFT JOIN category AS t3 ON t3.parent = t2.category_id LEFT JOIN category AS t4 ON t4.parent = t3.category_id WHERE t1.name = 'ELECTRONICS';
SQL
mysql-closure-table-hierarchy-save5.png
각 row (node) 는 parent id 값을 가지고 있으며, parent id 값이 null 이라면 그 node 는 root 가 된다.

select leaf nodes

SELECT t1.name FROM category AS t1 LEFT JOIN category as t2 ON t1.category_id = t2.parent WHERE t2.category_id IS NULL;
SQL
mysql-closure-table-hierarchy-save6.png
t1 은 데이터가 있는 node 이고, t1 을 parent 로 가지고 있는 node 들을 찾는 것이다.
leaf node 는 가장 밑에 있는 node 이므로, 그 무엇도 parent 로 가지지 않는다. 따라서 t2.parent 가 null 인 (부모로 참조하지 않는 데이터) node 를 가져온다.

select one node path

SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4 FROM category AS t1 LEFT JOIN category AS t2 ON t2.parent = t1.category_id LEFT JOIN category AS t3 ON t3.parent = t2.category_id LEFT JOIN category AS t4 ON t4.parent = t3.category_id WHERE t1.name = 'ELECTRONICS' AND t4.name = 'FLASH';
SQL
mysql-closure-table-hierarchy-save7.png
상단에 잘 그려진 tree 이미지 를 확인하면 eletronics → portable eletronics → mp3 player → flash 로 옴을 확인할 수 있다.
mysql-closure-table-hierarchy-save9.png

nested 모델(join 을 줄일 수 있다)

CREATE TABLE nested_category ( category_id INT AUTO_INCREMENT PRIMARY KEY, name VARCHAR(20) NOT NULL, lft INT NOT NULL, rgt INT NOT NULL );
SQL
INSERT INTO nested_category VALUES(1,'ELECTRONICS',1,20),(2,'TELEVISIONS',2,9),(3,'TUBE',3,4), (4,'LCD',5,6),(5,'PLASMA',7,8),(6,'PORTABLE ELECTRONICS',10,19),(7,'MP3 PLAYERS',11,14),(8,'FLASH',12,13), (9,'CD PLAYERS',15,16),(10,'2 WAY RADIOS',17,18);
SQL
SELECT * FROM nested_category ORDER BY category_id; +-------------+----------------------+-----+-----+ | category_id | name | lft | rgt | +-------------+----------------------+-----+-----+ | 1 | ELECTRONICS | 1 | 20 | | 2 | TELEVISIONS | 2 | 9 | | 3 | TUBE | 3 | 4 | | 4 | LCD | 5 | 6 | | 5 | PLASMA | 7 | 8 | | 6 | PORTABLE ELECTRONICS | 10 | 19 | | 7 | MP3 PLAYERS | 11 | 14 | | 8 | FLASH | 12 | 13 | | 9 | CD PLAYERS | 15 | 16 | | 10 | 2 WAY RADIOS | 17 | 18 | +-------------+----------------------+-----+-----+
SQL
여기서 column 명 lft 는 left 이다. 하지만, mysql 에서 left, right 는 예약어가 존재한다.
mysql-closure-table-hierarchy-save12.png

leaf node 검색

SELECT name FROM nested_category WHERE rgt = lft + 1;
SQL
leaf node 의 특징은 right = left + 1 이 성립된다.

Single path 검색

SELECT parent.name FROM nested_category AS node, nested_category AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt AND node.name = 'FLASH' ORDER BY parent.lft;
SQL
flash node 의 left 값을 n으로 가정할 때 parent.left < n < parent.right 인 parent.node 를 반환한다.
nested 인 이유는 root 가 모든 node 의 left, right 값을 root.left < 모든 노드의 left, right < root.right 가 성립하기 때문이다.

node 의 depth 계산하기

SELECT node.name, (COUNT(parent.name) - 1) AS depth FROM nested_category AS node, nested_category AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt GROUP BY node.name, node.lft ORDER BY node.lft;
SQL
mysql-closure-table-hierarchy-save9.png
위와 같이 depth 값을 알아낸다면, indent 를 추가하여 반환하는 것도 query 를 통해서 실행할 수 있다.
SELECT CONCAT( REPEAT(' ', COUNT(parent.name) - 1), node.name) AS name FROM nested_category AS node, nested_category AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt GROUP BY node.name, node.lft ORDER BY node.lft;
SQL
mysql-closure-table-hierarchy-save13.png

특정 지점의 하위 노드를 모두 가져오기

root 를 제외하고 node 를 찾으면 query 의 결과가 깨지는데 이러한 문제를 해결하기 위해 sub_parent 라는 테이블을 임의로 만들어 join 한다.
SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth FROM nested_category AS node, nested_category AS parent, nested_category AS sub_parent, ( SELECT node.name, (COUNT(parent.name) - 1) AS depth FROM nested_category AS node, nested_category AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt AND node.name = 'PORTABLE ELECTRONICS' GROUP BY node.name, node.lft ORDER BY node.lft )AS sub_tree WHERE node.lft BETWEEN parent.lft AND parent.rgt AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt AND sub_parent.name = sub_tree.name GROUP BY node.name, node.lft, sub_tree.depth ORDER BY node.lft;
SQL

새로운 노드 추가하기

mysql-closure-table-hierarchy-save11.png
여기서 televisions 과 portable electronics 사이에 새로운 node 를 추가한다고 하면 어떻게 해야 할까?
1.
lock 을 건다.
2.
portable 에 해당하는 모든 node 의 left, right 값이 +2 씩 되어야 하고
3.
원래 portable 의 left 값이 새로운 노드의 left, right 는 left + 1 이 되어야 한다.
4.
lock 을 푼다.
LOCK TABLE nested_category WRITE; SELECT @myRight := rgt FROM nested_category // 9 반환(television 의 right 값) WHERE name = 'TELEVISIONS'; UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myRight; UPDATE nested_category SET lft = lft + 2 WHERE lft > @myRight; INSERT INTO nested_category(name, lft, rgt) VALUES ('GAME CONSOLES', @myRight + 1, @myRight + 2); UNLOCK TABLES;
SQL

노드 삭제

추가와 맞찬가지로 node 가 제거되는 데는 lgt, lft -2 가 필요하다
LOCK TABLE nested_category WRITE; SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1 FROM nested_category WHERE name = 'GAME CONSOLES'; DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight; UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight; UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight; UNLOCK TABLES;
SQL
Made with 💕 and Oopy