[Algorithm] R-Tree

#자료구조/알고리즘

R-Tree는 B-Tree의 변종이라고 할 수 있는 자료구조다.
R은 Rectangle의 축약이다.

이건 지리적인 좌표 평면 기반으로 근접한 요소들을 찾는 것에 최적화되어있다.
쉽게 예를 들자면, "현재 위치에서 50km 이내의 식당을 전부 빠르게 찾아오는" 기능 같은 것을 구현하는 데에 쓴다.

기본 원리

공간에 최소 경계 사각형(MBR, Minimum Bounding Rectangle)이라는 사각형 영역을 정의하고, 이를 통해 인접 영역을 판별한다.

각각의 MBR은 다른 MBR에 속하거나 겹칠 수 있고, 이를 통해 포함이나 교차, 인접 연산을 빠르게 수행할 수 있다.
이것도 루트 노드에서 아래로 내려가면서 일치하거나 가까운 상세 좌표 값을 찾아가는 형태로 동작한다.

그리고 B-Tree와 마찬가지로, Tree level은 탐색을 위한 중간 단계일 뿐이고 모든 실제 데이터는 leaf 노드에만 위치한다. 그래서 캐시를 잘 타는 편이다.

B-Tree처럼 밸런스 관리도 기본으로 해야한다.
그래서 삽입/삭제시마다 Split/Merge가 빈번하게 일어난다.

복잡도
애초에 요구사항 자체가 비대하다보니 B-Tree 처럼 빠른 성능 (O(log N)) 보장은 안된다.
탐색 성능은 평균 O(log N), 최악 O(N)이다. 삽입도 최악 O(N)이다.

R-Tree의 단점을 개선한 변형 알고리즘으로 R+Tree, R*트리가 있다.
이름 짓는 꼬라지가 왜 이런건지

많은 좌표 검색 알고리즘들이 R-Tree나 R-Trer의 변형을 사용한다. GIS 계열들은 거의 다 그렇다.

일부 데이터베이스는 공간 기반 검색을 위해 R-Tree 타입 인덱스를 지원한다.
PostgreSQL은 기본 인덱스 타입으로 R-Tree를 지원한다.
MySQL의 Spatial Index은 공간 검색을 위한 R-Tree 기반 인덱스다.

대표적인 좌표 검색 환경인 PostgreSQL/PostGIS도 R-Tree 기반의 GIS 구현체다.