클로저 테이블

클로저 테이블(closure table)은 노드마다 자기 자신과 모든 조상, 자손의 조합을 저장합니다. 읽기는 ancestor_id나 descendant_id의 인덱스 범위가 되지만, 경로를 하나라도 빠뜨리면 있는 노드가 조회에서 사라집니다.

그래서 직속 간선만 손으로 넣지 않고, 인접 리스트를 원본으로 삼아 재귀로 백필합니다. 그래야 깊이 0의 자기 경로와 모든 간접 경로를 같은 규칙으로 만들 수 있습니다. 이 글은 14장 1편의 처음 일곱 노드 트리를 기준으로 계속 cs_db_lab에서 실행하며, 먼저 직속 부모 간선만 복사해 루트의 자손 조회가 데이터베이스를 놓치는 오류를 확인합니다.

불완전한 클로저 경로

인접 리스트의 부모 간선 여섯 개만 넣으면, 루트의 자손으로는 직속 자식 두 개만 조회됩니다. 깊이 0의 자기 경로가 없으므로 리프 자신을 기준으로 조회해도 빈 결과가 나옵니다.

DROP TABLE IF EXISTS category_closure_bad;

CREATE TABLE category_closure_bad (
  ancestor_id BIGINT UNSIGNED NOT NULL,
  descendant_id BIGINT UNSIGNED NOT NULL,
  depth SMALLINT UNSIGNED NOT NULL,
  PRIMARY KEY (ancestor_id, descendant_id)
) ENGINE=InnoDB;

INSERT INTO category_closure_bad
  (ancestor_id, descendant_id, depth)
SELECT parent_id, category_id, 1
FROM categories
WHERE parent_id IS NOT NULL;

SELECT c.category_name, p.depth
FROM category_closure_bad AS p
JOIN categories AS c
  ON c.category_id = p.descendant_id
WHERE p.ancestor_id = 1
ORDER BY p.depth, c.category_id;

category_name | depth
백엔드        | 1
프론트엔드    | 1

자기 자신까지 일곱 노드가 나와야 할 루트 1의 조회에서, 백엔드와 프론트엔드만 나오고 Java와 Spring, React, 데이터베이스, 루트 자신이 빠졌습니다. 클로저의 행은 간선이 아니라 도달할 수 있다는 사실이기 때문입니다.

자기 경로 (n, n, 0)과 직속 경로 (a, d, 1), 간접 경로 (a, d, k)가 모두 있어야 깊이 조건과 조상, 자손의 쿼리가 완전해집니다. 원본 인접 리스트에 순환이 있으면 백필도 같은 경로를 되풀이하므로 순환 감사를 먼저 통과시키며, 클로저의 기본 키는 같은 조합에 서로 다른 깊이를 허용하지 않아 트리에서 경로가 하나뿐이라는 가정을 반영합니다.

클로저 행의 의미

트리에서는 조상과 자손의 조합마다 경로가 하나이므로, 복합 기본 키 하나에 깊이를 함께 저장할 수 있습니다. DAG처럼 경로가 여러 개라면 최소 깊이만 저장할지 경로마다 행을 둘지에 따라 모델이 달라집니다.

자손 쿼리는 ancestor_id로 시작하는 기본 키를 쓰고, 조상 쿼리를 위해 (descendant_id, depth, ancestor_id)의 보조 인덱스를 둡니다. 행을 만드는 규칙은 하나입니다. 인접 리스트를 원본 간선으로 두고, 각 노드의 자기 경로를 깊이 0으로 만든 뒤, 현재 자손의 자식을 덧붙이며 깊이를 늘립니다.

인접 리스트 기반 경로 생성

