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