[Database] 계층적인 데이터 구조 관계형 DB에서 관리하는 방법

4가지 모델 소개

• 계층적인 클래스 구조를 가져가기 위해 DB에 저장하는 방식이 여러가지가 있습니다. 총 4가지의 방식이 있고 위의 표에서 각 방식의 장단점을 나타내고 있습니다.

1. Adjacency List

• Adjacency List는 테이블 1개로 계층적 구조를 나타낼 수 있습니다.

1.1 장점

• 스키마를 이해하기가 쉽습니다.
  • Parent_id 컬럼을 두어 해당 row의 부모가 어떤 row인지 쉽게 파악이 가능합니다.
  • 예를 들어 comment_id가 2인 row는 parent_id가 1이고 comment_id가 1인 row가 부모인 것을 알 수 있습니다.

1.2 단점

• 트리의 깊이가 깊어질수록 시간복잡도가 증가한다는 단점이 있습니다.
• 물론 현재 음식 계층은 3단계로 트리의 깊이가 깊지는 않지만 다른 방식에 비해 데이터가 많아질수록 조회하는데 시간이 오래 걸릴 수 있습니다.
• 성능이 다른 방식들에 비해 좋지 않습니다.

2. Path Enumeration

• path 컬럼에 각 계층 구조 경로를 string 형태로 명확하게 적어줌으로써 전체 경로를 빠르게 파악할 수 있습니다. 예를 들어 comment_id가 3인 경우는 path가 “1/2/3”으로 되어있고 comment_id가 2인 row가 부모 노드임을 알 수 있습니다.

2.1 장점

• path enumeration 방법은 path라는 컬럼을 통해서 전체 계층적인 구조가 어떻게 이루어지고 있는지 명확하게 바로 알 수 있습니다.

2.2 단점

• 트리가 깊어질수록 path의 string이 길어집니다.
• 쿼리를 할 때 string parsing이 필요해 큰 데이터셋에서 성능 저하를 일으킬 수 있습니다.
  • • SELECT * FROM mydata WHERE path LIKE ‘windows\system32\%’
• 참조 완결성이 없는 string 형태이므로 path가 잘못될 경우 어디가 잘못되어있는지 파악하기 힘듭니다.
  • 실제로 119라는 데이터가 없더라도 “1/2/3/119” 라는 데이터가 생성될 수 있습니다.
• 계층 구조를 변경할 때 cost가 비쌉니다.
  • 1/2/3/4 → 1/5/3/4 로 변경할 때 “1/2/3/”, “1/2/3/4”을 각각 “1/5/3”, “1/5/3/4/”등으로 수정해야하는데 string이라 변경하기가 어렵습니다.
• 큰 데이터셋에 대해 스케일링하기가 어렵습니다.

3. Nested Sets

• nested set 모델은 맨 상위부터 아래쪽으로 왼쪽에서 오른쪽으로 순서로 가며 번호를 붙입니다. 예를 들어 맨 위의 계층은 left가 1, right가 14이며 그 자식 노드는 left가 2 right가 5입니다. 자식 노드인지를 확인하는 방법은 자식 노드의 left가 부모 노드의 left와 right 사이에 있는지를 판단하여 그 안에 있으면 자식 노드인 것을 알 수 있습니다.

3.1 장점

• 트리의 깊이가 3단계 이상인 경우 조인의 오버헤드를 줄여 데이터 검색을 위해 발생하는 쿼리의 수가 매우 줄어듭니다.
• 매우 크고 동적인 계층 구조라면 Adjacency list보다 훨씬 낫고 다뤄보면 직관적입니다.

3.2 단점

• 참조 완결성이 없습니다. left와 right는 comment_id를 참조하는 것이 아니라 단지 노드의 숫자를 의미합니다. 따라서 nsleft, nsright가 잘못 들어갈 경우가 생깁니다.
• left와 right값이 모두 변경되어야 하므로 add/delete/move 에 대한 cost가 큽니다.
• 구조 상 멀티 쓰레드 환경에서 데이터를 변경할 경우 데이터의 손상이 있을 수 있기 때문에 해당 테이블의 데이터 변경을 여러 사용자가 동시에 진행할 수 없습니다.

4. Closure Table

• Closure Table은 테이블을 2개를 활용합니다. 왼쪽 테이블의 comment_id를 참조하여 오른쪽 테이블의 ancestor, descendant에 데이터를 삽입합니다. ancestor는 조상 노드, descendant는 후손 노드로 각 노드의 관계를, length 컬럼은 관계를 맺은 노드 간의 깊이 차이를 나타낸 것입니다. 3번 노드의 조상 노드를 찾는다면 descendant가 3인 ancestor를 찾아야 합니다. 2와 3이 있고 length가 1인 2가 부모 노드입니다.

4.1 장점

• 참조 완결성이 존재하므로 오른쪽 테이블의 ancestor, descendant 컬럼은 왼쪽 테이블의 comment id를 foreign key 로 참조하여 실제 있는 데이터를 참조하도록 설정 할 수 있습니다. path enumeration과 같은 문제점은 발생하지 않습니다.
• top/middle/leaf node 의 계층 구조에서 middle을 조작하기 쉽습니다.(add, move, delete)
• sub-tree를 사용하기 쉽습니다.
• 트리의 깊이가 깊더라도 시간 복잡도 면에서 큰 문제가 없습니다.

4.2 단점

• 오른쪽의 전체 row가 최악의 경우에 O(n2)으로 증가할 수 있습니다.

참고

Models for hierachical data

comparision between closure table and path enumeration

comparision between adjacency list and nested set model

comparision between adjacency list and nested set model2