Brain285. 트리 구조 저장 - Materialized Path, Nested Sets
핵심 인사이트 (3줄 요약)
- 본질: 트리 구조 저장(Tree Structure Storage)은 계층적(Hierarchical) 데이터인 조직도, 카테고리, 댓글 대댓글 등을 데이터베이스에 효율적으로 저장하고 조회하는 기법이다.
- 가치: Materialized Path, Nested Sets, Adjacency List 등 다양한 모델링 기법으로 트리 연산을 최적화하며, 조회 깊이 제한, 하위 트리 추출, 경로 조회 등이 가능하다.
- 융합: NoSQL 모델링, 몽고DB "$graphLookup", 재귀 CTE, 조직도/카테고리 관리, 메뉴 시스템과 밀접하게 연관된다.
Ⅰ. 개요 및 필요성 (Context & Necessity)
개념 정의
트리 구조 저장(Tree Structure Storage)은 계층적(Hierarchical) 데이터 구조를 데이터베이스에 저장하고管理하는 기법이다. 조직도(Organization Chart), 카테고리(Category Tree), 댓글 대댓글(Threaded Comments), 파일 시스템(File System) 등이 트리 구조의 대표적用例다. 이러한 계층적 데이터를 관계형 데이터베이스나 문서 데이터베이스에 어떻게 효율적으로 저장하고, 빠른 조회와 수정을 지원하는지가 핵심 과제이다.
필요성
계층적 데이터는 일반적인 테이블 구조(2차원 행렬)와 맞지 않는다. 자식-부모 관계를 외래 키로管理하는 방식(Adjacency List)은 구현은 간단하지만, 전체 하위 트리 조회나 특정 깊이의 노드 조회 시 자기 조인(Self-Join)이나 재귀 쿼리가 필요하여 성능이 저하된다. 따라서 트리 특유의 연산(하위 트리 추출,祖先 노드 조회, 깊이 제한 조회 등)을 최적화하는 특별한 저장 기법이 필요하다.
배경
계층적 데이터를管理하기 위한 기법은 오랜 역사를 가지고 있다. 관계형 데이터베이스에서는 Adjacency List, Materialized Path, Nested Sets, Closure Table 등의 기법이 널리 사용되어 왔다. NoSQL 문서 데이터베이스에서는 몽고DB의 "$graphLookup"聚合 연산자나 임베디드 배열(对于 댓글 대댓글) 패턴을活用한다. 각 기법은 장단점이 있어用例에 따라 적절한 것을 선택해야 한다.
비유
트리 구조 저장은大型기업의 조직도 관리 방법과 같다. 단순한 방법(Adjacency List)은 "내 상사는 누구입니다"만 표시하는 것이고, 고급 방법(Materialized Path)은 "나의 전체 경로: CEO → VP → Director → Manager → 나"를 함께 표시하는 것이다. 전체 부하 목록이 필요할 때, 단순한 방법은 모든层级을 재귀적으로 뒤져야 하고, 고급 방법은 경로 문자열에서 바로 필터링할 수 있다.
📢 섹션 요약: 트리 구조 저장은 계층적 데이터를 효율적으로 저장하고 조회하는 기법으로, Materialized Path, Nested Sets, Adjacency List 등 다양한 전략을 통해 트리 고유 연산을 최적화한다.
Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)
Adjacency List 모델
┌─────────────────────────────────────────────────────────────────────────────┐
│ Adjacency List 모델 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ [개념] │
│ ───── │
│ • 각 노드가 직접 부모에 대한 참조(Parent_ID)를 가짐 │
│ • 가장 단순한 트리 저장 방식, 이해하기 쉬움 │
│ • 쓰기에 유리, 읽기(특히 하위 트리 조회)에 불리 │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ employees 테이블 │ │
│ │ ───────────────── │ │
│ │ id │ name │ parent_id │ title │ │
│ │ 1 │ CEO │ NULL │ Chief Executive Officer │ │
│ │ 2 │ CTO │ 1 │ Chief Technology Officer │ │
│ │ 3 │ CFO │ 1 │ Chief Financial Officer │ │
│ │ 4 │ Dev Manager│ 2 │ Development Manager │ │
│ │ 5 │ QA Manager │ 2 │ QA Manager │ │
│ │ 6 │ Sr Engineer│ 4 │ Senior Engineer │ │
│ │ 7 │ Jr Engineer│ 6 │ Junior Engineer │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ [트리 구조] │
│ │
│ CEO (1) │
│ / \ │
│ CTO(2) CFO(3) │
│ / \ │
│ Dev Mgr(4) QA Mgr(5) │
│ / │
│ Sr Eng(6) │
│ / │
│ Jr Eng(7) │
│ │
│ [하위 트리 조회 - 재귀 CTE 필요] │
│ │
│ WITH RECURSIVE emp_tree AS ( │
│ SELECT id, name, parent_id, 0 AS depth │
│ FROM employees WHERE name = 'CTO' │
│ UNION ALL │
│ SELECT e.id, e.name, e.parent_id, et.depth + 1 │
│ FROM employees e │
│ JOIN emp_tree et ON e.parent_id = et.id │
│ ) │
│ SELECT * FROM emp_tree; │
│ │
│ ※ 복잡한 재귀 쿼리 필요, 성능 overhead │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
Materialized Path 모델
┌─────────────────────────────────────────────────────────────────────────────┐
│ Materialized Path 모델 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ [개념] │
│ ───── │
│ • 각 노드가 전체 경로(Root에서 현재까지의 모든祖先)를 문자열로 저장 │
│ • 경로 문자열을 통해 하위 트리/祖先 노드를 빠르게 조회 │
│ • 읽기에 매우 유리, 쓰기 시 경로 문자열 更新 필요 │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ employees 테이블 │ │
│ │ ───────────────── │ │
│ │ id │ name │ parent_id │ path │ depth │ │
│ │ 1 │ CEO │ NULL │ /1 │ 0 │ │
│ │ 2 │ CTO │ 1 │ /1/2 │ 1 │ │
│ │ 3 │ CFO │ 1 │ /1/3 │ 1 │ │
│ │ 4 │ Dev Manager│ 2 │ /1/2/4 │ 2 │ │
│ │ 5 │ QA Manager │ 2 │ /1/2/5 │ 2 │ │
│ │ 6 │ Sr Engineer│ 4 │ /1/2/4/6 │ 3 │ │
│ │ 7 │ Jr Engineer│ 6 │ /1/2/4/6/7 │ 4 │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ [경로 구조 시각화] │
│ │
│ /1 │
│ └─ /1/2 (CTO) │
│ ├─ /1/2/4 (Dev Manager) │
│ │ └─ /1/2/4/6 (Sr Engineer) │
│ │ └─ /1/2/4/6/7 (Jr Engineer) │
│ └─ /1/2/5 (QA Manager) │
│ └─ /1/3 (CFO) │
│ │
│ [고속 조회 예시] │
│ │
│ -- CTO의 모든 하위 노드 조회 (LIKE 패턴 매칭) │
│ SELECT * FROM employees WHERE path LIKE '/1/2%'; │
│ → Sr Engineer, Jr Engineer 포함, 단일 쿼리 │
│ │
│ -- Jr Engineer의 모든祖先 조회 (경로 파싱) │
│ SELECT * FROM employees │
│ WHERE id IN (1, 2, 4, 6); -- /1/2/4/6/7 에서 파싱 │
│ │
│ -- 깊이 2인 모든 노드 조회 │
│ SELECT * FROM employees WHERE depth = 2; │
│ → Dev Manager, QA Manager │
│ │
│ [쓰기 시 경로 업데이트] │
│ ────────────────────────── │
│ Jr Engineer의 parent가 Sr Engineer에서 Dev Manager로 변경되면: │
│ 1. Jr Engineer의 path: /1/2/4/7로 변경 (祖先 기준 재계산) │
│ 2. Jr Engineer의 모든 하위 노드 path 접두사 업데이트 │
│ → 쓰기 overhead 발생 │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
Nested Sets 모델
┌─────────────────────────────────────────────────────────────────────────────┐
│ Nested Sets 모델 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ [개념] │
│ ───── │
│ • 각 노드에 left, right 값을 부여하여 트리 구조를二次元 평면에 매핑 │
│ • left < right이고, 부모 노드의 left/right 범위 내에 자식 노드가 위치 │
│ • 하위 트리 조회가 매우 빠름, 삽입/삭제 시 many nodes 업데이트 필요 │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ employees 테이블 │ │
│ │ ───────────────── │ │
│ │ id │ name │ left │ right │ depth │ │
│ │ 1 │ CEO │ 1 │ 14 │ 0 │ │
│ │ 2 │ CTO │ 2 │ 9 │ 1 │ │
│ │ 3 │ CFO │ 10 │ 13 │ 1 │ │
│ │ 4 │ Dev Manager│ 3 │ 6 │ 2 │ │
│ │ 5 │ QA Manager │ 7 │ 8 │ 2 │ │
│ │ 6 │ Sr Engineer│ 4 │ 5 │ 3 │ │
│ │ 7 │ Jr Engineer│ 11 │ 12 │ 2 │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ [Nested Sets 평면 매핑] │
│ │
│ 1(CEO)────────────────────────────────────────────────────14 │
│ │ │
│ ├─2(CTO)───────────────────────────────────9 │
│ │ │ │
│ │ ├─3(Dev Mgr)────────────────6 │
│ │ │ │ │
│ │ │ └─4(Sr Eng)───────5 │
│ │ │ │
│ │ └─7(QA Mgr)────────────8 │
│ │ │
│ └─10(CFO)────────────────────────────────12 │
│ │ │
│ └─11(Jr Eng)───────────────12 │
│ │
│ [고속 조회 예시] │
│ │
│ -- CTO의 모든 하위 노드 조회 │
│ SELECT * FROM employees │
│ WHERE left > 2 AND right < 9; │
│ → Dev Manager, Sr Engineer, QA Manager │
│ │
│ -- 특정 노드의祖先 조회 │
│ SELECT * FROM employees │
│ WHERE left < 5 AND right > 5 │
│ ORDER BY left; │
│ → CEO, CTO, Dev Manager (Jr Engineer의祖先) │
│ │
│ [삽입/삭제 시 문제] │
│ ────────────────────── │
│ 새 노드 삽입 시: 삽입 위치 이후의 모든 left/right 값 업데이트 필요 │
│ 노드 삭제 시: 삭제 노드의 하위 트리 처리 + 이후 모든 left/right 값 업데이트 │
│ → 쓰기 overhead非常大,频繁한 변경에는不적합 │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
세 모델 비교
┌─────────────────────────────────────────────────────────────────────────────┐
│ Tree Storage Models 비교 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌────────────────┬───────────────┬──────────────┬──────────────┐ │
│ │ Operations │ Adjacency List │ Materialized │ Nested Sets │ │
│ │ │ │ Path │ │ │
│ ├────────────────┼───────────────┼──────────────┼──────────────┤ │
│ │ 하위 트리 조회 │ ★☆☆☆☆ │ ★★★★★ │ ★★★★★ │ │
│ │ (Read) │ (재귀 CTE) │ (LIKE) │ (범위查询) │ │
│ ├────────────────┼───────────────┼──────────────┼──────────────┤ │
│ │祖先 노드 조회 │ ★★★★★ │ ★★★★☆ │ ★★★★☆ │ │
│ │ (Ancestor) │ (재귀 CTE) │ (파싱) │ (범위查询) │ │
│ ├────────────────┼───────────────┼──────────────┼──────────────┤ │
│ │ 깊이 제한 조회 │ ★★★☆☆ │ ★★★★★ │ ★★★☆☆ │ │
│ │ │ │ (depth col) │ │ │
│ ├────────────────┼───────────────┼──────────────┼──────────────┤ │
│ │ 노드 삽입 │ ★★★★★ │ ★★★☆☆ │ ★☆☆☆☆ │ │
│ │ (Insert) │ │ (path 갱신) │ (left/right) │ │
│ ├────────────────┼───────────────┼──────────────┼──────────────┤ │
│ │ 노드 이동 │ ★★★★☆ │ ★★☆☆☆ │ ★☆☆☆☆ │ │
│ │ (Move) │ │ (subtree) │ (재계산) │ │
│ ├────────────────┼───────────────┼──────────────┼──────────────┤ │
│ │ 구현 난이도 │ 낮음 │ 낮음 │ 중간 │ │
│ └────────────────┴───────────────┴──────────────┴──────────────┘ │
│ │
│ [결정 가이드] │
│ ─────────── │
│ • 읽기 위주, 변경 드문: Nested Sets (카테고리 목록, 게시판 등) │
│ • 읽기/쓰기 균형: Materialized Path (조직도, 메뉴 시스템) │
│ • 쓰기 위주, 읽기 단순: Adjacency List (댓글, 좋아요 관계) │
│ • 복잡한階層쿼리: 몽고DB "$graphLookup" 고려 │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
[다이어그램 해설] 세 가지 트리 저장 모델은 각각 다른 트레이드오프를 가진다. Adjacency List는 쓰기에 유리하지만 하위 트리 조회가 복잡하고, Nested Sets은 하위 트리 조회가 매우 빠르지만 쓰기 시 overhead가 크다. Materialized Path는 양자의 절충안으로, 대부분의用例에서 좋은 성능을 보인다. 실제 시스템에서는 Hybrid 접근(예: Adjacency List + Materialized Path)을 선택하는 것도 고려할 수 있다.
📢 섹션 요약: 트리 구조 저장은 Adjacency List(쓰기 유리), Materialized Path(균형), Nested Sets(읽기 유리) 등 다양한 모델이 있으며,用例에 따라 적절한 전략을 선택해야 한다.
Ⅲ. 결론
트리 구조 저장은 계층적 데이터를 데이터베이스에 효율적으로 저장하고 조회하는 중요한 기법이다. Adjacency List, Materialized Path, Nested Sets 각 모델은 읽기/쓰기 성능에서 서로 다른 트레이드오프를 가진다. 읽기 위주이고 변경이 드문 구조(카테고리, 조직도)에는 Nested Sets이나 Materialized Path가 적합하고, 쓰기가 많은 구조에는 Adjacency List가 적합하다. 몽고DB의 "$graphLookup"이나 Closure Table 같은 고급 기법도 있으며, 실무에서는 Hybrid 접근을 선택하는 경우가 많다.
📢 섹션 요약: 트리 구조 저장 기법은 Adjacency List, Materialized Path, Nested Sets으로 나뉘며, 각각 읽기/쓰기 성능 트레이드오프가 다르므로用例에 맞게 선택해야 한다.
핵심 인사이트 ASCII 다이어그램 (Concept Map)
┌─────────────────────────────────────────────────────────────────────────────┐
│ Tree Structure Storage Concept Map │
│ │
│ ┌─────────────────────────────────┐ │
│ │ Tree Structure Storage │ │
│ │ (트리 구조 저장) │ │
│ └───────────────┬─────────────────┘ │
│ │ │
│ ┌────────────────────┼────────────────────┐ │
│ ▼ ▼ ▼ │
│ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ │
│ │ Adjacency │ │ Materialized │ │ Nested │ │
│ │ List │ │ Path │ │ Sets │ │
│ │ (쓰기 유리) │ │ (균형형) │ │ (읽기 유리) │ │
│ └──────────────┘ └──────────────┘ └──────────────┘ │
│ │ │ │ │
│ └────────────────────┼────────────────────┘ │
│ ▼ │
│ ┌─────────────────────┐ │
│ │ $graphLookup │ │
│ │ (MongoDB的高级) │ │
│ │ + Closure Table │ │
│ └─────────────────────┘ │
│ │
│ 선택 기준: 읽기/쓰기 비율 | 변경 빈도 | 쿼리 패턴 │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
참고
- 트리 구조 저장은 계층적 데이터를 효율적으로管理하는 기법이다.
- Adjacency List, Materialized Path, Nested Sets이 대표적 모델이다.
- Adjacency List는 쓰기에 유리, Nested Sets은 읽기에 유리하다.
- Materialized Path는 균형 잡힌 성능을 제공한다.
- 몽고DB "$graphLookup"은 복잡한階層쿼리에 유용하다.
- 실무에서는 Hybrid 접근을 선택하는 것도 고려할 수 있다.