R*-Tree 공간 인덱스의 오버랩 최소화 전략

공간 질의의 병목은 트리의 깊이만으로 설명되지 않는다. 서로 겹치는 MBR이 많아지면 하나의 범위 질의가 여러 페이지를 넘나들고, 최근접 객체를 찾을 때도 후보가 불필요하게 늘어난다. R*-Tree는 이 겹침과 경계 길이를 줄이는 쪽으로 삽입과 분할을 설계한 공간 인덱스다.

MBR 품질을 관리하는 균형 트리

R*-Tree는 MBR(Minimum Bounding Rectangle) 집합을 트리 형태로 계층화한다. 내부 노드는 자식 노드들의 MBR을, 리프 노드는 실제 객체의 MBR을 저장한다. 트리 높이는 균형을 유지하며, 노드 용량은 M, 최소 용량은 m 제약을 따른다. 일반적으로는 m≈0.4M을 사용한다.

평균적인 탐색과 삽입의 시간 복잡도는 O(log_M N) 수준이다. 항목을 디스크 페이지 단위로 모아 I/O를 집약하고, 강제 재삽입과 세밀한 분할 기준으로 탐색 과정의 페이지 교차 방문을 줄인다.

삽입 시에는 서브트리를 고르고, 노드가 넘치면 재삽입 또는 분할을 선택한다.

⤢✕

서브트리 선택에서는 오버랩 증가량을 먼저 비교한다. 같다면 면적 증가량, 다시 같다면 둘레(경계 길이) 증가량이 작은 쪽을 고른다. 분할할 때는 경계 길이 합이 가장 작은 축을 고른 뒤, 오버랩을 우선하고 면적 증가량을 다음 기준으로 삼아 분배 위치를 결정한다.

오버플로를 분할로만 처리하지 않는 이유

R*-Tree의 차별점은 오버플로가 발생했을 때 항상 노드를 분할하지 않는 데 있다. 강제 재삽입(forced reinsertion)은 중심에서 가장 먼 p% 항목을 꺼내 상위에서 다시 삽입한다. 원본 기준 예시는 p=30%다.

이 과정은 삽입 시점의 비용을 높이지만, 국지적인 배치를 다시 조정해 공간적 군집화를 강화한다. 분할 횟수와 파편화를 줄여 이후 질의에서 겹치는 페이지를 방문할 가능성을 낮춘다.

범위, 교차, 포함 질의뿐 아니라 k-NN 질의에도 적합하다. 우선순위 큐를 사용하는 best-first 탐색과 함께 쓸 수 있으며, MBR의 경계 길이와 오버랩이 줄어든 만큼 I/O와 후보 수를 함께 줄일 수 있다.

대량 적재에서는 STR(Sort-Tile-Recursive) 같은 bulk loading을 결합할 수 있다. 초기 트리 품질과 빌드 시간의 균형을 잡고, 페이지 크기와 노드 팬아웃을 조정해 트리 높이와 캐시 효율을 관리한다.

공간 객체가 많은 시스템에서의 사용처

GIS와 위치 기반 서비스에서는 행정구역, 도로망, 건물 폴리곤을 인덱싱해 범위·교차 질의를 빠르게 처리한다. SQLite R*Tree 모듈과 MySQL(InnoDB) 공간 인덱스에서 활용되며, PostGIS는 GiST 기반으로 유사한 전략을 적용한다. 버전별 구현 차이가 있으므로 최신 정보 확인이 필요하다.

실시간 시뮬레이션과 게임에서는 AABB 기반 충돌 후보를 좁혀보는 broad-phase 단계에 맞는다. 동적 객체의 삽입과 삭제를 처리하면서 k-NN 기반 주변 탐색, 시야 판정, 사운드 전파 근접 처리에도 사용할 수 있다.

CAD/BIM, 3D 시티, LiDAR 환경에서는 대규모 도형과 포인트클라우드의 MBR을 인덱싱한다. 시각화 타일링과 범위 필터링을 가속하고, 레벨오브디테일(LOD) 결정 및 스트리밍 I/O 절감에 활용할 수 있다.

읽기 성능과 삽입 비용의 교환

R*-Tree는 R-Tree와 비교해 범위·최근접 질의 I/O를 15~40% 줄일 수 있으며 캐시 적중률 상승을 기대할 수 있다. 다만 데이터 분포와 차원 수에 따라 편차가 존재한다.

그 대가로 삽입에는 재삽입과 휴리스틱에 따른 10~25%의 비용 증가가 수반된다. 읽기 비중이 높은 워크로드일수록 전체 소요 시간 개선 효과가 커진다.

