[MySQL] R-Tree Index 와 공간 탐색

MySQL 8.0 기준으로 작성한 글입니다.
이 글에서는 MySQL 의 R-Tree 에 대한 개념만 정리합니다.

1. R-Tree

R-Tree 는 점, 선, 면(다각형)과 같은 다차원 정보를 효율적으로 저장하기 위한 트리 형태의 자료구조 입니다.
보통 지도에서 좌표, 거리, 지역의 윤곽선 등을 저장하여 해당 개체를 더 빠르게 쿼리하는 목적으로 사용됩니다.
(예를 들면 "현재 위치로부터 1km 이내의 식당들 검색")

1.1 MBR : 최소 경계 사각형

R-Tree 의 핵심은 MBR(최소 경계 사각형) 입니다.
MBR 은 Minimun bounding rectangle 로 특정 도형을 감싸는 최소 크기의 사각형을 의미합니다.
하나의 도형뿐만 아니라 근처의 도형도 함께 감싸는 저장방식을 통해 도형의 포함 관계를 이용할 수 있습니다.

B-Tree 와 유사하게 특정 범위의 도형을 묶어서 저장할 경우, 탐색 시간을 획기적으로 줄일 수 있기 때문입니다.

1.2 R-Tree 자료구조

간단한 R-Tree 예시(출처 : Wikipedia)

R-Tree 자료구조는 B-Tree 와 흡사한 형태로 구성되어있습니다.
각 노드에 저장할 수 있는 도형의 개수는 사전에 지정되는데요.
최대 M개에서 최소 m(M/2)개 저장할 수 있습니다.

또한 B-Tree 처럼 리프 노드에 데이터(도형)를 저장하고, 리프 노드가 아닌 노드는 MBR 간의 포함관계를 표현합니다.

1) 탐색

탐색 연산의 시간 복잡도는 평균 $O(log_{M}n)$ 이고, 최악의 경우에는 $O(n)$ 입니다.
(M : 노드당 저장되는 도형 개수, n : 노드 수)

탐색은 Top down 방식으로 진행되며 로트 노드부터 리프 노드까지 내려갑니다.
이때 MBR 간에 중첩된 영역이 많을수록 탐색 성능은 떨어지는데요.
그 이유는 중첩된 영역이 이 많을수록 탐색할 노드가 많아지기 때문입니다.

탐색 과정은 다음과 같습니다.

1. 루트 노드부터 모든 하위 노드들을 순회하며 MBR 을 이용하여 검색 영역 내에 들어오는지 검사
2. 리프 노드를 찾으면 포함된 도형들이 검색 영역에 포함되는지 확인

도형 탐색(출처 : R-Tree와 BSP-Tree를 이용한 지도 Data의 탐색, 경북대학교 권구호)

2) 삽입

삽입 연산은 $O(n)$ 으로 성능이 뛰어나진 않은데요.
그 이유는 삽입 시 MBR 을 최소로 확장시키는 노드를 찾아 도형을 삽입하기 때문입니다.
삽입 과정은 다음과 같습니다.

1. 트리를 순회하며 어떤 리프 노드에 삽입하면 확장되는 MBR 영역이 최소가 되는지 확인
   (확장되는 면적이 동일한 경우에는 MBR 면적이 작은 것을 선택)
2. 선택한 리프 노드에 도형을 삽입
   (노드가 담을 수 있는 최대 개수를 넘는다면 분할 과정이 진행됨)
   1. 가장 멀리 떨어진 두 개의 도형 탐색(MBR 이 최대가 되는 두 도형, 이 도형을 둘을 노드로 삼음)
   2. 두 도형 중 MBR 확장이 최소가 되는쪽으로 삽입
   3. ii 를 반복하다, 오버플로우가 발생하면 다른 노드로 나머지 노드 삽입
   4. 모든 도형이 노드에 포함되면 분할 종료
3. 삽입 후에는 트리 구조를 재구성한다.

도형 15 삽입 전(출처 : R-Tree와 BSP-Tree를 이용한 지도 Data의 탐색, 경북대학교 권구호)

도형 15 삽입 후(출처 : R-Tree와 BSP-Tree를 이용한 지도 Data의 탐색, 경북대학교 권구호)

3) 삭제

삭제 연산의 시간복잡도에 대한 자료는 찾지 못했으나, 탐색 연산 + @ 가 될 것이라 생각합니다.

삭제 과정은 다음과 같습니다.

1. 리프 노드에서 삭제할 도형을 제거하고, 부모 노드의 사각형은 크기가 축소됨
   (삭제된 도형이 속한 MBR 의 크기 축소)
2. 만약 리프 노드의 도형 개수가 최소 개수(M/2) 이하가 된다면 트리를 재구성함
   1. 언더 플로우가 되는 노드를 제거하고, 그에 속하는 도형은 트리에 재삽입함

도형 7 삭제 전(출처 : R-Tree와 BSP-Tree를 이용한 지도 Data의 탐색, 경북대학교 권구호)

도형 7 삭제, 언드플로우 노드(R5) 발생(출처 : R-Tree와 BSP-Tree를 이용한 지도 Data의 탐색, 경북대학교 권구호)

언더플로우 노드 제거 후 재삽입(출처 : R-Tree와 BSP-Tree를 이용한 지도 Data의 탐색, 경북대학교 권구호)

도형 7 삭제 후(출처 : R-Tree와 BSP-Tree를 이용한 지도 Data의 탐색, 경북대학교 권구호)

