클로저 테이블

클로저 테이블은 노드마다 자신과 모든 조상·자손 조합을 저장합니다.

읽기는 ancestor_id 또는 descendant_id 인덱스 범위가 되지만 경로를 하나라도 빼먹으면 존재하는 노드가 조회에서 사라집니다.

수동으로 직속 간선만 입력하지 않고 인접 리스트를 원본으로 재귀 백필해야 자기 참조 깊이 0과 모든 간접 경로를 같은 규칙으로 생성할 수 있습니다.

개발에서 데이터베이스까지의 경로를 클로저로 옮깁니다.

먼저 직접 부모 간선만 복사해 루트 자손 쿼리가 데이터베이스를 놓치는 오류를 확인합니다.

불완전한 클로저 경로

인접 리스트의 여섯 부모 간선만 넣으면 루트의 직속 자식 두 개만 조회됩니다.

깊이 0 자기 참조 행이 없어 리프 자신을 기준으로 조회해도 빈 결과가 나옵니다.

직속 parent만 복사한 불완전 경로 표

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;

루트 1 조회에는 백엔드와 프론트엔드만 나오며 Java·Spring·React·데이터베이스와 루트 자신이 빠집니다.

오류 실행 결과

category_name | depth
데이터베이스   | 1
프론트엔드       | 1

expected nodes including self: 7
returned nodes: 2

클로저 행은 간선이 아니라 도달 가능성입니다.

자기 참조 (n,n,0), 직속 (a,d,1), 간접 (a,d,k)가 모두 있어야 깊이 필터와 조상/자손 쿼리가 완전합니다.

원본 인접 목록이 순환이면 백필도 반복되므로 먼저 순환 감사를 통과시킵니다.

클로저 PK는 같은 조합의 서로 다른 깊이를 허용하지 않아 트리의 유일 경로 가정을 반영합니다.

직속 두 행만 남아 루트 하위 트리가 잘린 이유

자기 참조 — 모든 노드에 깊이 0 경로가 있는지 셉니다.
직접 — 부모 간선 수와 클로저 깊이 1 수를 비교합니다.
전이 — 루트 자손과 리프 조상이 전체 경로를 갖는지 봅니다.
깊이 — 클로저 깊이와 재귀 CTE 거리가 같은지 대조합니다.

클로저 행의 의미

트리에서는 조상·자손 조합마다 경로가 하나이므로 복합 PK 하나에 깊이를 저장할 수 있습니다.

DAG처럼 경로가 여러 개면 최소 깊이만 저장할지 경로별 행을 둘지 모델이 달라집니다.

자손 쿼리는 조상 선두 PK를 사용하고 조상 쿼리를 위해 (descendant_id, depth, ancestor_id) 보조 인덱스를 둡니다.

자기 참조·직접·전이 경로를 하나의 규칙으로 만들기

원본 — 인접 리스트를 원본 간선으로 둡니다.
시작 행 — 각 노드의 자기 참조 경로를 깊이 0으로 만듭니다.
확장 — 현재 자손의 자식을 붙여 깊이를 증가시킵니다.
제약 조건 — 두 FK·PK·깊이 범위와 양방향 인덱스를 둡니다.

인접 리스트 기반 경로 생성

클로저를 비우고 자기 참조 경로를 시작 행으로 한 CTE가 자식 간선을 끝까지 확장합니다.

최종 18개 경로를 한 INSERT로 적재합니다.

완전 closure schema와 backfill

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;

7개 자기 참조 경로, 6개 직접 경로, 5개 전이 경로가 생성되어 어느 노드에서 시작해도 자신과 전체 조상·자손을 읽을 수 있습니다.

개선 실행 결과

self paths (depth 0): 7
direct paths (depth 1): 6
transitive paths (depth >= 2): 5
total closure rows: 18
duplicate pairs: 0

백필은 인접 목록 스냅샷과 같은 시점이어야 합니다.

운영 중 이동과 동시에 재생성하면 섞인 그래프를 만들 수 있으므로 쓰기를 멈추거나 고정 스냅샷·새 테이블·원자적 이름 변경 절차를 사용합니다.

클로저는 원본이 아니라 읽기 모델로 운영할 수 있습니다.

인접 목록과 클로저 불일치 검사가 있으면 클로저를 폐기하고 원본에서 재구축할 수 있어야 합니다.

인접 목록과 깊이 1의 양방향 차집합 확인

행 건수 — 자기 참조·직접·전이 수를 분리해 셉니다.
자손 — 조상 1에서 7개 노드와 깊이를 확인합니다.
조상 — 자손 7에서 네 조상을 확인합니다.
불일치 — 인접 목록 직접 간선과 클로저 깊이 1의 양방향 차집합을 구합니다.

