📨

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
복사

위의 댓글 중 4번에 해당하는 댓글들을 가져오려면 다음과 같이 질의 하면 된다.

code block 에 테스트해볼 수 있는 데이터를 넣어두었으니, 실행해보자

SELECT c.*
FROM Comments AS c
JOIN TreePaths AS t ON c.comment_id = t.descendant
WHERE t.ancestor = 4;
SQL
복사

6번에 해당하는 상위 댓글들을 가져오려면 다음과 같이 질의한다.

SELECT c.*
FROM Comments AS c
JOIN TreePaths AS t ON c.comment_id = t.ancestor
WHERE t.descendant = 6;
SQL
복사

새로운 노드 추가

5의 reply 글을 작성한다 → commend id: 8

8이 8을 참조하는 path 를 만들어 저장하고

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 만 삭제하는 것임을 유의 하자

트리 옮기기

서브트리의 최상위 노드와 그 노드의 자손들을 참조하는 행을 삭제한다.

•

자신을 포함하는 참조는 삭제하지 않도록 한다.

•

위의 6을 자손으로 포함하는 모든 노드의 참조 제거

•

6의 후손을 전체 노드에서 자손으로 포함하는 모든 노드의 참조 제거

•

삭제 대상: (1, 6), (1, 7), (4, 6), (4, 7)

새로운 위치의 조상들과 서브트리의 자손들을 붙인다.

•

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 에서 관리하기

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
복사

각 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
복사

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
복사

상단에 잘 그려진 tree 이미지 를 확인하면 eletronics → portable eletronics → mp3 player → flash 로 옴을 확인할 수 있다.

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 는 예약어가 존재한다.

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
복사

위와 같이 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
복사

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

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
복사

새로운 노드 추가하기

여기서 televisions 과 portable electronics 사이에 새로운 node 를 추가한다고 하면 어떻게 해야 할까?

lock 을 건다.

portable 에 해당하는 모든 node 의 left, right 값이 +2 씩 되어야 하고

원래 portable 의 left 값이 새로운 노드의 left, right 는 left + 1 이 되어야 한다.

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
복사