자기 경로에서 자식 간선을 깊이 20까지 펼치므로, 더 깊은 트리의 모든 경로를 보장하는 백필은 아닙니다. 처음 트리의 경로를 한 번의 INSERT로 적재합니다. 12장 4편에서 본 CHECK와 외래 키 참조 동작의 제한은 자식 행의 열 값을 바꾸는 동작에 걸립니다. MySQL 8.4는 ON UPDATE CASCADE와, ON UPDATE나 ON DELETE의 SET NULL, SET DEFAULT가 있는 외래 키의 열을 CHECK에 쓰면 거부하지만, ON DELETE CASCADE는 자식 행을 통째로 지울 뿐 열의 값을 바꾸지 않으므로 아래 DDL처럼 ancestor_id와 descendant_id를 CHECK에 함께 쓸 수 있습니다.

DROP TABLE IF EXISTS category_closure;

CREATE TABLE category_closure (
  ancestor_id BIGINT UNSIGNED NOT NULL,
  descendant_id BIGINT UNSIGNED NOT NULL,
  depth SMALLINT UNSIGNED NOT NULL,
  PRIMARY KEY (ancestor_id, descendant_id),
  CONSTRAINT fk_closure_ancestor FOREIGN KEY (ancestor_id)
    REFERENCES categories (category_id) ON DELETE CASCADE,
  CONSTRAINT fk_closure_descendant FOREIGN KEY (descendant_id)
    REFERENCES categories (category_id) ON DELETE CASCADE,
  CONSTRAINT chk_closure_depth CHECK (
    (ancestor_id = descendant_id AND depth = 0)
    OR
    (ancestor_id <> descendant_id AND depth > 0)
  ),
  INDEX ix_closure_descendant_depth
    (descendant_id, depth, ancestor_id)
) ENGINE=InnoDB;

INSERT INTO category_closure
  (ancestor_id, descendant_id, depth)
WITH RECURSIVE paths AS (
  SELECT category_id AS ancestor_id,
         category_id AS descendant_id,
         0 AS depth
  FROM categories

  UNION ALL

  SELECT path.ancestor_id,
         child.category_id,
         path.depth + 1
  FROM paths AS path
  JOIN categories AS child
    ON child.parent_id = path.descendant_id
  WHERE path.depth < 20
)
SELECT ancestor_id, descendant_id, depth
FROM paths;

SELECT c.category_name, p.depth
FROM category_closure AS p
JOIN categories AS c
  ON c.category_id = p.descendant_id
WHERE p.ancestor_id = 1
ORDER BY p.depth, c.category_id;

category_name | depth
개발          | 0
백엔드        | 1
프론트엔드    | 1
Java          | 2
Spring        | 2
React         | 2
데이터베이스  | 3

이번에는 루트 1의 조회가 자기 자신을 포함한 일곱 노드를 깊이와 함께 돌려줍니다. 최대 깊이가 3인 처음 트리에서 INSERT는 18행을 넣는데, 깊이 0이 7행, 깊이 1이 6행, 깊이 2가 4행, 깊이 3이 1행입니다.

같은 18행을 자손을 기준으로 다시 셀 수도 있습니다. 자손 하나를 고정하고 자기 자신을 포함한 조상의 수를 세면, ID 1은 1행, 2와 3은 2행씩, 4와 5, 6은 3행씩, 7은 4행이므로 1 + 2 + 2 + 3 + 3 + 3 + 4 = 18입니다. 간접 경로 (1, 5, 2)와 (5, 7, 1)을 이으면 (1, 7, 3)도 필요하지만, 그렇다고 인접 리스트에 새 직속 간선이 생기는 것은 아닙니다.

백필은 인접 리스트의 한 시점과 맞아야 합니다. 운영 중에 이동과 동시에 다시 만들면 두 상태가 섞인 그래프가 될 수 있으므로, 쓰기를 멈추거나, 고정된 스냅샷에서 새 테이블을 만들어 원자적으로 이름을 바꿉니다. 클로저는 원본이 아니라 읽기 모델로 운영할 수 있고, 인접 리스트와의 불일치를 검사할 수 있다면 클로저를 버리고 원본에서 다시 만들 수 있어야 합니다.

직접 관계의 일치 확인

클로저 전체가 아무리 많아도, 깊이 1의 행은 원본 인접 리스트의 간선과 같아야 합니다. 두 방향의 차집합과 깊이별 행의 수를 함께 확인합니다.

