RDBMS 계층 구조 4가지 모델(Nested Set, Adjacency List, Materialized Path, Closure Table)

관계형 데이터베이스에서 계층 구조를 표현하는 4가지 주요 모델(Nested Set, Adjacency List, 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: 모든 계층 관계를 명시적으로 저장하므로 탐색 성능이 뛰어나지만, 데이터 중복과 관리의 복잡성이 존재함.

 

각 모델은 데이터베이스의 크기, 트리의 깊이, 쿼리 패턴 등에 따라 적절히 선택되어야 합니다.