B-Tree 인덱스가 인덱스를 구성하는 칼럼의 값이 1차원의 스칼라 값이라면,
R-Tree 인덱스는 2차원의 공간 개념 값이다.
Mysql은 공간 확장을 통해 공간 정보의 저장 및 검색 기능을 수행할 수 있는데, 이 기능에는 크게 세 가지 기능이 포함된다.
- 공간 데이터를 저장할 수 있는 데이터 타입
- 공간 데이터의 검색을 위한 공간 인덱스(R-Tree 알고리즘)
- 공간 데이터의 연산 함수(거리 또는 포함 관계의 처리)
구조 및 특성
Mysql이 공간 정보를 저장하기 위해 기하학적 정보(geometry) 관리를 제공하는 데이터 타입은 다음과 같다.
마지막의 geometry 타입은 point, line, polygon 객체를 모두 저장 가능한 슈퍼 타입이다.
공간 정보를 검색하는 R-Tree 알고리즘을 이해하려면 MBR 개념을 알아야 한다.
MBR은 Minimum Bounding Rectangle의 약자로, 해당 도형을 감싸는 최소 크기의 사각형을 의미한다.
이 사각형들의 포함 관계를 B-Tree 형태로 구현한 인덱스가 R-Tree 인덱스다.
위와 같은 도형 공간 데이터를 저장하려 할 때, 이 도형의 MBR이 어떻게 되는지 파악할 필요가 있다
위 공간 데이터들의 mbr은 다음과 같이 3계층으로 나눌 수 있다.
- 최상위 레벨 : R1, R2
- 차상위 레벨 : R3, R4, R5, R6
- 최하위 레벨 : R7 ~ R14
이 레벨에 따라 R-Tree에서 저장되는 위치가 다르다.
여기서 최상위 레벨은 루트 노드,
차상위 레벨은 브랜치 노드,
최하위 레벨은 리프 노드에 저장된다.
따라서 인덱스 내부는 다음과 같이 구성된다.
R-Tree 인덱스의 용도
R-Tree 인덱스는 위도, 경도 좌표 혹은 좌표 시스템 기반을 둔 정보에 대해서 적용 가능하다.
R-Tree는 도형의 포함 관계를 이용해 만들어진 인덱스이므로,
ST_Contains() 혹은 ST_Within() 등과 같은 포함 관계를 비교하는 함수로 검색을 수행할 때만, 인덱스를 이용할 수 있다. “현재 사용자의 위치로부터 반경 5km 이내의 음식점 검색”과 같은 검색에서 사용 가능하다.
> SELECT * FROM tb_location
WHERE ST_Contains(사각상자, px)
-> 첫 번째 인자로 받은 Geometry 객체(사각 상자) 안에,
두 번째 인자로 받은 Geometry 객체가 완전히 포함되는지를 검색
> SELECT * FROM tb_location
WHERE ST_Within(px, 사각상자)
-> 첫 번째 인자로 받은 Geometry 객체가,
두 번째 인자로 받은 Geometry 객체에 포함되는 지를 검색
> SELECT * FROM tb_location
WHERE ST_Contains(사각상자, px)
AND ST_Distance_Sphere(p,px) <= 5*1000
-> 사각 상자 안에 존재하고, 반경 5km 이내에 존재하는지 필터링, 이 때 p6는 결과 산출되지 않음