[DB 설계] 관계형 데이터베이스에서 계층 구조를 표현하는 4가지 방법

관계형 데이터베이스에서 카테고리, 조직도, 댓글과 같은 계층 구조를 표현해야 하는 경우가 많다.

이때 트리 구조를 어떻게 테이블로 설계하느냐에 따라
조회 성능, 데이터 수정 비용, 구현 복잡도가 크게 달라진다.

대표적으로 사용되는 Adjacency List, Nested Set, Materialized Path, Closure Table
네 가지 모델의 개념과 각각의 장단점을 간단하게 정리해본다.

 

1. Adjacency List Model(인접 리스트 모델)

: 각 노드가 부모 노드에 대한 참조를 포함하는 모델이다.
즉, 노드는 parent_id 필드를 통해 상위 노드와 연결된다.

 

장점

1. 구현이 간단하다 - 데이터베이스 테이블 설계가 직관적이며, 부모 노드의 ID만 추가하면 되므로 별도의 복잡한 구조가 필요하지 않다.

2. 삽입 및 삭제가 용이하다 - 단일 노드 삽입 및 삭제 작업이 빠르고 간단하다.

3. 기본적으로 거의 모든 RDBMS에서 지원한다 - 특별한 쿼리나 저장소 구조가 필요하지 않다.

단점

1. 트리 전체를 탐색하기 어렵다 - 자식 노드나 하위 계층을 찾으려면 반복적인 쿼리가 필요하여 성능이 저하될 수 있다.

2. 깊이 우선 탐색에 비효율적이다 - 모든 하위 노드를 조회하거나 트리 구조를 재귀적으로 탐색할 때 비효율적이다.

 

 

2. Nested Set Model(중첩 세트 모델)

: 트리 구조를 선형적으로 표현하며, 각 노드는 왼쪽 값과 오른쪽 값(즉, left, right 값)을 통해 트리의 위치를 나타낸다.

장점

1. 전체 트리 구조 조회가 매우 빠르다 - 트리나 서브트리를 한 번의 쿼리로 빠르게 조회할 수 있다.

2. 자식 노드, 조상 노드 등의 관계 조회가 효율적이다 - 관계를 쉽게 정의할 수 있다.

단점

1. 삽입, 삭제, 이동이 비효율적이다 - 새로운 노드 추가, 삭제, 위치 변경 시 left와 right 값이 바뀌므로 많은 노드를 업데이트해야 하므로 비효율적이다.

2. 구현이 복잡하다 - 트리 구조를 유지하기 위한 알고리즘이 복잡해질 수 있다.

 

 

3. Materialized Path Model(구체화 경로 모델)

: 각 노드가 루트부터 해당 노드까지의 경로를 문자열로 저장하여 트리 구조를 표현하는 모델이다.

장점

1. 전체 트리 및 서브트리 조회가 간단하다 - 문자열 패턴 매칭을 통해 특정 노드와 그 하위 노드들을 쉽게 조회할 수 있다.

2. 구현이 상대적으로 단순하다 - 경로만 저장하면 되므로 트리 구조를 유지하는 데 큰 복잡성이 없음.

단점

1. 삽입, 삭제, 이동 시 경로 업데이트가 필요하다 - 노드의 경로가 바뀌면 하위 노드들의 경로도 모두 변경해야 함.

2. 문자열로 처리한다 - 경로 정보가 문자열 형태로 저장되기 때문에 긴 트리의 경우 문자열 처리 비용이 증가할 수 있다.

 

 

4. Closure Table Model(폐쇄 테이블 모델)

: 트리의 모든 조상-자손 관계를 별도의 테이블에 저장하는 모델이다.
(ancestor, descendant) 형태의 모든 관계를 저장한다.

장점

1. 삽입, 삭제, 이동 시 경로 업데이트가 필요하다 - 노드의 경로가 바뀌면 하위 노드들의 경로도 모두 변경해야 함.

2. 트리 전체 탐색이 빠르다 - 조상-자손 관계를 명시적으로 저장하고 있기 때문에 탐색 성능이 뛰어나다.

3. 계층적인 연산에 적합하다 - 복잡한 트리 구조 내의 상호 관계 계산에 유리하다.

단점

1. 데이터가 중복이다 - 노드 간 모든 관계를 저장하기 때문에 테이블 크기가 매우 커질 수 있다.

2. 데이터 유지 관리가 복잡하다 - 삽입, 삭제, 이동 시에 추가적인 관계 데이터를 관리해야 한다.

 

 

비교 요약

• Adjacency List: 구현이 간단하고 삽입/삭제가 쉬우나, 트리 구조 전체를 탐색하기 비효율적.

• Nested Set: 트리 조회가 빠르지만, 삽입/삭제/이동 시 많은 노드가 업데이트되어야 하므로 성능이 저하될 수 있음.

• Materialized Path: 트리 탐색이 효율적이지만, 노드 경로 업데이트 시 복잡함이 발생.

• Closure Table: 모든 계층 관계를 명시적으로 저장하므로 탐색 성능이 뛰어나지만, 데이터 중복과 관리의 복잡성이 존재함.

 

 

계층 구조를 표현하는 방법에는 정답이 없다.
데이터의 크기, 트리 깊이, 조회 패턴, 그리고 수정 빈도를 고려해 상황에 맞는 모델을 선택하는 것이 중요하다.