R-Tree index

MySQL에는 공간 인덱스(Spatial Index)가 존재한다. 공간 인덱스는 R-Tree 인덱스 알고리즘을 이용해서 2차원의 데이터를 인덱싱하고 검색하는 목적의 인덱스이다.

기본적인 내부 메커니즘은 B-Tree와 흡사한데, B-Tree는 인덱스를 구성하는 컬럼의 값이 1차원 스칼라이지만, R-Tree 인덱스는 2차원의 공간 개념 값이다.

스마트폰이 대중화되면서 GIS, GPS 기반의 서비스가 확장되고 있다. 이러한 위치 기반의 서비스를 구현하는 방법은 많지만 MySQL의 공간 확장(Spatial Extenstions)을 이용하면 간단하게 구현할 수 있다.

MySQL 공간 확장에는 세 가지 기능이 포함돼 있다.

• 공간 데이터를 저장할 수 있는 데이터 타입

• 공간 데이터의 검색을 위한 공간 인덱스(R-Tree (Range Tree) 알고리즘)

• 공간 데이터의 연산 함수(거리 or 포함 관계의 처리) 여기서는 R-Tree 알고리즘에 대해서만 학습하는 것을 목표로 한다.

구조 및 특성

MySQL은 공간 정보의 저장과 검색을 위해 여러 가지 기하학적 도형(Geometry) 정보를 관리할 수 있는 데이터 타입을 제공한다. MySQL에서는 크게 두 가지 카테고리로 나뉜다.

1. 단일 기하학을 저장하는 타입:

   • Point, Line, Polygon, Geometry

2. 여러 기하학의 값의 컬렉션을 저장하는 컬렉션 타입:

   • Multi-Point, Multi-Line, Multi-Polygon, GeometryCollection

대표적으로 MySQL에서 지원하는 공간 데이터 타입(Spatial Data Type)은 아래와 같다.

Goemetry 타입은 모든 종류의 공간 데이터를 저장할 수 있는 일반적인 타입으로, 기하학 값도 저장할 수 있다. 즉, POINT, LINE, POLYGON 객체도 저장할 수 있다. (= GeomCollection도 동일)

MBR(Minimum Bounding Rectangle): 최소 경계 사각형

공간 정보 검색을 위한 R-Tree를 이해하기 위해서는 MBR 개념을 알아야 한다. (핵심이다!)

MBR은 특정 도형을 감싸는 최소 크기의 사각형을 의미한다. 여기서 “특정 도형”은 MySQL에서 제공하는 공간 데이터 타입으로, 기하학적 객체를 의미한다.

아래 그림을 통해 확인해 보자.

R-Tree 자료구조는 B-Tree 와 흡사한 형태로 구성되어있다. 따라서 도형이 저장됐을 때 만들어지는 인덱스 구조를 이해해야 한다. 도형을 레벨로 나눠보자.

• 최상위 레벨: X, Y

• 최하위 레벨: A, B, C, D, E

최상위 MBR은 R-Tree의 루트 노드에 저장되는 정보이며, 최하위 레벨은 리프 노드가 된다.

• 또, 중간 레벨이 존재한다면 그 MBR은 브랜치 노드가 된다.

R-Tree 인덱스의 용도

R-Tree는 MBR 정보를 이용해 B-Tree 형태로 인덱스를 구축하므로 Rectangle의 ‘R’과 B-Tree를 섞어서 이름을 붙였으며, 공간(Spatial) 인덱스라고 한다. 일반적으로 WGS84(GPS) 기준의 위도, 경도 좌표 저장에 주로 사용된다.

또, 위 그림과 같이 R-Tree는 도형의 포함 관계를 이용해 만든 인덱스이다. ST_Contains() 또는 ST_Within() 등과 같은 포함 관계를 비교하는 함수로 검색을 수행하는 경우에만 인덱스를 이용할 수 있다.

대표적으로는 ‘현재 사용자의 위치로부터 반경 5km 이내의 음식점 검색’ 등과 같은 검색에 사용할 수 있다.

그림 8.24에서 ‘P’가 기준점이다. 기준점으로부터 반경 5km 이내의 위치(점)들을 검색하려면 사각 점선의 상자에 포함되는(ST_Contains() 또는 ST_Within() 함수 이용) 점들을 검색하면 된다.

• 여기서 contains(), within() 연산은 사각형 박스와 같은 다각형(Polygon)으로 연산할 수 있으므로, 반경 5km를 그리는 원을 포함하는 최소 사각형(MBR)으로 포함 관계를 수행한다.

• 점 ‘P6’은 5km 이상 떨어져 있지만 최소 사각형 내에는 포함된다.

여기서 점 ‘P6’을 제외하고 결과를 조회하려면 조금 복잡한 비교가 필요하다. P6을 결과에 포함시킨다면 다음 쿼리만 수행하는 것이 좋다.

# ST_Contains() 또는 ST_Within()을 이용해 "사각 상자"에 포함된 좌표 Px만 검색
mysql> select * from tb_location where ST_Contains(사각 상자, px);
mysql> select * from tb_location where ST_Within(px, 사각 상자);

contains()와 within() 함수는 거의 동일한 비교를 수행하지만 두 함수의 파라미터는 반대로 사용해야 한다.

• contains()의 첫 번째 파라미터는 포함 경계를 가진 도형을 명시하고 두 번째 파라미터는 포함되는 도형(또는 점 좌표)을 명시해야 한다.

• within()은 그 반대이다.

점 P6을 제외시키려면 contains() 비교 결과에 ST_Distance_Sphere()함수를 이용해 한번 더 필터링해야 한다.

mysql> select * from tb_location
       where ST_Contains(사각 상자, px) # 공간 좌표 Px가 사각 상자에 포함되는지 비교
         and ST_Distance_Sphere(p, px) <= 5 * 1000  # 5km 범위비교