8.4 R-Tree 인덱스

8.4 R-Tree 인덱스

MySql 의 공간인덱스(Spacial Index) : R-Tree 인덱스 알고리즘을 이용해 2차원의 데이터를 인덱싱 하고 검색하는 목적의 인덱스

기본적인 내부 메커니즘은 B-Tree와 비슷하나 B-Tree 인덱스는 컬럼 값이 1차원의 스칼라 값인 반면, R-Tree인덱스는 2차원의 공간 개념 값이다.

MySql의 공간확장(Spatial Extension)을 이용하면 위치기반 서비스를 구현하기 쉽다.

MySql의 공간확장의 기능

• 공간 데이터를 저장할 수 있는 데이터 타입
• 공간 데이터이 검색을 위한 공간 인덱스(R-Tree 인덱스)
• 공간 데이터의 연산 함수(거리 또는 포함 관계의 처리)

8.4.1 구조 및 특성

MySql은 공간 정보의 저장 및 검색을 위해 기하학적 도형(Geometry) 정보를 관리할 수 있는 데이터 타입을 제공함.

GEOMETRY 타입은 나머지 3개의 슈퍼타입으로 POINT, LINE, POLYGON 객체를 모두 저장 가능.

공간 데이터 타입 참조

MBR : Minimum Bounding Rectangle, 도형을 감싸는 최소 크기의 사각형

이 사각형들의 포함 관계를 B-Tree 형태로 구현한 인덱스가 R-Tree 인덱스.

도형이 저장 되었을 때 만들어지는 인덱스 구조를 이해하려면 이 도형들의 MBR이 어떻게 되는지 알아야함.

• 최상위 레벨 : R1, R2, R-Tree의 루트 노드
• 차상위 레벨 : R2, R4, R5, R6, 도형 객체의 그룹, R-Tree의 브랜치 노
• 최하위 레벨 : R7 ~ R14, 각 도형을 제일 안쪽에서 둘러싼 점선 상자

8.4.2 R-Tree 인덱스의 용도

주로 위도, 경도 좌표 저장에 사용.

뿐만 아니라 좌표 시스템에 기반을 둔 정보에 대해서는 모두 적용할 수 있음(CAD/CAM 소프트웨어, 회로 디자인 등)

R-Tree는 각 도형의 MBR의 포함 관계를 이용해 만들어진 인덱스임.

따라서 ST_Contains() 또는 ST_Within() 등과 같은 포함 관계를 비교하는 함수로 검색하는 경우에만 인덱스를 이용할 수 있음.

현재 사용자의 위치로 부터 반경 5Km 이내의 음식점 검색

P를 기준으로 반경5km 이내의 점 위치를 검색할 경우

ST_Contains 또는 ST_Within을 사용해야함

SELECT * FROM TB_LOCATION
WHERE ST_CONTAINS(사각상자, px);

SELECT * FROM TB_LOCATION
WHERE ST_WITHIN(px, 사각상자);

사각 상자 예)
ST_GEOMFROMTEXT('POLYGON((175 150, 20 40, 50 60, 125 100, 175 150))');
-- ST_GEOMFROMTEXT 은 텍스트를 공간데이터 타입으로 변경해줌

P6을 반드시 제거 해야한다면

SELECT * FROM TB_LOCATION
WHERE ST_CONTAINS(사각 상자, px)
AND ST_DISTANCE_SPHERE(p, px) <= 5 * 1000 /* 5Km */

-- ST_DISTANCE_SPHERE : 두 점 사이의 거리 반환