Nested Set Model: 효율적인 트리 구조

실무에서 Nested Set Model로 구성된 데이터를 관리하면서 겪은 경험과 개념을 정리해보고자 합니다.👩🏻‍💻

 

 

Nested Set Model이란?

데이터베이스에서 트리 구조를 저장하는 방법에는 여러 가지가 있지만, Nested Set Model은 lft, rgt 값을 이용해 한 번의 SQL 쿼리로 전체 트리 구조를 빠르게 조회할 수 있는 방식입니다.

많은 경우, 부모-자식 관계를 나타내는 Adjacency List 방식을 사용하지만, 이 방법은 하위 노드를 조회할 때 반복적인 SQL 실행이 필요하다는 단점이 있습니다. 반면, Nested Set Model은 하나의 SQL로 모든 하위 노드를 조회할 수 있다는 강력한 장점이 있습니다.

(물론 둘을 혼용하여 쓰는 방법도 있습니다. 🤔)

 

Nested Set Model의 개념

Nested Set Model에서는 트리의 각 노드에 좌측 값(lft)과 우측 값(rgt)을 할당합니다.

 

✅ 예제 트리 구조

Root
├── Animal
            ├── Dog
            ├── Cat
├── Plants
            ├── Rose
            ├── Cosmos

 

✅ 트리를 Nested Set Model로 표현하면?

id	name	lft	rgt
1	Root	1	14
2	Animal	2	7
3	Dog	3	4
4	Cat	5	6
5	Plants	8	13
6	Rose	9	10
7	Cosmos	11	12

• lft와 rgt는 전위 순회(Preorder Traversal) 방식으로 결정됩니다.
• 부모 노드는 항상 lft 값이 작고, rgt 값이 큽니다.
• 특정 노드의 하위 노드는 lft와 rgt 값이 해당 부모의 lft, rgt 범위 내에 포함됩니다.

 

Nested Set Model을 활용한 SQL 예제

✅ 테이블 구조 설계

CREATE TABLE categories (
    id INT PRIMARY KEY AUTO_INCREMENT,
    name VARCHAR(255) NOT NULL,
    lft INT NOT NULL,
    rgt INT NOT NULL
);

 

✅ 하위 항목 조회 (Animal 아래의 모든 카테고리 찾기)

SELECT * FROM categories WHERE lft BETWEEN 2 AND 7;

 

✅ 부모 찾기 (Dog의 부모 찾기)

SELECT * FROM categories WHERE lft < 3 AND rgt > 4 ORDER BY lft DESC LIMIT 1;

 

 

Nested Set Model의 장점과 단점

✅ 장점

1. 빠른 조회
   → 한 번의 SQL 실행으로 전체 트리를 조회 가능합니다.
2. 트리 깊이가 깊어져도 성능 저하가 적습니다.

❌ 단점

1. 삽입, 삭제가 복잡
   → 새로운 노드를 추가하면 lft, rgt 값을 업데이트해야 합니다.
2. 동시성 문제 발생 가능
   → 다중 트랜잭션 환경에서 lft, rgt 업데이트 충돌 가능합니다.

 

Nested Set Model 적용 시 고려할 점

• 데이터 추가/삭제 시 트랜잭션을 사용하여 동시성 문제 해결.
• 대량 업데이트가 필요한 경우, Adjacency List와 혼용하여 최적화 가능.
• 최신 RDBMS에서 WITH RECURSIVE를 지원하는 경우, Nested Set Model 대신 계층형 쿼리(CTE)를 활용할 수도 있음.
• 트리 데이터가 자주 변경될 경우, 전체 lft, rgt 값을 업데이트해야 하므로 성능 영향을 고려해야 함.
• 트랜잭션 중단으로 인해 데이터 정합성이 깨질 수 있으므로, 트랜잭션 관리 및 롤백 전략을 신중하게 설계해야 함.

 

실무에서 경험한 Nested Set Model의 어려움

실무에서 Nested Set Model을 관리하면서 다음과 같은 어려움을 겪었습니다.

1. 전체 트리 업데이트 문제
   • lft, rgt 값이 깨지면 전체 데이터를 다시 계산해야 하는데, 데이터가 많아지면 이 작업이 오래 걸릴 수 있음.
   • 이를 방지하기 위해 트리 구조가 변경될 때마다 즉시 lft, rgt 값을 보정하는 로직이 필요함.
2. 동시성 문제
   • 여러 요청이 동시에 들어와 트리 업데이트가 발생하면 lft, rgt 값이 충돌할 가능성이 있음.
   • 트랜잭션을 활용해 정합성을 유지해야 하지만, 잠금(lock)을 과도하게 걸면 성능 저하가 발생할 수 있음.
3. 데이터 정합성 유지
   • 트랜잭션 중간에 실패하면 일부 데이터가 업데이트되지 않아 트리가 깨질 수 있음.
   • 이를 방지하기 위해 자동 복구 로직 또는 백업 후 복원 전략이 필요함.

 

 

실무에서는 전체 트리 업데이트의 비용과 트랜잭션 관리 문제를 고려하면서 적용하는 것이 중요합니다.
트랜잭션 관리와 동시성 처리 방안을 마련하지 않으면 데이터 정합성이 깨질 가능성이 있으므로 신중한 설계가 필요합니다. 🚀