R트리 색인 (R-Tree Index)
한 줄 정의: R트리 색인은 공간 객체들을 최소경계사각형으로 감싸 계층적인 트리 구조로 정리함으로써 빠른 공간 검색을 가능하게 하는 대표적인 공간색인 기법입니다.
쉽게 풀면
R트리는 여러 개의 물건을 상자 안에 넣고, 그 상자들을 다시 더 큰 상자에 담는 방식과 비슷합니다. 지도 위의 여러 도형들을 작은 사각형 상자로 감싸고, 가까운 상자들을 묶어 더 큰 상자로 정리해 나가는 것입니다. 이렇게 하면 특정 지역을 검색할 때 관련 없는 큰 상자들은 아예 열어볼 필요가 없어 검색 속도가 크게 빨라집니다. GIS 소프트웨어와 공간 데이터베이스에서 매우 널리 쓰이는 기법입니다.
왜 중요한가
지도학 및 GIS 연구에서 방대한 공간 데이터를 다룰 때 검색 성능은 실용성과 직결됩니다. R트리는 비교적 구현이 간단하면서도 다양한 공간 질의에 효과적으로 대응할 수 있어, 여러 GIS 소프트웨어와 공간 데이터베이스에서 기본 색인 방식으로 채택되고 있습니다.
논문에서는 이렇게 쓰입니다
"본 연구에서는 대규모 벡터 데이터의 검색 효율을 높이기 위해 R트리 색인을 구축하였다."
이 문장은 벡터 형태의 지리 데이터를 빠르게 찾기 위해 R트리 구조를 만들어 사용했다는 뜻입니다.
"제안된 알고리즘은 R트리 색인을 기반으로 인접 객체 탐색 시간을 단축시켰다."
이 문장은 R트리를 활용해 주변에 있는 객체를 찾는 시간을 줄였다는 의미입니다.
조금 더 깊게 보면
R트리는 각 노드가 자신이 포함하는 하위 객체들을 모두 감싸는 최소경계사각형(MBR)을 가지며, 이 사각형들이 겹치는 정도를 최소화하도록 데이터를 삽입하고 조정합니다. 이후 R*트리 등 성능을 개선한 변형 구조들이 제안되기도 했습니다. PostGIS를 비롯한 여러 공간 데이터베이스가 R트리 계열의 색인을 기본으로 제공합니다.
주의할 점
데이터의 분포가 불균일하거나 사각형들이 많이 겹치는 경우 검색 효율이 떨어질 수 있으며, 색인을 구성하고 갱신하는 데에도 추가적인 연산 비용이 발생합니다.