이번 글에서는 R-트리(R-Tree)라는 자료구조를 살펴봅니다. R-트리는 공간(spatial) 데이터 인덱스를 효율적으로 저장하기 위해 설계된 트리 구조로, 공간 질의(spatial query)와 대용량 공간 데이터 저장에 매우 유용하게 활용됩니다.
R-트리의 주요 활용 분야
R-트리는 실제 다양한 산업 현장에서 사용되고 있으며, 대표적인 적용 사례는 다음과 같습니다.
- 다차원 정보(multidimensional information)의 인덱싱
- 게임 데이터 처리 및 관리
- 지리적 좌표(geospatial coordinates) 저장
- 가상 지도(virtual map) 구현
R-트리의 동작 예시
예를 들어 평면 위에 여러 객체들이 배치되어 있다고 가정해 보겠습니다.
이 공간 데이터를 R-트리로 표현하면 아래와 같은 계층 구조가 됩니다.
R-트리의 핵심 속성
R-트리를 제대로 이해하려면 다음과 같은 구조적 특징을 알아야 합니다.
- R-트리는 단일 루트(root), 내부 노드(internal node), 리프 노드(leaf node)로 구성됩니다.
- 루트 노드는 해당 공간 도메인에서 가장 큰 영역을 가리키는 포인터를 가집니다.
- 부모 노드는 자식 노드들을 포함하며, 각 자식 노드의 영역은 부모 노드의 영역 안에 완전히 포함(중첩)됩니다.
- 리프 노드에는 현재 객체에 대한 MBR 정보가 저장됩니다.
- MBR(Minimum Bounding Region, 최소 경계 영역)이란 대상 영역을 감싸는 최소 크기의 경계 상자(bounding box)를 의미합니다.
R-트리 vs 쿼드트리(Quad-tree) 비교
공간 인덱싱에 널리 쓰이는 또 다른 구조인 쿼드트리와 R-트리는 여러 면에서 차이를 보입니다. 두 자료구조를 비교하면 다음과 같습니다.
| 쿼드트리(Quad Tree) | R-트리(R-Tree) |
|---|---|
| 타일링(tiling) 수준의 최적화 작업이 필요함 | 별도의 최적화 과정이 필요하지 않음 |
| B-트리 기반으로 구성할 수 있음 | B-트리의 구조를 따르지 않음 |
| 공간 인덱스 생성 속도가 빠름 | 공간 인덱스 생성 속도가 상대적으로 느림 |
| 최근접 이웃(nearest neighbor) 질의는 느리지만, 윈도우(window) 질의는 빠름 | 최근접 이웃 질의는 빠르지만, 윈도우 질의는 느림 |
정리
R-트리는 지리 정보 시스템(GIS), 게임 엔진, 위치 기반 서비스 등 공간 데이터를 다루는 거의 모든 분야에서 활용되는 강력한 인덱싱 구조입니다. 최근접 이웃 검색에 강점을 가진 만큼, "가까운 매장 찾기"나 "주변 검색" 같은 기능을 구현할 때 특히 효과적입니다. 반면 인덱스 생성 속도나 윈도우 질의 성능이 중요한 상황이라면 쿼드트리와의 비교를 통해 용도에 맞는 구조를 선택하는 것이 좋습니다.