계층적 데이터 모델링 기법 - low-hill/Knowledge GitHub Wiki

서론

계층적 데이터를 효율적으로 관리하는 것은 많은 애플리케이션에서 중요한 과제입니다. 이 글에서는 세 가지 주요 계층적 데이터 모델링 기법인 Adjacency List, Materialized Path, Closure Table에 대해 자세히 살펴보고, 각각의 장단점과 사용 사례를 비교해보겠습니다.

Adjacency List (인접 리스트)

1.1 기본 개념

가장 직관적이고 널리 사용되는 계층적 데이터 모델링 기법으로, 각 노드는 부모 노드에 대한 참조(parent_id)를 가지며, 이를 통해 트리 구조를 표현합니다.

계층 구조 예시

1. 전자제품
   └── 2. 노트북
       └── 3. 게이밍노트북
   └── 4. 스마트폰

5. 가전제품
   └── 6. TV

상위 카테고리와의 관계:
각 레코드는 parent_id를 통해 자신의 직계 부모를 가리킵니다.
- 예: '게이밍노트북'의 parent_id는 2('노트북')
parent_id가 NULL인 경우, 해당 노드는 최상위(root) 노드가 됩니다.
- 예: '전자제품'과 '가전제품'은 parent_id가 NULL
한 노드의 모든 조상(ancestors)을 찾으려면 재귀적 쿼리나 애플리케이션 레벨에서의 반복 조회가 필요합니다.
계층 구조 탐색:
- 부모 → 자식: WHERE parent_id = ?로 직계 자식 조회
- 자식 → 부모: parent_id를 사용해 부모 조회
- 깊이 우선 탐색: 재귀적 쿼리(CTE)나 애플리케이션 코드로 구현

이 방식은 직관적이지만, 깊은 계층 구조를 가진 데이터를 조회할 때는 성능 이슈가 발생할 수 있습니다.

1.2 테이블 구조

위에서 살펴본 계층 구조를 데이터베이스에 저장하기 위한 테이블 구조는 다음과 같습니다:

CREATE TABLE categories (
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    slug VARCHAR(255) UNIQUE,
    parent_id INT NULL,
    display_order INT DEFAULT 0,
    is_active BOOLEAN DEFAULT true,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    updated_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
    FOREIGN KEY (parent_id) REFERENCES categories(id) ON DELETE CASCADE
);

-- 인덱스 추가
CREATE INDEX idx_categories_parent_id ON categories(parent_id);

1.3 작업 예시

앞서 예시로 든 계층 구조를 기반으로 한 일반적인 작업 예시입니다:


-- 재귀적 CTE를 사용한 전체 트리 조회 (MySQL 8.0+, PostgreSQL)
WITH RECURSIVE category_tree AS (
    SELECT id, name, parent_id, 0 AS level
    FROM categories
    WHERE parent_id IS NULL
  
    UNION ALL
  
    SELECT c.id, c.name, c.parent_id, ct.level + 1
    FROM categories c
    JOIN category_tree ct ON c.parent_id = ct.id
)
SELECT id, LPAD(' ', level * 2) || name AS tree
FROM category_tree
ORDER BY level, id;

1.4 장단점 및 최적화 전략

장점:
- 구현이 간단하고 직관적
- 노드 추가/삭제가 용이
- 대부분의 ORM에서 기본 지원
- 외래 키 제약 조건으로 데이터 무결성을 보장
단점:
- 깊은 계층 조회 시 성능 이슈가 있을 수 있음
- 재귀 쿼리 혹은 애플리케이션에서 반복 조회 필요
최적화 전략:
- application level에서 트리 구조 구성
- 데이터가 커지고 쿼리가 복잡해지면 Materialized Path로 마이그레이션 고려

1.5 적합한 사용 사례

2~3단계의 단순한 카테고리 구조
- 예: 대분류 > 중분류 > 소분류
간단한 메뉴 시스템
- 드롭다운 메뉴와 같은 UI에 적합
- 깊이가 깊지 않은 네비게이션 구조
댓글 시스템
- 대댓글이 1~2단계 정도인 경우

2. Materialized Path (구체화된 경로)

2.1 기본 개념

각 노드에 루트부터 해당 노드까지의 전체 경로를 문자열로 저장하는 방식입니다. 각 노드는 자신의 위치를 나타내는 경로 정보를 가지며, 이를 통해 계층 구조를 표현합니다.

계층 구조 예시

/ (Root)
├── 전자제품 (/1/)
│   ├── 스마트폰 (/1/2/)
│   │   ├── 아이폰 (/1/2/5/)
│   │   │   └── 아이폰 14 (/1/2/5/8/)
│   │   └── 갤럭시 (/1/2/6/)
│   │
│   ├── 노트북 (/1/3/)
│   │   ├── 맥북 (/1/3/7/)
│   │   └── 갤럭시북 (/1/3/9/)
│   │
│   └── 태블릿 (/1/4/)
│
└── [다른 최상위 디렉토리들...]

위 예시에서 각 파일/폴더는 다음과 같이 저장됩니다:

Level	Name	Path	Display_Order
1	전자제품	/1/	1
2	├── 스마트폰	/1/2/	1
3	│ ├── 아이폰	/1/2/5/	1
4	│ │ └── 아이폰 14	/1/2/5/8/	1
3	│ └── 갤럭시	/1/2/6/	2
2	├── 노트북	/1/3/	2
3	│ ├── 맥북	/1/3/7/	1
3	│ └── 갤럭시북	/1/3/9/	2
2	└── 태블릿	/1/4/	3

