R-Tree

R-Tree

다차원 공간 객체(점, 선, 면)를 경계 상자(MBR, Minimum Bounding Rectangle)로 그룹화하여 계층적으로 인덱싱하는 트리 자료구조로, 공간 데이터베이스와 GIS에서 범위 쿼리와 공간 조인에 사용

목적: 공간 인덱싱, 범위 쿼리, 최근접 이웃, GIS 데이터 관리

특징: MBR 기반, B-트리 변형, 중복 가능, 디스크 최적화

구성요소: ① MBR(Minimum Bounding Rectangle): 객체를 감싸는 최소 경계 사각형 ② 내부 노드: 하위 MBR 그룹 ③ 리프 노드: 실제 객체 저장 ④ 최대/최소 항목 수

동작

• •삽입: 면적 증가 최소 MBR 선택 → 재귀 삽입 → 오버플로우 시 분할
• •검색: MBR 겹침 확인 → 재귀 탐색
• •범위 쿼리: 쿼리 MBR과 겹치는 모든 노드 탐색

분할 전략: 선형 분할(빠름), 제곱 분할(품질), R*-트리(최적화)

시간 복잡도: 삽입·검색·삭제 O(log n), 범위 쿼리 O(k + log n) - k는 결과 수

공간 복잡도: O(n)

장점: 공간 쿼리 효율, 범위·KNN 지원, 디스크 I/O 최적화, 다양한 객체 타입

단점: 구현 복잡도, MBR 중복(검색 효율↓), 고차원 비효율

적용사례: GIS(지리 정보 시스템), 공간 데이터베이스(PostgreSQL PostGIS), CAD, 게임 엔진

변형: R+-Tree(중복 제거), R*-Tree(최적화), Hilbert R-Tree

비교: R-Tree(공간객체/MBR) vs KD-Tree(점/분할) vs B-Tree(1차원/정렬)

연관: GIS, 공간 인덱스, MBR, PostgreSQL PostGIS