계층형 테이블 구조 및 쿼리

참고: 

원문: http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

구글 번역문: http://hmjkor.tistory.com/472

계층적 데이터 처리를 위해 검색해본 결과 참고 사이트 를 발견하게 됨.

조직도 와 같은 구조의 데이터를 테이블에 넣고 단순히 부모와 자식간 형태로만 저장 하려고 하였으나, 쿼리를 할때마다 순환을 해야 하기 때문에 많은 소요 시간이 필요하게 된다.

단순히 부모와 자식간 관계만 있을 경우의 테이블 구조와 query:

CREATE TABLE nav_map(
  id INT AUTO_INCREMENT PRIMARY KEY ,
  name VARCHAR(50),
  pid INT
);
ALTER TABLE nav_map AUTO_INCREMENT=1;
INSERT INTO nav_map VALUES
  (1,'CEO',  0),
  (2,'개발부서', 1),
  (3,'경영부서', 1),
  (4,'서버개발팀', 2),
  (5,'앱 개발팀', 2),
  (6,'웹 개발팀', 2),
  (7,'회계 팀', 3),
  (8,'재무 팀', 3),
  (9,'서버개발자1', 4),
  (10,'서버개발자2', 4),
  (11,'앱 개발자1', 5),
  (12,'앱 개발자2', 5),
  (13,'웹 개발자1', 6),
  (14,'웹 개발자2', 6),
  (15,'회계사1', 7),
  (16,'재무사1', 8);

- 앱개발자1 에 대한 전체 경로를 가져오기 위해서는 아래와 같이 자체 조인을 해야함.

SELECT t1.name as lev1,t2.name as lev2, t3.name as lev3,t4.name as lev4 from nav_map as t1
LEFT JOIN nav_map as t2 on t2.pid = t1.id
LEFT JOIN nav_map as t3 on t3.pid = t2.id
LEFT JOIN nav_map as t4 on t4.pid = t3.id
WHERE t1.name = 'CEO' AND t4.name = '앱 개발자1';

결과:

|lev1 | lev2   | lev3    | lev4     |
| CEO | 개발부서 | 앱 개발팀  | 앱 개발자1 |

- 전체 팀원 (leaf node 가 됨)들을 가져오자.

SELECT t1.name FROM nav_map AS t1 
LEFT JOIN nav_map as t2 ON t1.id = t2.pid WHERE t2.id IS NULL

   

현 구조에서의 한계는 모든 계층에서 하나의 자체 조인이 필요하며, 조인수가 증가할 때마다 성능이 저하 된다.


참고 글에서는 해당 문제점에 대해 Nested Set Model 방법으로 접근하고자 함.
CEO 는 개발부서 뿐만 아니라 경영부서 이하를 포함 하는 형태이다.(그림에는 추가되지 않았음)


위의 형태를 트리 형태로 표시하면 아래와 같다.
참고로 개발팀까지만 트리 형태로 표현 하였다.


노드의 중첩을 표현하기 위해 left , right 값을 사용하여 테이블에서 해당 계층구조를 나타내도록 한다.
left , right 값을 붙인 이유는 트리의 전위순회 (pre-order traversal) 를 사용하기 위함이다.
전위 순회: 
root -> left node ->  right node 를 방문 하는것, root 가 가장 먼저 나온다.

트리 형태로 데이터 테이블을 구성하고 데이터를 추가,삭제, 검색 해보도록 한다.
CREATE TABLE nav_map(
  id INT AUTO_INCREMENT PRIMARY KEY ,
  name VARCHAR(50),
  lft INT,
  rgt INT
);
DELETE from nav_map;
ALTER TABLE nav_map AUTO_INCREMENT=1;


#CEO 추가 (최상위 root 노드 추가)
#한개 노드만 존재 하므로 left = 1, right = 2 가 된다
INSERT INTO nav_map VALUES (1,'CEO',1,2);

#방법
#부모가 될 노드의 정보를 가져온다
#현재 테이블의 right 값을 부모가 될 노드의 left 값보다 큰 값들에 대해 2 자리씩 증가 시켜준다.
#마찬가지로 left 값을 부모가 될 노드의 left 값보다 큰 값들에 대해 2 자리씩 증가 시켜준다.
#추가하려는 노드의 left 값은 부모 노드의 left + 1 , right 값은 부모노드의 left+2

#CEO 하위로 하나씩 추가해보도록 한다.

