R-Tree와 반경 검색(MySQL) 알아보기

Jang990·2024년 9월 13일

반경검색 기능 추가하기

목록 보기

4/4

R-Tree 알아보기

지금 당장 이해는 안되겠지만 일단 R-Tree가 무엇인지를 확인해보겠습니다.

R-Tree는 MBR 정보를 이용해 B-Tree 형태로 인덱스를 구축하므로 Rectangle의 'R'과 B-Tree의 Tree를 섞어서 R-Tree라는 이름이 붙여졌습니다. (공간 인덱스라고도 한다.)

일반적으로 WGS84(GPS) 기준의 위도, 경도 좌표 저장에 주로 사용됩니다.

이 내용을 이해하기 위해서 공간 데이터는 어떤 타입이 있고, 이것들을 효율적으로 조회를 위해서 어떤 방식이 적용되는지를 확인해보겠습니다.

데이터 타입

공간 데이터는 일반적인 숫자, 문자 데이터와 다르게 2차원으로 표현됩니다.
다음 그림과 같이 점, 선, 도형으로 표현되는 것입니다.

마지막에 GEOMETRY 타입은 나머지 3개 타입의 슈퍼 타입으로, POINT와 LINE, POLYGON을 모두 저장할 수 있습니다.

MBR(Minimum Bounding Rectangle)

위치 정보는 점, 선, 폴리곤으로 제각기 다르게 표현될 수 있습니다.
이 위치 정보를 단순화한 것이 바로 MBR입니다.

MBR이란 도형을 감싸는 최소 크기의 사각형을 의미합니다.

다음 그림과 같이 별 모양의 폴리곤과 대각선들이 MBR로 단순화하여 표현되는 것입니다.

R-Tree

그림에 있는 1~9의 위치 정보를 R트리에 저장했다고 할 때 R트리에는 MBR을 통해 다음과 같이 저장됩니다.

상위 MBR이 하위 MBR들을 포함하는 계층적인 구조를 갖고 있습니다.

지금 하나의 노드에 하나의 데이터만 담고있는 것처럼 보이지만, B-Tree와 마찬가지로 하나의 노드가 여러 데이터를 가질 수 있습니다.

(범위) 조회

숫자를 조회할 때 10 < 조회할 값 < 1000 범위가 될 10과 1000을 받는 것처럼, 범위 조회에서는 조회할 MBR을 받습니다.
조회는 B+ Tree에서의 조회와 매우 유사하고, 다음 규칙을 따릅니다.

(시작이라면 Root) 노드에서 조회 MBR과 겹치는지 여부를 확인
겹치는 경우 해당 MBR의 자식 노드 조회
다시 1로 돌아가서 자식 노드에서 재귀적으로 수행

조회는 모든 겹치는 노드를 탐색할 때까지 진행됩니다.

리프 노드에 도달하면 포함된 MBR과 조회 MBR과 비교하고, 해당 객체가 검색 MBR 내에 있는 경우 결과 집합에 추가됩니다.

Worst Case 생각하기

모든 중간 노드에 애매하게 겹쳐있는 초록색 MBR로 조회를 한다고 가정해봅시다.

이 경우 모든 리프노드를 탐색해야 합니다.
B-Tree는 최악의 경우에도 O(logN)을 보장했지만,
R-Tree는 최악의 경우 O(N)의 시간복잡도를 갖습니다.

실행 계획 확인

SPATIAL INDEX로 R트리 인덱스를 설정한 테이블과, 인덱스를 전혀 설정하지 않은 테이블을 만들었습니다.

-- location테이블과 인덱스가 없는 locations_without_index 테이블
CREATE TABLE locations_without_index ( -- location
	id INT NOT NULL AUTO_INCREMENT,
	location POINT NOT NULL SRID 4326,
-- 	SPATIAL INDEX(location)
	CONSTRAINT testTable_PK PRIMARY KEY(id)
);

각각의 테이블에 5만건의 위치정보를 저장했고, 다음 쿼리를 통해서 범위 검색을 실행할 것입니다.

EXPLAIN ANALYZE 
SELECT id, ST_AsText(location) FROM locations
WHERE ST_Contains(
    ST_GeomFromText('POLYGON((
        37.5165 126.9280,
        37.5165 127.0280, 
        37.6165 127.0280, 
        37.6165 126.9280 , 
        37.5165 126.9280
    ))', 4326),
    location
);

인덱스를 설정한 테이블과 인덱스를 설정하지 않은 테이블은 다음과 같은 차이가 났습니다.

-- 인덱스를 설정한 테이블
-> Limit: 200 row(s)  (cost=5.66 rows=12) (actual time=0.236..1.8 rows=49 loops=1)
    -> Filter: st_contains(<cache>(st_geomfromtext('POLYGON((\r\n        37.5165 126.9280,\r\n        37.5165 127.0280, \r\n        37.6165 127.0280, \r\n        37.6165 126.9280 , \r\n        37.5165 126.9280\r\n    ))',4326)),locations.location)  (cost=5.66 rows=12) (actual time=0.235..1.79 rows=49 loops=1)
        -> Index range scan on locations using location over (location unprintable_geometry_value)  (cost=5.66 rows=12) (actual time=0.129..0.254 rows=50 loops=1)
        

-- 인덱스를 설정하지 않은 테이블
-> Limit: 200 row(s)  (cost=5051 rows=200) (actual time=0.171..1485 rows=49 loops=1)
    -> Filter: st_contains(<cache>(st_geomfromtext('POLYGON((\r\n        37.5165 126.9280,\r\n        37.5165 127.0280, \r\n        37.6165 127.0280, \r\n        37.6165 126.9280 , \r\n        37.5165 126.9280\r\n    ))',4326)),locations_without_index.location)  (cost=5051 rows=50112) (actual time=0.17..1485 rows=49 loops=1)
        -> Table scan on locations_without_index  (cost=5051 rows=50112) (actual time=0.033..43.5 rows=50000 loops=1)

번외) 좌표계 종류와 WGS 84

흔히 사람들은 지리 좌표라고 하면 GPS로부터 수신받는 위도와 경도만 생각합니다.
하지만 나라별, 지역별 그리고 목적이나 용도별로 사용하는 좌표는 매우 다양합니다.
그래서 지구상의 동일 지점이라 하더라도 어느 공간 좌표계(SRS)를 사용하느냐에 따라 표시 방법이 달라집니다.

SRS(Spatial Reference System) - 흔히 이야기 하는 좌표계
GCS(Geographic Coordinate System) - 지구 구체상의 특정 위치나 공간을 표현하는 좌표계
PCS(Projected Coordinate System) - 지구를 종이 지도와 같이 평면으로 투영시킨 좌표계

다른 좌표계. 같은 위치. 다른 표현.

WGS 84 (SRID 4326)
일반적으로 사용되는 지구 표면의 경도 및 위도 좌표를 사용하여 공간 데이터를 나타냄
126.994744 37.538350

Web Mercator (SRID 3857)
구글 지도 등 전 세계의 지도들이 사용하는 좌표계
14136990.232691 4514413.916586

일반적으로 휴대폰과 같은 모바일 장치로부터 수신받는 GPS 좌표는 WGS 84이며, SRID 4326인 지리 좌표계로 표현됩니다.