R-Tree로 공간 인덱스 설계하기: MBR 기반 범위·근접 질의

객체가 아니라 MBR을 따라 공간을 찾는다

R-Tree는 2D·3D 공간 객체의 범위 질의와 교차 검사를 위한 균형 인덱스다. 각 객체를 감싸는 최소 경계 사각형(Minimum Bounding Rectangle, MBR)을 엔트리로 저장하고, 이 MBR을 계층적으로 묶는다.

내부 노드는 자식 노드의 MBR을 보관한다. 리프 노드에는 실제 객체 또는 객체 식별자와 해당 MBR이 들어간다. 노드는 페이지 크기 기반의 용량 M을 가지며, 트리 높이는 균형을 유지한다.

평균 탐색 복잡도는 O(log_M N)을 기대할 수 있다. 다만 데이터 분포가 고르지 않거나 MBR 중첩이 심해지면 탐색이 넓어져 최악의 경우 O(N)이 될 수 있다. R*-Tree는 중첩을 줄이는 방식으로 평균 성능을 개선한다.

삽입부터 질의까지의 경로

새 객체를 넣을 때는 루트부터 리프까지 내려가며, MBR 면적 증가가 가장 작은 자식 노드를 고른다. 리프에 엔트리를 넣은 뒤 노드가 넘치면 선형·이차 분할 또는 R*-Tree의 강제 재삽입을 수행한다. 이후 상위 노드의 MBR을 보정하고, 분할이 전파되면 루트도 분할될 수 있다.

삭제는 리프에서 엔트리를 제거한 뒤 시작한다. 언더플로우가 나면 노드를 병합하거나 엔트리를 재삽입하며, 경로를 거슬러 올라가면서 MBR을 축소한다. 내부 노드의 MBR은 언제나 자식 MBR을 포함해야 하므로, 이 불변식이 깨지면 전체 경로를 다시 계산해야 한다.

범위 질의는 질의 영역과 교차하는 MBR만 방문한다. k-최근접(kNN) 질의는 거리 하한을 기준으로 우선순위 큐를 사용하며, MINDIST와 MINMAXDIST 휴리스틱으로 후보를 줄인다. 공간 조인에서는 두 R-Tree를 함께 하향 탐색해 MBR이 겹치는 조합만 남긴다.

⤢✕

중첩을 줄이기 위한 구조적 선택

R-Tree의 성능은 MBR의 면적·둘레·중첩을 얼마나 낮게 유지하느냐에 달려 있다. 데이터 분포에 맞춰 묶일수록 탐색에서 제외할 수 있는 가지가 늘어난다. 격자나 균등 분할을 고정적으로 적용하는 대신, 실제 공간 분포에 맞춰 그룹을 형성한다는 점이 특징이다.

Guttman R-Tree는 선형 분할 O(M)과 이차 분할 O(M^2)을 제공한다. 구현 복잡도와 분할 품질 사이의 선택이 필요하다. R*-Tree는 강제 재삽입과 둘레 최소화 휴리스틱을 이용해 중첩과 면적을 낮추며, 평균 질의 성능에서 우수하다. 그만큼 삽입 비용은 커진다.

대용량 환경에서는 노드 크기를 디스크 페이지에 맞추고 I/O를 줄이는 설계가 필요하다. 고정·가변 엔트리를 함께 쓸 때는 패딩 전략도 고려 대상이다. 버퍼 캐시, 프리페치, 상위 레벨 상주 전략은 랜덤 I/O를 줄이는 데 쓰인다.

동시 갱신에서는 분할 전파와 MBR 중첩 때문에 잠금 범위 관리가 까다롭다. 래치 크래빙(latch crabbing), 레벨 단위 락 전략, 분할 시 상향 원자성 보장이 필요하다. 장애 복구는 로그 기반으로 다루며 루트 스플릿의 원자성도 보장해야 한다.

공간 데이터가 쓰이는 곳

PostGIS/GiST, SQLite R*Tree 모듈, MySQL InnoDB Spatial Index는 위치 기반 서비스와 GIS에서 활용된다. 지오펜싱, 반경 검색, 타일 인덱싱의 지연시간을 줄이는 용도다.

물류·모빌리티·IoT에서는 경로 근접 배차, 충돌 위험 감시, 영역 입출 이벤트 처리에 적용할 수 있다. 대량 트래픽 환경에서는 초단위 윈도우 집계와 조인 성능이 주요 관심사다.