SELECT depth, COUNT(*) AS path_count
FROM category_closure
GROUP BY depth
ORDER BY depth;

SELECT 'ADJACENCY_ONLY' AS mismatch,
       c.parent_id AS ancestor_id,
       c.category_id AS descendant_id
FROM categories AS c
LEFT JOIN category_closure AS p
  ON p.ancestor_id = c.parent_id
 AND p.descendant_id = c.category_id
 AND p.depth = 1
WHERE c.parent_id IS NOT NULL
  AND p.ancestor_id IS NULL

UNION ALL

SELECT 'CLOSURE_ONLY' AS mismatch,
       p.ancestor_id,
       p.descendant_id
FROM category_closure AS p
LEFT JOIN categories AS c
  ON c.parent_id = p.ancestor_id
 AND c.category_id = p.descendant_id
WHERE p.depth = 1
  AND c.category_id IS NULL;

SELECT ancestor.category_name,
       p.depth
FROM category_closure AS p
JOIN categories AS ancestor
  ON ancestor.category_id = p.ancestor_id
WHERE p.descendant_id = 7
ORDER BY p.depth;

depth | path_count
0     | 7
1     | 6
2     | 4
3     | 1

category_name | depth
데이터베이스  | 0
Spring        | 1
백엔드        | 2
개발          | 3

깊이 1의 두 방향 차집합은 빈 결과이고, 자손 7의 조상은 자기 자신과 Spring, 백엔드, 개발의 순서입니다. 다만 이 확인은 직속 간선의 일치만 보장할 뿐, 자기 경로와 모든 간접 경로, 깊이의 완전성을 증명하지는 않습니다.

예를 들어 정상 클로저에서 (1, 7, 3)을 지우고 있지도 않은 경로 (3, 7, 2)를 넣으면, 전체 18행과 깊이 1의 감사는 그대로입니다. 그러나 개발의 자손 조회는 7을 놓치고, 프론트엔드의 자손 조회는 잘못된 7을 포함합니다. 외래 키와 깊이 조건, 전체 행의 수, 직속 간선만으로는 모든 간접 경로가 정확한지 알 수 없으므로, 원본에서 계산한 전체 (조상, 자손, 깊이) 집합과도 대조해야 합니다(연습 문제 3).

경로의 수와 운영

클로저 테이블의 크기는 대략 노드의 수에 평균 조상의 수를 곱한 값입니다. 한 줄로 이어진 연쇄는 노드 n개에 n(n + 1) / 2행으로 늘지만 균형 트리는 훨씬 작으므로, 노드의 수만으로 저장 비용을 예측하지 않습니다. 외래 키의 CASCADE는 노드를 물리 삭제할 때 관련 경로를 지우지만, 하위 트리의 다른 노드의 수명과 인접 리스트의 재연결까지 정하지는 않으므로, 삭제 명령은 그래프의 정책을 먼저 수행해야 합니다.

DAG는 같은 조합에 여러 경로가 있을 수 있어 깊이 하나만 저장하면 정보가 줄어듭니다. 이 백필에는 방문 경로 검사가 없고 깊이 20의 상한만 있으므로, 원본에 순환이 있으면 같은 쌍이 다른 깊이로 만들어져 기본 키 위반이 나거나, 자기 자신을 가리키는 쌍에 0이 아닌 깊이가 붙어 chk_closure_depth 위반이 날 수 있습니다. 하위 트리마다 테넌트가 다르다면 테넌트를 넘는 경로를 만드는 것 자체를 금지하고, 논리 삭제한 노드를 경로에 남길지 순회에서 건너뛸지도 정합니다.

운영에서는 클로저 전체의 행 수와 평균, 최대 조상의 수, 인접 리스트와 깊이 1의 불일치, 재생성에 걸린 시간을 지켜봅니다. 대량 재생성은 새 테이블에 적재하고 검증한 뒤 짧은 교체 단계로 내보냅니다.

클로저는 더 좋은 트리 모델이 아니라, 읽기 작업을 위해 구체화한 경로입니다. 원본과 재생성, 불일치의 규칙이 있을 때만 고릅니다.