상위-하위 관계:
- 각 노드는 자신의 path를 통해 전체 계층 구조를 표현
주요 작업:
- 직계 자식 조회: WHERE path LIKE '/1/2/%' AND level = 3
- 모든 하위 항목 조회: WHERE path LIKE '/1/2/%'
- 특정 깊이의 항목 조회: WHERE path LIKE '/1/%' AND level = 3
- 부모 경로 추출: SUBSTRING_INDEX(SUBSTRING_INDEX(path, '/', -2), '/', 1)

2.2 테이블 구조

CREATE TABLE product_categories (
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(255) NOT NULL,
    path VARCHAR(512) NOT NULL,  -- 예: /1/2/5/
    level TINYINT UNSIGNED NOT NULL,
    display_order INT NOT NULL DEFAULT 0,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    updated_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP
);

-- 인덱스
CREATE INDEX idx_product_categories_path ON product_categories(path(200));
CREATE INDEX idx_product_categories_level ON product_categories(level);
CREATE INDEX idx_product_categories_parent ON product_categories((SUBSTRING_INDEX(SUBSTRING_INDEX(path, '/', -2), '/', 1))); -- 부모 ID 인덱스
-- 4. 자주 사용되는 조회를 위한 커버링 인덱스
CREATE INDEX idx_product_categories_covering ON product_categories(path, level, name);

2.3 작업 예시

-- 특정 경로 아래의 모든 항목을 트리 구조로 조회 (계층 및 순서 유지)
SELECT 
    id, 
    CONCAT(REPEAT('  ', level - 1), 
           CASE WHEN level > 1 THEN '└── ' ELSE '' END, 
           name) AS tree_view
FROM product_categories
WHERE path LIKE '/1/2/%'  -- /문서/ 아래의 모든 항목
ORDER BY 
    path,                 -- 부모-자식 관계 유지
    display_order;        -- 형제 노드 간 순서 유지

-- 2. 특정 노드의 직계 자식 조회
SELECT * FROM product_categories 
WHERE path LIKE '/1/2/%'
  AND level = 3
ORDER BY path;

-- 3. 부모 경로로 이동
SELECT * FROM product_categories 
WHERE id = (
  SELECT CAST(SUBSTRING_INDEX(SUBSTRING_INDEX(path, '/', -2), '/', 1) AS UNSIGNED)
  FROM product_categories 
  WHERE id = 8
);

2.4 장단점 및 최적화 전략

경로 형식: 선행/후행 구분자 포함 (예: /1/4/7/)

장점:

탐색 성능
- 하위 트리 조회 시 단일 쿼리로 처리 가능
  - 예: WHERE path LIKE '/1/4/%'로 모든 하위 노드 조회
쿼리 효율성
- 특정 레벨, 하위 트리, 조상 경로에 대한 유연한 쿼리 가능
- 경로 기반으로 한 번에 계층 구조 파악 가능
인덱스 활용
- LIKE '경로%' 조건에서 B-Tree 인덱스 효율적 사용
  - 특히 = 또는 LIKE '경로%' 조건에서 B-Tree 인덱스가 효과적으로 작동
- Adjacency List에 비해 깊은 계층에서도 일관된 성능 제공

단점:

유지보수 오버헤드 - 트리 구조 변경 시 고비용
- 노드 이동 시 하위 모든 노드 경로(path)를 업데이트 필요
  - 예: /1/2/를 /1/3/으로 이동하면, /1/2/ 아래의 모든 노드 경로도 함께 업데이트 필요
경로 기반 제약사항
- 경로 문자열 길이 제한 (일반적으로 255자 - 데이터베이스에 따라 상이)
- 깊은 계층 구조에서 LIKE 쿼리 성능 저하 가능성
  - LIKE '%/X/%'와 같은 전방 일치가 아닌 패턴 검색은 인덱스 효율이 떨어짐

최적화 전략:

성능 최적화:
- 경로 길이 제한 설정, 일반적인 문자와 겹치지 않는 구분자(예: |, >) 사용
- 자주 사용되는 쿼리 패턴에 맞춰 인덱스 설계
- 대량 업데이트 시 일괄 처리

2.5 적합한 사용 사례

적합한 경우:

트리 구조 변경이 빈번하지 않은 읽기 위주의 계층 구조 (예: 조직도, 카테고리, 메뉴 구조)
전체 경로를 자주 표시해야 하는 경우 (예: 파일 경로, 브레드크럼 내비게이션)
트리 깊이가 비교적 일정하거나 예측 가능한 경우
계층 구조의 임의 수준에 대한 쿼리가 필요한 경우 (예: 특정 레벨의 모든 노드 조회)

부적합한 경우:

트리 구조가 매우 자주 변경되는 경우
매우 깊은 수준의 트리에서 경로 문자열 길이 제한이 문제가 될 수 있는 경우

계층적 데이터 모델링 기법 - low-hill/Knowledge GitHub Wiki

목차

서론

Adjacency List (인접 리스트)

1.1 기본 개념

계층 구조 예시

1.2 테이블 구조

1.3 작업 예시

1.4 장단점 및 최적화 전략

1.5 적합한 사용 사례

2. Materialized Path (구체화된 경로)

2.1 기본 개념

계층 구조 예시

2.2 테이블 구조

2.3 작업 예시

2.4 장단점 및 최적화 전략

장점:

단점:

최적화 전략:

2.5 적합한 사용 사례