R-Tree 인덱스

공간 인덱스 (Spatial Index)

공간 인덱스란

• R-Tree 인덱스 알고리즘을 이용해 2차원의 데이터를 인덱싱하고 검색하는 목적의 인덱스다.
• 기본적인 내부 메커니즘은 B-Tree와 흡사하다.
• B-Tree는 인덱스를 구성하는 칼럼의 값이 1차원의 스칼라 값인 반면, R-Tree 인덱스는 2차원 공간 개념 값이다.

MySQL의 공간 확장 (Spatial Extension)

• MySQL의 공간 확장을 이용하면 간단하게 위치 기반의 서비스(기능)를 구현할 수 있다.
• 크게 다음 세 가지 기능이 포함되어 있다.
  • 공간 데이터를 저장할 수 있는 데이터 타입
  • 공간 데이터의 검색을 위한 공간 인덱스 (R-Tree 알고리즘)
  • 공간 데이터의 연산 함수 (거리 또는 포함 고나계의 처리)

구조 및 특성

• MySQL은 공간 정보의 저장 및 검색을 위해 여러 가지 기하학적 도형(Geometry) 정보를 관리할 수 있는 데이터 타입을 제공한다.
  • 대표적으로 POINT, LINE, POLYGON, GEOMETRY 데이터 타입이 있다.
  • GEOMETRY 타입은 나머지 3개 타입의 슈퍼 타입으로, 세 객체를 모두 저장할 수 있다.

최소 경계 상자 (MBR)

• Minimum Bounding Rectangle의 약자로, 해당 도형을 감싸는 최소 크기의 사각형을 의미한다.
• 이 사각형들의 포함 관계를 B-Tree형태로 구현한 인덱스가 R-Tree 인덱스다.

구조

• 공간 데이터의 도형들의 MBR을 3개 레벨로 나눠 그려본다.
  • 최하위 레벨: 각 도형을 제일 안쪽에서 둘러싼 점선 상자
  • 차상위 레벨: 중간 크기의 도형 객체의 그룹
  • 최상위 레벨
• 최상위 MBR은 R-Tree 루트 노드에 저장된다.
• 차상위 그룹 MBR은 R-Tree 브랜치 노드가 된다.
• 각 도형의 객체는 리프 노드에 저장된다.

R-Tree 인덱스의 용도

R-Tree란

• R-Tree는 MBR의 정보를 이용해 B-Tree 형태로 인덱스를 구축한다.
  • 공간(Spatial) 인덱스라고도 한다.
• 일반적으로 WGS84(GPS) 기준의 위도, 경도 좌표 저장에 주로 사용된다.
• CAD/CAM 소프트웨어 또는 회로 디자인 등과 같이 좌표 시스템에 기반을 둔 정보에 대해서는 모두 적용할 수 있다.

R-Tree 검색

• R-Tree는 각 도형(정확히는 도형의 MBR)의 포함 관계를 이용해 만들어진 인덱스이므로, 포함 관계를 비교하는 함수로 검색을 수행하는 경우에만 인덱스를 이용할 수 있다.
  • ST_Contains() 또는 ST_Within() 등
  • ex) 현재 사용자의 위치로부터 반경 5km 이내의 음식점 검색
• 현재 출시되는 버전의 MySQL에서는 거리를 비교하는 ST_Distance() 와 ST_Distance_Sphere() 함수는 공간 인덱스를 효율적으로 사용하지 못한다.
  • 따라서 공간 인덱스를 사용할 수 있는 ST_Contains() 또는 ST_Within() 를 이용해 거리 기반의 검색을 해야 한다.
• ST_Contains() 또는 ST_Within() 연산은 사각형 박스와 같은 다각형(Polygon)으로만 연산할 수 있다.
• 기준점 P로부터 반경 거리 5km 이내의 위치(점)을 검색하려면

  • ST_Contains() 또는 ST_Within() 함수를 이용하여 반경 5km를 그리는 원을 포함하는 최소 사각형(MBR)으로 포함 관계 비교를 수행

    SELECT * FROM tb_location WHERE ST_Contains(사각 상자, px);
    SELECT * FROM tb_location WHERE ST_Within(px, 사각 상자);

  • 이때, 사각형 안에 있지만 원 밖에 있는 점을 제거하고 싶다면 ST_Contains() 비교의 결과에 대해 ST_Distance_Sphere() 함수를 이용해 다시 한 번 필터링 해야 한다.

    SELECT * FROM tb_location
    	WHERE ST_Contains(사각 상자, px) -- // 공간 좌표 px가 사각 상자에 포함되는지 비교
    				AND ST_Distance_Sphere(p, px) <= 5*1000 -- // 5km

Reference

참고 서적

📔 Real MySQL 8.0