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

태기 2024. 8. 27. 17:50

관계형 데이터베이스에서 계층 구조를 표현하는 4가지 주요 모델(Nested Set, Adjacency List, Materialized Path, Closure Table) 설명과 각각의 장단점을 간단하게 정리해보겠습니다.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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