# CEO 노드 하위에 개발 부서 추가하기 ----- 1
SELECT @myLeft := lft FROM nav_map
WHERE name = 'CEO';
UPDATE nav_map SET rgt = rgt + 2 WHERE rgt > @myLeft;
UPDATE nav_map SET lft = lft + 2 WHERE lft > @myLeft;
INSERT INTO nav_map(name, lft, rgt) VALUES('개발부서', @myLeft + 1, @myLeft + 2);

# CEO 노드 하위에 경영부서 추가하기 ----- 2
SELECT @myLeft := lft FROM nav_map
WHERE name = 'CEO';
UPDATE nav_map SET rgt = rgt + 2 WHERE rgt > @myLeft;
UPDATE nav_map SET lft = lft + 2 WHERE lft > @myLeft;
INSERT INTO nav_map(name, lft, rgt) VALUES('경영부서', @myLeft + 1, @myLeft + 2);

#개발부서 하위에 웹 개발팀 추가하기 ------ 3
SELECT @myLeft := lft FROM nav_map
WHERE name = '개발부서';
UPDATE nav_map SET rgt = rgt + 2 WHERE rgt > @myLeft;
UPDATE nav_map SET lft = lft + 2 WHERE lft > @myLeft;
INSERT INTO nav_map(name, lft, rgt) VALUES('웹 개발팀', @myLeft + 1, @myLeft + 2);

#개발부서 하위에 앱 개발팀 추가하기 ------ 4
SELECT @myLeft := lft FROM nav_map
WHERE name = '개발부서';
UPDATE nav_map SET rgt = rgt + 2 WHERE rgt > @myLeft;
UPDATE nav_map SET lft = lft + 2 WHERE lft > @myLeft;
INSERT INTO nav_map(name, lft, rgt) VALUES('앱 개발팀', @myLeft + 1, @myLeft + 2);

#개발부서 하위에 서버 개발팀 추가하기 ------ 5
SELECT @myLeft := lft FROM nav_map
WHERE name = '개발부서';
UPDATE nav_map SET rgt = rgt + 2 WHERE rgt > @myLeft;
UPDATE nav_map SET lft = lft + 2 WHERE lft > @myLeft;
INSERT INTO nav_map(name, lft, rgt) VALUES('서버 개발팀', @myLeft + 1, @myLeft + 2);

#웹 개발팀에 웹 개발자1 추가하기 ------ 6
SELECT @myLeft := lft FROM nav_map
WHERE name = '웹 개발팀';
UPDATE nav_map SET rgt = rgt + 2 WHERE rgt > @myLeft;
UPDATE nav_map SET lft = lft + 2 WHERE lft > @myLeft;
INSERT INTO nav_map(name, lft, rgt) VALUES('웹 개발자1', @myLeft + 1, @myLeft + 2);

#앱 개발팀에 앱 개발자1 추가하기 ------ 7
SELECT @myLeft := lft FROM nav_map
WHERE name = '앱 개발팀';
UPDATE nav_map SET rgt = rgt + 2 WHERE rgt > @myLeft;
UPDATE nav_map SET lft = lft + 2 WHERE lft > @myLeft;
INSERT INTO nav_map(name, lft, rgt) VALUES('앱 개발자1', @myLeft + 1, @myLeft + 2);

#서버 개발팀에 서버 개발자1 추가하기 ------ 8
SELECT @myLeft := lft FROM nav_map
WHERE name = '서버 개발팀';
UPDATE nav_map SET rgt = rgt + 2 WHERE rgt > @myLeft;
UPDATE nav_map SET lft = lft + 2 WHERE lft > @myLeft;
INSERT INTO nav_map(name, lft, rgt) VALUES('서버 개발자1', @myLeft + 1, @myLeft + 2);

#경영부서에 회계팀 추가하기 ------ 9
SELECT @myLeft := lft FROM nav_map
WHERE name = '경영부서';
UPDATE nav_map SET rgt = rgt + 2 WHERE rgt > @myLeft;
UPDATE nav_map SET lft = lft + 2 WHERE lft > @myLeft;
INSERT INTO nav_map(name, lft, rgt) VALUES('회계팀', @myLeft + 1, @myLeft + 2);

#경영부서에 재무팀 추가하기 ------ 10
SELECT @myLeft := lft FROM nav_map
WHERE name = '경영부서';
UPDATE nav_map SET rgt = rgt + 2 WHERE rgt > @myLeft;
UPDATE nav_map SET lft = lft + 2 WHERE lft > @myLeft;
INSERT INTO nav_map(name, lft, rgt) VALUES('재무팀', @myLeft + 1, @myLeft + 2);


