Ch08-4 R-Tree 인덱스

한 줄 정의

R-Tree는 2차원 이상의 공간 데이터 를 효율적으로 검색하기 위한 인덱스로, 각 도형을 감싸는 최소 경계 사각형(MBR) 을 계층적으로 저장합니다.

쉽게 말하면

R-Tree는 지도에서 지역을 찾는 방식 입니다.

“서울” 안에 “강남구” 안에 “역삼동” 안에 “특정 건물”이 있는 것처럼,
큰 사각형 안에 작은 사각형이 들어가고, 그 안에 또 작은 사각형이 들어가는 구조입니다
“이 좌표와 가까운 식당” 같은 질의가 들어오면, 해당 좌표를 포함하는 큰 사각형부터 좁혀 내려가며 찾습니다

B-Tree가 1차원의 값(숫자/문자)을 정렬한다면, R-Tree는 2차원 공간을 재귀적으로 분할 해서 관리합니다.

핵심 내용

MBR (Minimum Bounding Rectangle)

R-Tree의 핵심 개념입니다. 임의의 도형을 둘러싸는 가장 작은 직사각형 을 의미합니다.

flowchart TB
    subgraph MBR_Concept["MBR 개념"]
        direction LR
        R1["큰 MBR<br/>(여러 도형 포함)"]
        R2["중간 MBR<br/>(일부 도형 포함)"]
        R3["작은 MBR<br/>(개별 도형)"]

        R1 --> R2
        R2 --> R3
    end

복잡한 폴리곤도 MBR로 단순화해 비교
공간 검색 시 먼저 MBR끼리 비교 해서 후보를 빠르게 줄인 뒤, 실제 도형 연산은 후보에만 수행

언제 R-Tree를 쓰는가

MySQL에서 R-Tree는 SPATIAL INDEX 로 생성되며, 다음 타입에만 적용됩니다.

POINT : 점
LINESTRING : 선
POLYGON : 다각형
GEOMETRY : 위 타입의 상위 개념

공간 인덱스 생성

CREATE TABLE tb_location (
    id BIGINT NOT NULL AUTO_INCREMENT,
    loc GEOMETRY NOT NULL SRID 0,
    PRIMARY KEY (id),
    SPATIAL INDEX sx_loc (loc)
);

MySQL 8.0부터 SRID(Spatial Reference ID) 를 명시해야 인덱스 생성 가능
SRID 0 : 일반 직교 좌표계
SRID 4326 : WGS84 (지구 경위도)

공간 검색 함수

함수	의미
`ST_Contains(A, B)`	A가 B를 포함하는가
`ST_Within(A, B)`	A가 B 안에 있는가
`ST_Intersects(A, B)`	A와 B가 교차하는가
`ST_Distance(A, B)`	A와 B의 거리
`ST_Distance_Sphere(A, B)`	구면(지구) 거리

예시: 특정 반경 내 검색

-- 서울 시청 좌표 (126.9780, 37.5665) 에서 5km 이내
SELECT id, name,
       ST_Distance_Sphere(loc, ST_GeomFromText('POINT(126.9780 37.5665)', 4326)) AS dist_m
FROM tb_location
WHERE ST_Distance_Sphere(loc, ST_GeomFromText('POINT(126.9780 37.5665)', 4326)) <= 5000;

내 생각

R-Tree는 실무에서 지도/물류/IoT 센서 위치 처럼 공간 데이터가 핵심인 서비스가 아니라면 거의 쓸 일이 없습니다. 하지만 그런 도메인에서는 R-Tree 없이는 성능을 확보할 수 없습니다.
위치 기반 서비스에서는 MySQL의 R-Tree만으로 부족 한 경우가 많습니다. PostGIS, Elasticsearch의 geo_point, Redis의 GEO 명령 같은 전문 솔루션을 함께 고려해야 합니다. MySQL의 R-Tree는 “있다는 사실을 아는 것” 정도로 충분할 수 있습니다.

출처

Real MySQL 8.0 (1권), 8.4 R-Tree 인덱스

Dev Wiki

탐색기