노드 팬아웃을 맞추면 트리 높이를 낮추고 대규모 타일·샤딩 환경에서 선형적 확장성을 확보할 수 있다. 오버랩을 낮추는 방식은 최악 상황에서의 성능 열화 가능성도 완화한다. 운영 중에는 페이지 크기, M/m, 재삽입 비율 p 사이의 성능-비용 트레이드오프를 조정해야 하며, 대량 적재 후에는 주기적인 Repack/Rebuild로 품질을 유지하는 방식을 고려할 수 있다.

지표	R-Tree	R*-Tree	R+Tree
범위/교차 질의 성능	중	상	상
kNN 성능	중	상	중~상
오버랩	중~상	낮음	거의 없음(분리 저장)
삽입 비용	낮음	중(재삽입/휴리스틱)	중~상(분리·복수 경로 관리)
운영 편의	높음	높음(튜닝 필요)	중(중복 관리 오버헤드)

주: 구현체·데이터 분포·차원 수에 따라 변동하며, DBMS/엔진별 차이가 존재한다. 최신 정보 확인이 필요하다.

페이지와 질의 특성에 맞춘 튜닝

노드 용량 M은 페이지 크기와 엔트리 크기에 맞춰 정한다. 최소 용량은 m≈0.4M이 권장된다. 재삽입 비율 p는 2033% 범위에서 쓰기 부하와 읽기 성능의 균형을 보며 조정한다. 페이지 정렬과 압축은 416KB 페이지에서 효과적이고, 대용량 환경에서는 16~64KB도 검토할 수 있다.

읽기 비중이 큰 서비스라면 R*-Tree와 best-first k-NN을 우선 적용할 수 있다. 대량 적재는 STR bulk-load 뒤 선택적으로 Reinsert 패스를 수행하는 방식이 가능하다. 다만 고차원 데이터(>10D)에서는 R*-Tree의 효과가 저하될 수 있으므로 HNSW/IVF 같은 대안을 검토한다.

동시성 측면에서는 트랜잭션 격리 수준과 페이지 잠금 정책을 확인해야 한다. 대량 업데이트에는 배치 단위 커밋을 적용하고, 좌표계·단위를 포함한 지오메트리 정규화와 MBR 정밀도 관리를 통해 부동소수 오차 누적을 막는다. 백업과 복구 계획에는 인덱스 재생성 시간을 포함하며 온라인 리빌드 지원 여부도 점검한다.

Python rtree로 구성하는 R*-Tree

전제조건은 Python 3.10+, rtree 1.2.0, libspatialindex 1.9.3이며 설치 명령은 pip install rtree다.

# rtree 1.2.0 + libspatialindex 1.9.3 기준 실행 예시
from rtree import index
import random

# 인덱스 옵션: R*-Tree 알고리즘 사용(기본), 페이지/분할 파라미터 튜닝
p = index.Property()
p.dimension = 2
p.fill_factor = 0.7          # m≈0.4M 보장되도록 간접 제어
p.index_capacity = 64        # 내부 노드 용량 M
p.leaf_capacity = 64         # 리프 노드 용량 M
p.near_minimum_overlap_factor = 32  # R*-split 휴리스틱 관련
p.reinsert_factor = 0.3      # 강제 재삽입 비율 p

idx = index.Index(properties=p)

# 샘플 데이터: 2D 박스 10,000개 삽입
def rand_box(i):
    x, y = random.random()*1000, random.random()*1000
    w, h = random.random()*5, random.random()*5
    return (i, (x, y, x+w, y+h))

for i in range(10_000):
    id_, bbox = rand_box(i)
    idx.insert(id_, bbox)

# 범위 질의: 주어진 창과 교차하는 객체 검색
window = (100, 100, 120, 120)
hits = list(idx.intersection(window))
print(f"Range hits: {len(hits)}")

# k-NN 질의: 점에 가장 가까운 상위 5개
point = (110, 110, 110, 110)  # 점은 동일 좌표의 박스
nearest = list(idx.nearest(point, 5))
print("kNN:", nearest)

libspatialindex가 설치되지 않은 경우 ImportError가 발생할 수 있어 시스템 패키지 설치가 필요하다. 대량 삽입 시에는 배치 크기를 조정해 메모리 피크를 완화한다.

R*-Tree는 오버랩과 둘레를 줄이고 강제 재삽입을 적용해 읽기 지향 공간 워크로드의 성능을 높인다. 노드 용량, 재삽입 비율, 페이지 크기, bulk-load 전략을 함께 맞추면 GIS, 실시간 탐색, 3D 시각화처럼 대규모 공간 데이터를 다루는 환경에 적용할 수 있다.