2. MySQL Spatial Index

MySQL 에서는 Spatial Index 를 생성하면 앞서 살펴봤던 R-Tree 자료구조를 이용합니다.
MyISAM 과 InnoDB 스토리지 엔진 모두 Spatial Index 를 지원합니다.

2.1 생성 방법

1) CREATE TABLE

CREATE TABLE geom (g GEOMETRY NOT NULL SRID 4326, SPATIAL INDEX(g));

2) ALTER TABLE

CREATE TABLE geom (g GEOMETRY NOT NULL SRID 4326);
ALTER TABLE geom ADD SPATIAL INDEX(g);

3) CREATE INDEX

CREATE TABLE geom (g GEOMETRY NOT NULL SRID 4326);
CREATE SPATIAL INDEX g ON geom (g);

2.2 Spatial data type

MySQL 의 Spatial data type 은 크게 Single geometry 타입과 Collections 타입으로 나누어집니다.
이 구조는 OpenGIS Geometry Model을 따른다고 하는데요.
각 타입들에 대한 내용은 아래에서 알아보겠습니다.

1) Single geometry

2차원 좌표공간에 존재하는 0차원(점), 1차원(선), 2차원(면)의 도형을 표현하는 자료구조들 입니다.

• GEOMETRY : 0~2차원 도형을 모두 포함
• POINT : 0차원(점)을 나타냄
  • 속성 : X, Y 좌표값
  • 활용 : 버스 정류장의 위치 등
• LINESTRING : 1차원(선)을 나타냄
  • 속성 : 두 점(POINT)
  • 활용 : 두 지점간 거리 등
• POLYGON : 2차원(면)을 나타냄
  • 속성 : LINESTRING 집합
  • 활용 : 특정 영역 표시 등

2) Collections

• GEOMETRYCOLLECTION : 0~2차원 도형을 모두 포함
• MULTIPOINT : 0차원(점)을 나타냄
  • 속성 : 중복되지 않는 POINT 집합
  • 활용 : 여러 지점을 동시에 표시(놀이공원의 매표소들 위치 등)
• MULTILINESTRING : 1차원(선)을 나타냄
  • 속성 : LINESTRING 집합
  • 활용 : 하천, 고속도로 표시 등
• MULTIPOLYGON : 2차원(면)을 나타
  • 속성 : POLYGON 집합(POLYGON 을 구성하는 LINESTRING 은 단 하나의 POLYGON 에만 속함)
  • 활용 : 도시의 호수들의 영역 표시 등(system of lakes)

2.3 SRID

Spatial Index 의 생성 방법을 다시 살펴보겠습니다.

CREATE TABLE geom (g GEOMETRY NOT NULL SRID 4326, SPATIAL INDEX(g));

여기서 g 컬럼 선언부에 SRID 4326 이라는 구문이 있습니다.
이게 어떤것을 의미하는지 살펴보려고 하는데요.
그러나 SRID 를 얘기하려면 먼저 좌표계에 대해서 알아야 합니다.

1) 좌표계

기하학에서 2차원 평면 혹은 3차원 공간안에서의 특정 위치를 표현하는 방식을 의미합니다.
이 중에서 위치, 지도 서비스에서는 지구상에 특정 지점을 표현하기 위한 좌표계를 사용하게 되는데요.

• 구글맵 : WGS84(참고)
• 네이버 지도 : WGS84(참고)
• 카카오맵 : EPSG5181(참고)

이 처럼 서비스마다 각자 목적에 맞는 좌표계를 선택하여 사용하게 됩니다.

참고로 MySQL 의 information_schema 의 st_spatial_reference_systems 테이블에서 지원하는 좌표계를 확인할 수 있습니다.

mysql> desc information_schema.st_spatial_reference_systems;
+--------------------------+---------------+------+-----+---------+-------+
| Field                    | Type          | Null | Key | Default | Extra |
+--------------------------+---------------+------+-----+---------+-------+
| SRS_NAME                 | varchar(80)   | NO   |     | NULL    |       |
| SRS_ID                   | int unsigned  | NO   |     | NULL    |       |
| ORGANIZATION             | varchar(256)  | YES  |     | NULL    |       |
| ORGANIZATION_COORDSYS_ID | int unsigned  | YES  |     | NULL    |       |
| DEFINITION               | varchar(4096) | NO   |     | NULL    |       |
| DESCRIPTION              | varchar(2048) | YES  |     | NULL    |       |
+--------------------------+---------------+------+-----+---------+-------+

2) SRID

즉, SRID 는 Spatial Reference Identifier 의 약자로 각 좌표계의 고유식별자 입니다.
그래서 컬럼 선언 혹은 데이터 삽입시 원본 데이터의 SRID 와 같게 설정해주어야 합니다.

MySQL 에서는 SRID 를 설정하지 않으면 기본적으로 0 으로 설정됩니다.
만약 SRID 에 차이가 있으면 거리 계산 혹은 좌표 표현시 오차가 발생할 수 있습니다.

참고 자료

• Real MySQL 8.0 1권
• R-Tree와 BSP-Tree를 이용한 지도 Data의 탐색, 경북대학교 권구호님
• https://dev.mysql.com/doc/refman/8.0/en/creating-spatial-indexes.html
• https://dev.mysql.com/doc/refman/8.0/en/spatial-type-overview.html
• https://dev.mysql.com/doc/refman/8.0/en/opengis-geometry-model.html
• https://hoing.io/archives/5457