정리

• 클로저는 간선이 아니라 도달할 수 있는 모든 조합을 저장합니다.
• 자기 경로와 직속 경로, 간접 경로가 모두 있어야 조회가 완전합니다.
• 손으로 넣지 않고 인접 리스트에서 재귀로 백필해 누락을 막습니다.
• 깊이 1의 일치 확인은 필요하지만 충분하지 않으며, 전체 경로 집합과 대조하고 원본에서 다시 만들 수 있어야 합니다.

연습 문제

1. 새 리프의 경로

처음 트리의 데이터베이스 7 아래에 새 리프 8을 하나 더하고, 클로저를 정상적으로 갱신했습니다. 기존 경로는 그대로입니다. 새로 생기는 경로는 어떤 (ancestor, descendant, depth)이고, 클로저는 모두 몇 행이 되나요?

2. 자손의 수와 리프 여부

각 분류의 descendant_count와 리프 여부 is_leaf를 구해 보세요. 관계는 클로저로 판단하고 이름은 categories에서 읽습니다. 자기 경로는 descendant_count에서 빼고, 리프는 깊이 1의 자식이 없는 노드입니다.

SELECT c.category_id,
       c.category_name,
       COUNT(CASE WHEN path.depth > 0 THEN 1 END) AS descendant_count,
       NOT EXISTS (
         SELECT 1
         FROM category_closure AS direct
         WHERE direct.ancestor_id = c.category_id
           AND direct.depth = 1
       ) AS is_leaf
FROM categories AS c
LEFT JOIN category_closure AS path
  ON path.ancestor_id = c.category_id
GROUP BY c.category_id, c.category_name
ORDER BY c.category_id;

category_id | category_name | descendant_count | is_leaf
1           | 개발          | 6                | 0
2           | 백엔드        | 3                | 0
3           | 프론트엔드    | 1                | 0
4           | Java          | 0                | 1
5           | Spring        | 1                | 0
6           | React         | 0                | 1
7           | 데이터베이스  | 0                | 1

3. 전체 경로 집합의 대조

본문의 예처럼 (1, 7, 3)을 지우고 (3, 7, 2)를 넣은 손상을 트랜잭션 안에서 만들고, 원본 인접 리스트에서 계산한 전체 경로 집합과 클로저를 양방향으로 대조해 보세요.

START TRANSACTION;

DELETE FROM category_closure
WHERE ancestor_id = 1 AND descendant_id = 7;
INSERT INTO category_closure (ancestor_id, descendant_id, depth)
VALUES (3, 7, 2);

WITH RECURSIVE expected AS (
  SELECT category_id AS ancestor_id,
         category_id AS descendant_id,
         0 AS depth
  FROM categories
  UNION ALL
  SELECT e.ancestor_id, c.category_id, e.depth + 1
  FROM expected AS e
  JOIN categories AS c ON c.parent_id = e.descendant_id
  WHERE e.depth < 20
)
SELECT 'MISSING' AS problem, e.ancestor_id, e.descendant_id, e.depth
FROM expected AS e
WHERE NOT EXISTS (
  SELECT 1 FROM category_closure AS p
  WHERE p.ancestor_id = e.ancestor_id
    AND p.descendant_id = e.descendant_id
    AND p.depth = e.depth
)
UNION ALL
SELECT 'EXTRA', p.ancestor_id, p.descendant_id, p.depth
FROM category_closure AS p
WHERE NOT EXISTS (
  SELECT 1 FROM expected AS e
  WHERE e.ancestor_id = p.ancestor_id
    AND e.descendant_id = p.descendant_id
    AND e.depth = p.depth
);

ROLLBACK;

problem | ancestor_id | descendant_id | depth
MISSING | 1           | 7             | 3
EXTRA   | 3           | 7             | 2

다음 글 하위 트리 이동에서는 클로저가 완전한 상태에서 하위 트리를 옮길 때, 바깥 조상과의 이전 경로를 지우고 새 조상과의 경로를 원자적으로 넣습니다.