Nested Set Model: 계층적 데이터 관리를 위한 효율적인 접근법

1. Nested Set Model 개요

Nested Set Model은 데이터베이스에서 계층적 데이터를 저장하고 관리하는 방법 중 하나입니다. 이 모델에서는 각 노드를 두 개의 숫자(lft, rgt)로 표현하여 계층 구조를 효율적으로 조회할 수 있도록 합니다.

2. Nested Set Model의 원리

트리 구조의 각 노드는 왼쪽 값(lft)과 오른쪽 값(rgt)을 가지며, 이를 통해 트리 계층을 표현합니다.

예를 들어, 다음과 같은 트리 구조를 생각해 보겠습니다.

       A
      / \
     B   C
    / \   \
   D   E   F

이를 Nested Set Model로 변환하면 다음과 같이 저장됩니다.

 

ID	Name	lft	rgt
1	A	1	10
2	B	2	5
3	C	6	9
4	D	3	4
5	E	5	6
6	F	7	8

3. Nested Set Model의 장점과 단점

 장점

1. 효율적인 계층적 데이터 조회
   • 트리의 특정 서브트리를 SQL 한 번으로 조회할 수 있음
   • JOIN 없이 계층 구조를 쉽게 표현 가능
2. 부모-자식 관계를 빠르게 조회 가능
3. 트리 전체를 빠르게 탐색 가능

단점

1. 삽입, 삭제, 이동이 복잡함
   • 새로운 노드를 추가하거나 삭제할 때, 기존의 lft, rgt 값을 변경해야 함
   • 노드 이동 시 전체 lft, rgt 값 조정이 필요하여 성능 부담이 있음
2. 트리 구조 변경 시 성능 저하
   • 노드 추가, 삭제, 이동 시 전체 데이터에 영향을 미칠 수 있음

4. Nested Set Model을 활용한 SQL 쿼리

4.1 서브트리 조회하기

특정 노드(A)의 모든 자식 노드 조회:

SELECT * FROM tree WHERE lft BETWEEN 1 AND 10;

4.2 부모 노드 찾기

특정 노드(E)의 부모 찾기:

SELECT * FROM tree WHERE lft < 5 AND rgt > 6 ORDER BY lft DESC LIMIT 1;

4.3 노드 삽입 알고리즘

새로운 노드를 추가할 때는 lft, rgt 값을 조정하는 알고리즘이 필요합니다.

1. 새로운 노드를 삽입할 위치를 결정
2. 기존 노드들의 rgt 값을 조정하여 공간 확보
3. 새 노드의 lft, rgt 값을 설정

4.4 노드 삭제 알고리즘

삭제할 노드의 lft, rgt 범위에 있는 값을 삭제한 후, 나머지 값을 업데이트하는 방식으로 진행됩니다.

DELETE FROM tree WHERE lft BETWEEN 3 AND 4;
UPDATE tree SET lft = lft - 2 WHERE lft > 4;
UPDATE tree SET rgt = rgt - 2 WHERE rgt > 4;

5. Nested Set Model vs. Adjacency List Model

Nested Set Model을 선택해야 하는 경우

• 트리 구조에서 조회가 빈번하고, 변경이 드문 경우
• 계층 구조를 SQL 한 번으로 쉽게 조회해야 하는 경우

Adjacency List Model을 선택해야 하는 경우

• 삽입/삭제가 빈번한 트리
• parent_id를 이용한 단순한 계층 구조가 필요한 경우

6. 결론

Nested Set Model은 계층적 데이터를 SQL 한 번으로 효율적으로 조회할 수 있는 강력한 모델이지만, 삽입/삭제가 빈번한 경우 성능 문제가 발생할 수 있습니다. 따라서, 사용 목적에 따라 Nested Set Model과 Adjacency List Model을 적절히 선택하는 것이 중요합니다.