R-Tree 공간 인덱스와 MBR 기반 다차원 검색
R-Tree의 MBR 계층 구조, 삽입·삭제 유지관리, 범위·포함·근접 이웃 검색 방식과 공간 데이터베이스 운영 설계를 정리한다.
2026-08-14 · 최초 발행 2024-04-29
공간 객체를 MBR 계층으로 탐색하는 방식
R-Tree는 N차원 객체를 최소 경계 사각형(MBR, Minimum Bounding Rectangle)으로 요약하고, 여러 MBR을 다시 상위 MBR로 감싸는 M원(M-ary) 균형 트리다. 점·선·폴리곤·3D 솔리드처럼 형태가 다른 객체도 경계 상자로 다룰 수 있어, 교차·포함·근접 이웃 질의를 위한 공통 탐색 구조를 제공한다.
리프 노드는 객체 MBR과 객체 식별자 또는 포인터를 보관한다. 내부 노드는 하위 노드를 감싸는 MBR과 자식 포인터를 저장한다. 모든 리프는 같은 깊이를 유지하며, 각 노드의 엔트리 수는 최소 m, 최대 M 범위에 놓인다.
삽입과 삭제가 발생해도 트리 전체를 다시 만들지 않는다. 국소적인 분할, 병합, 재삽입으로 구조를 유지하므로 CAD/3D 설계나 GIS처럼 공간 데이터를 계속 갱신하는 시스템에서 동적 인덱스로 사용할 수 있다.
노드가 담는 정보와 균형 조건
객체 MBR은 실제 공간 객체의 경계 상자를 나타내는 요약 정보다. 리프 노드는 이 MBR을 객체 식별자나 포인터와 함께 저장하며, 디스크 페이지 경계에 맞춘 고정 크기 레코드로 구성할 수 있다.
내부 노드에는 자식 MBR 전체를 감싸는 상위 MBR과 자식 포인터가 들어간다. 상위로 올라갈수록 더 넓은 영역을 포괄하지만, 면적 증가를 억제해야 불필요한 탐색 경로를 줄일 수 있다.
모든 리프의 깊이가 같으므로 검색 시간은 O(log_M N)을 기대할 수 있다. 노드를 페이지 단위로 매핑하면 디스크 I/O를 줄이는 데도 유리하다. 분기도 M은 페이지 크기, 키와 포인터 크기, MBR 좌표 정밀도를 함께 고려해 정하며, m≈0.4M가 권장된다.
삽입과 삭제에서 트리를 유지하는 방법
새 객체를 넣을 때는 면적 증가가 가장 작은 서브트리를 우선 선택한다. 이후 면적, 겹침 증가를 기준으로 선택을 좁힌다. 노드가 최대 엔트리 수를 넘으면 선형 또는 이차 분할 알고리즘으로 분리한다.
삭제는 대상 객체가 있는 리프에서 시작한다. 제거 후 엔트리 수가 최소 m에 못 미치면 노드를 축소하고 엔트리를 재삽입하는 CondenseTree 과정을 수행한다. 이 방식은 온라인 삽입·삭제를 처리하면서도 전체 인덱스 재구성을 피한다.
질의 조건에 따라 달라지는 가지치기
범위 질의에서는 노드 MBR과 질의 영역이 교차하는지 확인한다. 교차하지 않는 서브트리는 탐색하지 않는다. 다만 MBR이 겹치면 여러 경로를 방문할 수 있다.
포함 질의에서는 질의 영역이 노드 MBR을 완전히 포함할 때 해당 서브트리를 일괄 수용(accept)할 수 있다. 일부만 겹치는 경우에는 하위 노드로 재귀 탐색을 이어 간다.
근접 이웃 검색은 노드와 질의 사이의 최소거리(minDist)를 우선순위 큐에 넣는 Best-First 방식으로 수행한다. 현재 최적 거리보다 먼 노드는 제외하고, 가까운 후보부터 확장한다.
범위·포함·근접 이웃 검색의 공통 흐름
질의는 교차, 포함, 근접 이웃 중 하나의 형태로 루트 노드에서 시작한다. 각 단계에서 노드 MBR과 질의 Q의 교차·포함·거리 관계를 검사하고, 조건을 만족하지 않는 서브트리를 가지치기한다. 결과는 조건을 충족하는 객체 식별자 집합이다.
빈 트리 또는 비정상 MBR이 입력되면 빈 결과 또는 예외를 반환한다. 경계가 맞닿는 상황에서는 수치 오차를 고려해 epsilon 허용치를 적용할 수 있다. MBR 겹침으로 여러 경로를 방문할 수 있지만, 동일 객체는 리프에 단일 저장하는 것이 원칙이므로 결과 중복은 OID 기준으로 제거한다.
CAD, GIS, 공간 분석에서의 사용
CAD/3D 설계에서는 부품과 어셈블리의 BBox를 인덱싱해 충돌 검사, 간섭 체크, 가시화 레벨-오브-디테일(LOD) 선택을 빠르게 처리한다. 대용량 3D 장면에서는 카메라 프러스텀과 교차하는 객체를 선별하는 용도로도 쓰인다.
GIS와 차량 관리, 항법에서는 도로 링크, 지하철 폴리라인, 건물 폴리곤의 범위·포함·근접 질의를 가속한다. GPS 위치를 기준으로 가장 가까운 POI, 차량, 긴급 시설을 찾는 k-NN 탐색에도 적용할 수 있다.
공간 조인에서는 두 레이어의 MBR을 먼저 비교해 후보를 줄이고, 그 뒤 정밀 지오메트리 연산을 수행한다. 드론·위성 타일 인덱싱, 위험 구역 근접 경보, 지자체 시설 배치 최적화도 같은 구조를 활용할 수 있다.
인덱스 설계에서 조정할 지점
페이지 크기가 4–16KB일 때는 포인터와 좌표 정밀도(float/double)를 고려해 M을 산정한다. 좌표 정밀도를 높이면 M이 감소하는 트레이드오프가 있으며, 메모리 캐시 친화성도 함께 봐야 한다.
선형 분할은 삽입이 빠르지만 MBR 겹침이 커질 수 있어 평균 검색 성능에서 불리하다. 이차(Quadratic) 분할은 삽입 비용이 증가하는 대신 겹침과 면적 증가를 억제한다. R*-Tree는 재삽입(reinsert)으로 겹침을 더 줄이지만, 삽입 지연 비용이 따른다.
서브트리 선택 시에는 면적 증가, 겹침 증가, 환경 적합성(주변 둘레 증가) 순으로 타이브레이크할 수 있다. 포함 질의에는 accept 최적화를 적용하고, NN에는 Best-First(BF) 탐색을 사용하는 방식이 권장된다.
동시성 제어에는 B-Tree와 유사한 라칭(latch) 계층을 적용할 수 있다. 상향식 삽입에서는 부모와 자식 순서로 락을 잡고, 분할 시 스플릿 세이프티를 확보한다. 쓰기가 잦은 환경에서는 버퍼풀 핀, 쓰기 집약 배치, 체크포인트 주기 조정도 고려 대상이다.
대량 적재 시에는 공간곡선(Z-order, Hilbert)으로 정렬한 뒤 Bulk-load를 수행해 초기 겹침을 줄인다. 정기적인 Vacuum이나 MBR 재계산은 필요 없지만, 지오메트리가 대량으로 바뀌면 재빌드-대체 전략이 더 효율적일 수 있다.
R-Tree 계열의 선택 기준
| 지표 | R-Tree | R*-Tree | R+Tree |
|---|---|---|---|
| 검색 성능 | 보통, 겹침 영향 큼 | 우수, 겹침·면적 최소화 | 겹침 제거, 경로 증가 가능 |
| 공간 활용 | 높음 | 높음 | 중복 저장으로 증가 |
| 노드 겹침 | 중간~높음 | 낮음 | 없음(분할 시 중복 배치) |
| 삽입/분할 비용 | 낮음~보통 | 보통~높음(재삽입) | 보통(중복 관리) |
| 운영 편의 | 단순 | 중간(튜닝 필요) | 중간(중복 처리 주의) |
선형 스캔과 비교하면 디스크 페이지 접근은 데이터 분포와 M에 따라 7095% 감소할 수 있다. 범위·포함 질의의 평균 지연은 320배, k-NN 질의는 210배 단축을 기대할 수 있다. 수천만수억 개 객체에서도 로그 스케일 탐색을 유지하며, 분산 파티셔닝과 병행하면 수평 확장이 용이하다. 동적 삽입과 삭제를 지원하므로 배치 리빌드 없이 운영 가용성을 높일 수 있다.