R-트리 변형인 Hilbert R-트리는 선, 영역, 3D 개체 또는 고차원 기능 기반 매개변수 개체와 같은 다차원 개체에 대한 인덱스로 정의됩니다. 다차원 개체에 대한 B+-트리의 확장으로 상상할 수 있습니다.
R-트리의 성능은 노드의 데이터 사각형을 클러스터링하는 알고리즘의 품질에 따라 다릅니다. Hilbert R-tree는 데이터 직사각형에 선형 순서를 부과하기 위해 공간 채우기 곡선, 특히 Hilbert 곡선을 구현합니다.
Hilbert R-tree는 두 가지 유형이 있습니다. 하나는 정적 데이터베이스용이고 다른 하나는 동적 데이터베이스용입니다. 두 경우 모두 노드에서 다차원 객체의 더 나은 순서를 달성하기 위해 Hilbert 공간 채우기 곡선이 구현됩니다. 이 순서는 '유사한' 데이터 직사각형을 함께 그룹화하여 결과 MBR(최소 경계 직사각형)의 면적과 둘레를 줄여야 한다는 의미에서 '양호'로 취급되어야 합니다. Packed Hilbert R-tree는 업데이트가 매우 드물거나 업데이트가 전혀 없는 정적 데이터베이스에 유용합니다.
기본 아이디어
다음 예제는 정적 환경을 위한 것이지만 좋은 R-트리 디자인을 위한 직관적인 원칙에 대해 설명합니다. 이러한 원칙은 정적 및 동적 데이터베이스 모두에 적합합니다.
Roussopoulos와 Leifker는 거의 100% 공간 활용도를 달성하는 패킹된 R-트리를 구성하는 기술을 제안했습니다.
아이디어는 직사각형 모서리 중 하나의 x 또는 y 좌표에 대한 데이터를 정렬하기 위해 개발되었습니다. 4개의 좌표 중 하나를 기준으로 정렬하면 동일한 결과가 나타납니다. 이 논의에서 점 또는 직사각형은 "lowx 패킹된 R-트리"로 표시된 직사각형의 왼쪽 하단 모서리의 x 좌표에 정렬됩니다. 사각형의 정렬된 목록을 스캔합니다. 노드가 가득 찰 때까지 그리고 그렇지 않은 경우 연속 직사각형이 유사한 R-트리 리프 노드에 할당됩니다. 그런 다음 새 리프 노드가 빌드되고 정렬된 목록의 스캔이 계속됩니다. 따라서 결과 R-트리의 노드는 각 수준의 마지막 노드를 제외하고 완전히 패킹됩니다. 이로 인해 공간 활용률이 ≈100%가 되도록 사고가 발생합니다. 더 높은 수준의 트리도 비슷한 방식으로 구축됩니다.
알고리즘 Hilbert-Pack
(R-트리에 직사각형 패킹)
1단계. 각 데이터 사각형에 대한 힐베르트 값이 계산됩니다.
2단계. 힐베르트 값의 오름차순으로 데이터 사각형이 정렬됩니다.
3단계. /* 리프 노드 생성(레벨 l=0) */
- 동안(직사각형이 더 있음)
- 새로운 R-트리 노드가 생성됨
- 이 노드에 다음 C 직사각형이 할당됩니다.
4단계. /* 상위 레벨에서 노드 생성(l + 1) */
- 동안(레벨 l에 1개 이상의 노드가 있음)
- 생성 시간이 오름차순으로 l ≥ 0인 노드가 정렬됩니다.
- 3단계 반복
여기서 가정은 데이터가 정적이거나 수정 빈도가 낮다는 것입니다. 이것은 ~100% 공간 활용도와 동시에 좋은 응답 시간을 갖는 R-트리를 구축하기 위한 간단한 경험적 방법입니다.