직접 관계 일치 확인

클로저 전체가 많아도 깊이 1은 원본 인접 목록과 같아야 합니다.

두 방향 차집합과 깊이별 행 수를 함께 확인합니다.

경로 완전성·drift 감사

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;

두 불일치 방향은 모두 0행입니다.

자손 7의 조상은 데이터베이스 깊이 0, Spring 1, 백엔드 2, 개발 3입니다.

누락·재구축·연쇄 크기를 바꾸는 실험

자기 참조 누락 — 노드 7 자기 참조 경로를 지우고 리프 조회 오류를 확인합니다.
직접 누락 — 깊이 1 한 행을 지워 불일치 쿼리를 실행합니다.
재생성 — 클로저 전체를 비운 뒤 CTE INSERT로 18행을 복원합니다.
연쇄 — 깊이 10 연쇄의 클로저 행 증가를 계산합니다.

경로 수 증가와 원본/읽기 모델 책임

클로저 테이블 크기는 대략 노드×평균 조상 수입니다.

연쇄는 O(n²), 균형 트리는 훨씬 작으므로 노드 수만으로 저장 비용을 예측하지 않습니다.

FK CASCADE는 노드 물리 삭제 시 관련 경로를 지우지만 하위 트리의 다른 노드 수명과 인접 목록 재연결까지 결정하지 않습니다.

삭제 명령은 그래프 정책을 먼저 수행해야 합니다.

DAG·테넌트·소프트 삭제의 경계

DAG는 같은 조합에 여러 경로가 존재할 수 있어 깊이 하나만 저장하면 정보가 줄어듭니다.
순환 원본에서는 재귀 백필이 종료 상한에 걸리므로 먼저 순환 감사를 통과합니다.
하위 트리별 테넌트가 다르면 교차-테넌트 경로 생성 자체를 금지합니다.
논리 삭제된 노드를 경로에 유지할지 순회에서 건너뛸지 결정합니다.

동기·비동기·재생성 클로저 운영 비교

선택	얻는 효과	감수할 비용	적합한 조건
필요 시 CTE	중복 저장 없음	반복 순회	조회 빈도와 하위 트리가 작을 때
동기 클로저	즉시 빠른 경로 조회	쓰기 증폭·잠금	강한 최신성이 필요할 때
비동기 클로저	원본 쓰기 단순	잠시 오래된	분류 읽기 지연을 허용할 때
주기 재생성	복구가 단순	재생성 사이 불일치	구조 변경이 매우 드물 때

경로 수와 재생성 시간을 관찰하기

클로저 합계 행 수, 평균/최대 조상, 인접 목록-depth1 불일치, 재생성 소요 시간을 관찰합니다.

대량 재생성은 새 테이블에 적재·검증한 뒤 짧은 교체 단계로 노출합니다.

다음 문서는 클로저가 완전한 상태에서 하위 트리 이동 때 이전 외부 경로를 지우고 신규 조상 경로를 원자적으로 삽입합니다.

클로저 테이블 도입 기준

판단 축	확인할 질문
읽기	조상·자손 쿼리 빈도와 지연 시간이 CTE 예산을 넘는가?
쓰기	분류 이동이 드물고 쓰기 증폭을 감수할 수 있는가?
크기	노드×조상 경로 수가 저장·인덱스 예산 안인가?
복구	인접 목록에서 전체 클로저를 재구축할 수 있는가?
일치 검사	깊이 1 간선과 자기 참조 경로 불일치를 탐지하는가?

클로저는 더 좋은 트리 모델이 아니라 읽기 워크로드를 위한 구체화 경로입니다.

원본·재생성·불일치 규칙이 있을 때만 선택합니다.

연습 문제

각 분류의 descendant_count와 leaf_count를 클로저만 사용해 구하세요.

자기 참조 경로는 descendant_count에서 제외하고 리프는 깊이 1 자식이 없는 노드입니다.

해설과 예시 답안

분류를 기준으로 클로저를 LEFT JOIN하고 깊이>0을 조건부 건수합니다.

리프는 직접 자식 경로가 한 행도 없는 경우입니다.

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;

데이터베이스·Java·React는 descendant_count 0과 is_leaf 1입니다.

개발은 자기 참조를 제외한 descendant_count 6입니다.

핵심 정리

클로저는 간선이 아니라 모든 도달 가능 조합을 저장합니다.
자기 참조·직접·전이 경로가 모두 필요합니다.
재귀 백필이 수동 누락을 막습니다.
인접 목록-depth1 일치 검사와 전체 재생성이 불일치 복구 기준입니다.

다음 문서에서는 하위 트리 이동을 클로저와 인접 목록에 원자적으로 반영합니다.

이 페이지의 목차