#회계팀에 회계사 추가하기 ------ 11
SELECT @myLeft := lft FROM nav_map
WHERE name = '회계팀';
UPDATE nav_map SET rgt = rgt + 2 WHERE rgt > @myLeft;
UPDATE nav_map SET lft = lft + 2 WHERE lft > @myLeft;
INSERT INTO nav_map(name, lft, rgt) VALUES('회계사1', @myLeft + 1, @myLeft + 2);


# indent 를 사용하여 출력 해보자.
SELECT CONCAT( REPEAT( ' ', (COUNT(parent.name) - 1) ), node.name) AS name
FROM nav_map AS node,
     nav_map AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;
출력 결과

# 위와 같은 방법도 좋지만 미리 right 와 left 값을 정하여 한번에 query 하는것이 좋다.
# 한번에 쿼리 하기 (right,left 의 위치를 알고 있다고 가정 함)
INSERT INTO nav_map VALUES
  (1,'CEO',1,24),
  (2,'개발부서',10,23),
  (3,'경영부서',2,9),
  (4,'웹 개발팀',19,22),
  (5,'앱 개발팀',15,18),
  (6,'서버 개발팀',11,14),
  (7,'웹 개발자1',20,21),
  (8,'앱 개발자1',16,17),
  (9,'서버 개발자1',12,13),
  (10,'회계팀',5,8),
  (11,'재무팀',3,4),
  (12,'회계사1',6,7);

# 각 부서와 팀들 순서대로 넣으려면 아래 와 같이 동등한 레벨의 노드일 경우 해당 해당 노드의 오른쪽으로 추가 해줄수 있다.
SELECT @myRight := rgt FROM nav_map
WHERE name = '추가하려는 동일한 레벨의 노드선택';
UPDATE nav_map SET rgt = rgt + 2 WHERE rgt > @myRight;
UPDATE nav_map SET lft = lft + 2 WHERE lft > @myRight;
INSERT INTO nav_map(name, lft, rgt) VALUES('추가할 노드', @myRight + 1, @myRight + 2);



## 앱 개발자1 1까지 경로 탐색,
# 해당 노드의 최상위까지의 싱글 경로 탐색
SELECT parent.name,parent.lft,parent.rgt
  FROM nav_map AS node,
       nav_map AS parent
  WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND node.name = '앱 개발자1'
  ORDER BY parent.lft;

## 선택한 노드의 하위 전체 노드 검색
SELECT node.name,node.lft,node.rgt
FROM nav_map AS node,
        nav_map AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND parent.name = '개발부서'
ORDER BY node.lft;


# 해당 노드의 하위 경로 (1 depth 만 보여준다.)
# HAVING depth <=1 일 경우 자신을 포함한다. = 일 경우 자신은 포함시키지 않는다.
SELECT node.name,(COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
  FROM nav_map AS node,
          nav_map AS parent,
          nav_map AS sub_parent,
          (
                  SELECT node.name, (COUNT(parent.name) - 1) AS depth
                  FROM nav_map AS node,
                          nav_map AS parent
                  WHERE node.lft BETWEEN parent.lft AND parent.rgt
                          AND node.name = '개발부서'
                  GROUP BY node.name
                  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
  HAVING depth <= 1
  ORDER BY node.lft;


# 삭제 하기 (하위 노드까지 삭제 하도록 한다.)
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nav_map
WHERE name = '웹 개발팀';
DELETE FROM nav_map WHERE lft BETWEEN @myLeft AND @myRight;
UPDATE nav_map SET rgt = rgt - @myWidth WHERE rgt > @myRight;
UPDATE nav_map SET lft = lft - @myWidth WHERE lft > @myRight;

#부모이면 삭제 한 후 자식노드 승격 시킴
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nav_map
WHERE name = '앱 개발팀';
DELETE FROM nav_map WHERE lft = @myLeft;
UPDATE nav_map SET rgt = rgt - 1, lft = lft - 1 WHERE lft BETWEEN @myLeft AND @myRight;
UPDATE nav_map SET rgt = rgt - 2 WHERE rgt > @myRight;
UPDATE nav_map SET lft = lft - 2 WHERE lft > @myRight;
# indent 활용하여 출력
SELECT CONCAT( REPEAT( ' ', (COUNT(parent.name) - 1) ), node.name) AS name
FROM nav_map AS node,
        nav_map AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;