CAD/BIM과 게임 엔진에서는 복잡한 형상의 충돌 감지 전처리, 뷰 프러스텀 컬링에 사용한다. 대규모 객체 집합에서 후보를 먼저 줄여 CPU와 메모리 사용량을 낮춘다.

페이지, 적재 방식, 차원이 만드는 차이

노드 크기는 스토리지 페이지(예: 4KB/8KB)에 맞추고, 목표 필 팩터는 70~85%로 잡는다. 노드가 작으면 깊이와 메타데이터 오버헤드가 증가한다. 반대로 너무 크면 MBR 중첩과 캐시 비효율이 커질 수 있다.

대량 초기 적재에는 STR/Hilbert bulk-load가 적합하다. 정렬·타일·재귀 방식으로 겹침을 줄인다. 점진 삽입은 실시간 갱신에 유리하지만, 시간이 지나며 형상이 왜곡될 수 있어 주기적인 리빌드가 필요하다.

차원이 높아지면 MBR 중첩이 빠르게 늘어난다. 고차원(>6~10)에서는 성능 저하를 고려해 X-Tree, SR-Tree, VA-File 같은 대안을 검토한다. 클러스터링이 좋지 않다면 지오해시·타일링 기반 파티셔닝과 혼합하는 방법도 있다.

리더-리더 공유락과 라이터 단독락 패턴을 적용할 수 있으며, 분할 시에는 상향 원자성을 보장해야 한다. WAL/Redo를 쓰는 시스템에서는 페이지 단위 로그와 루트 교체 로그를 분리한다.

인덱스	성능(범위/조인)	확장성(대용량)	일관성(중첩 관리)	안정성(갱신/복구)	운영 편의
R-Tree	중간	높음	중간(중첩 증가 경향)	높음	쉬움
R*-Tree	높음	높음	높음(중첩 최소화)	중간(재삽입 비용)	보통
Quadtree	중간(균등 분포)	보통	높음(불변 분할)	높음	쉬움
KD-Tree	낮음(범위/교차)	낮음(차원↑)	중간	높음	쉬움

분포·차원·페이지 크기에 따라 편차가 존재한다.

Python으로 인덱스 동작 확인하기

전제조건: Python 3.11, rtree>=1.2.0, libspatialindex 설치 필요.

# pip install rtree shapely
from rtree import index
from shapely.geometry import box

# 인덱스 생성(메모리)
p = index.Property()
p.fill_factor = 0.8
p.leaf_capacity = 64
p.index_capacity = 64
idx = index.Index(properties=p)

# 사각형 1만 건 적재
for i in range(10000):
    geom = box(i, i, i+1, i+1)          # (minx, miny, maxx, maxy)
    idx.insert(i, geom.bounds)

# 범위 질의
window = box(500, 500, 520, 520)
candidates = list(idx.intersection(window.bounds))
print(len(candidates))

# kNN 질의(중심 기준)
pt = (505, 505, 505, 505)               # 점도 4튜플로 표현
neighbors = list(idx.nearest(pt, 5))
print(neighbors)

초기 대량 적재에는 bulk-load API 또는 정렬 기반 삽입을 사용하고, 적재 뒤에는 통계 갱신과 VACUUM을 권장한다. PostGIS에서는 ST_CreateSpatialIndex와 ANALYZE를 활용하고, 테이블 클러스터링으로 로컬리티를 개선할 수 있다. SQLite RTree에서는 rowid 재사용에 주의하고 MBR 정확도를 위해 좌표를 정규화한다.

범위·교차 질의는 선형 스캔과 비교해 10100배 단축을 기대할 수 있고, 대형 공간 조인은 310배 단축을 기대할 수 있다. 랜덤 읽기는 3~20배 줄어들 수 있으며 버퍼 적중률 향상도 기대된다. CPU 필터링 부하와 애플리케이션 레벨 후보 수가 줄어 다운스트림 처리량 증가로 이어진다.

대신 MBR과 내부 노드 때문에 스토리지는 10~40% 추가 오버헤드를 가진다. 평균 질의 성능 이득이 이를 상쇄하는지, 데이터 분포와 갱신 패턴을 기준으로 판단해야 한다.