힐베르트 R-트리란 무엇인가?
힐베르트 R-트리(Hilbert R-tree)는 R-트리의 변형으로, 선분, 영역(region), 3차원 객체, 고차원 특징 기반 파라메트릭 객체처럼 다차원 객체를 위한 인덱스로 정의됩니다. 다차원 객체를 위한 B+ 트리의 확장판이라고 생각하면 이해하기 쉽습니다.
R-트리의 성능은 노드에 데이터 사각형(data rectangle)을 어떻게 군집화(cluster)하느냐에 따라 크게 좌우됩니다. 힐베르트 R-트리는 공간 채움 곡선(space-filling curve), 그중에서도 힐베르트 곡선을 활용해 데이터 사각형에 선형 순서(linear ordering)를 부여합니다.
힐베르트 R-트리는 정적 데이터베이스용과 동적 데이터베이스용 두 가지 유형으로 나뉩니다. 두 경우 모두 노드 안에서 다차원 객체를 더 잘 정렬하기 위해 힐베르트 공간 채움 곡선을 사용합니다. 여기서 '좋은' 정렬이란 '유사한' 데이터 사각형끼리 묶어 최종적으로 만들어지는 최소 경계 사각형(MBR, Minimum Bounding Rectangle)의 면적과 둘레를 줄일 수 있는 순서를 의미합니다. 패킹된 힐베르트 R-트리(packed Hilbert R-tree)는 업데이트가 거의 없거나 전혀 없는 정적 데이터베이스에 특히 유용합니다.
기본 아이디어
아래 예제는 정적 환경을 전제로 하지만, 좋은 R-트리 설계를 위한 직관적인 원리를 담고 있습니다. 이 원리들은 정적 데이터베이스와 동적 데이터베이스 모두에 적용할 수 있습니다.
루수풀로스(Roussopoulos)와 라이프커(Leifker)는 거의 100%에 가까운 공간 활용률을 달성하는 패킹 R-트리(packed R-tree)를 구성하는 기법을 제안했습니다.
핵심 아이디어는 사각형 모서리의 x 좌표 또는 y 좌표 중 하나를 기준으로 데이터를 정렬하는 것입니다. 네 좌표 중 어느 것을 기준으로 삼아도 결과는 동일합니다. 이 글에서는 점 또는 사각형을 사각형의 왼쪽 아래 모서리 x 좌표로 정렬하며, 이를 "lowx 패킹 R-트리(lowx packed R-tree)"라고 부릅니다. 정렬된 사각형 목록을 순서대로 훑으면서 연속된 사각형들을 하나의 R-트리 리프 노드에 계속 할당하고, 해당 노드가 가득 차면 새 리프 노드를 만들어 스캔을 이어갑니다. 그 결과 각 레벨의 마지막 노드를 제외한 모든 노드가 꽉 차게 되어 공간 활용률이 약 100%에 도달합니다. 트리의 상위 레벨도 같은 방식으로 구축됩니다.
알고리즘: 힐베르트-팩(Hilbert-Pack)
사각형을 R-트리에 패킹하는 알고리즘은 다음과 같습니다.
1단계
각 데이터 사각형의 힐베르트 값을 계산합니다.
2단계
데이터 사각형을 힐베르트 값 오름차순으로 정렬합니다.
3단계 — 리프 노드 생성 (레벨 l = 0)
- while (정렬 대상 사각형이 남아 있는 동안)
- 새로운 R-트리 노드를 생성합니다
- 다음 C개의 사각형을 해당 노드에 할당합니다
4단계 — 상위 레벨 노드 생성 (레벨 l + 1)
- while (레벨 l에 노드가 1개보다 많은 동안)
- 레벨 l(l ≥ 0)의 노드를 생성 시간 오름차순으로 정렬합니다
- 3단계를 반복합니다
마무리: 적용 조건과 장점
이 알고리즘의 전제는 데이터가 정적이거나 수정 빈도가 낮다는 것입니다. 즉, 힐베르트-팩은 약 100%의 공간 활용률을 확보하면서 동시에 우수한 응답 시간(response time)을 유지하는 R-트리를 만들 수 있는 간단하지만 효과적인 휴리스틱입니다.