관계형 DB 상에서의 Tree 모델 저장 및 조회

Algorithm2011. 12. 29. 02:18

관계형 DB 상에서의 Tree 모델 저장 및 조회

The Adjacency List Model
The Nested Set Model

http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

Tree와 같은 계층구조 데이터를 처리할 때면 늘상 조회 속도 문제로 골머리를 썩는다. 왜 이리 문제가 많은것일까?
허긴 평면구조의 관계형 DB 상에서 계층구조의 Tree 데이터가 쉽고 빠르게 조회되길 바라는 내가 더 이상하다.

모든 Tree 노드가 자신의 Parent 만을 참조하는 일반적 형태로 테이블을 구성했다면 데이터의 저장은 매우 빨리 처리될 것이나 조회는 재귀호출을 사용해야 하므로 매우 느려질 것이 자명하다. 양질의 네트웍과 고사양의 장비가 있기에 재귀적인 쿼리요청이 무리가 되지 않는다 하더라도 이를 피해갈 방법이 있다면 한번쯤 고민해 보는것도 나쁘진 않을듯 싶다.

이제부터 설계하고자 하는 시스템은 Tree 데이터의 저장(변경)보다는 조회 빈도가 월등히 높다고 가정한다. 그렇다면 저장시 부하가 걸리더라도 조회에 최적된 형태로 데이터를 유지하는 것도 나쁘지 않은 생각이다. 그렇다면 조회에 최적화된 Tree 데이터는 도대체 어떤 정보들을 포함하고 있어야 하며 어떻게 조회되어야 하는가? 이제 그 해답을 찾아보자..

아래 그림들을 유심히 살펴보자.
모든 노드들은 왼쪽 숫자와 오른쪽 숫자를 가지고 있으며 이를 "left" 와 "right" 라 지칭한다.
N-1에 시작하여 파란색 화살표는 노드 변경(추가 또는 삭제) 전의 경로이고, 붉은색 화살표하는 노드 변경(추가 또는 삭제)후의 경로이다. 파란 화살표를 따라 검은색 숫자를 순차적으로 따라가보면 변경전 Tree의 left, right 가 어떻게 구성되어 있는지 알 수 있을 것이다.

자. 이제 노드가 삽입 또는 삭제되었을 때 초록색 번호를 기준으로 특정 법칙에 따라 left, right 값이 shift(모든 숫자가 동일하게 증가하거나 감소함) 되어진다. 빨간 번호들이 shift 후의 left 와 right 값이다. 4가지 경우따라 shift 법칙이 틀려지는 것을 볼 수 있다.

1) 노드추가-1. 중간노드 삽입
NextSibling.left(3) 기준으로 업데이트 후 Node 삽입