SQLite R*Tree 모듈

이 문서는 SQLite의 RTree(R-star tree) 모듈을 설명해요. RTree는 공간(spatial) 검색을 빠르게 하기 위한 특수한 가상 테이블(virtual table)이에요.

출처: 문서

본문

RTree 모듈은 SQLite의 표준 확장으로, 직사각형(bounding box)을 다루는 공간 데이터에서 "이 상자 안에 들어 있는 것은 무엇인가?" 같은 질문을 빠르게 처리해요. RTree는 1~5개 차원을 지원하며, 기본적으로 실수(REAL) 좌표를 사용해요.

R*Tree 만들기

CREATE VIRTUAL TABLE ... USING rtree(...)로 만들 수 있어요.

CREATE VIRTUAL TABLE demo_index USING rtree(
   id,              -- 정수형 기본 키
   minX, maxX,      -- X축 최소/최대
   minY, maxY       -- Y축 최소/최대
);

첫 번째 열은 1~8바이트 정수형 id(기본 키)여야 해요. 그 뒤의 열들은 2의 배수 개수여야 하며, 각 차원에 대해 (최소, 최대) 쌍으로 이뤄져요. 위 예에서는 2차원(X, Y) 상자를 표현했어요.

데이터 삽입

INSERT INTO demo_index VALUES(
   1,   -- id
   -80.7749, -80.7747,   -- X 범위
   35.3776, 35.3777      -- Y 범위
);

공간 검색 쿼리

R*Tree는 WHERE 절에서 부등호와 범위 연산자로 고속 검색을 해요.

-- 특정 상자와 겹치는(overlap) 모든 항목 찾기
SELECT id FROM demo_index
  WHERE minX >= -81.0 AND maxX <= -80.0
    AND minY >= 35.0  AND maxY <= 36.0;

-- 특정 점을 포함하는 항목 찾기
SELECT id FROM demo_index
  WHERE minX <= -80.77 AND maxX >= -80.77
    AND minY <= 35.38  AND maxY >= 35.38;

각 차원의 (최소, 최대) 열에 대해 검색 조건을 함께 쓰면, R*Tree가 인덱스를 이용해 후보를 크게 줄인 뒤 결과를 확인해요.

LIMIT 문법

R*Tree 쿼리에서 결과 수를 제한할 때는 LIMIT 뒤에 확인할 최대 후보 수를 지정해요.

SELECT * FROM demo_index WHERE minX < -80 LIMIT 10;

정수 좌표: rtree_i32

좌표가 정수인 경우 기본 rtree 대신 rtree_i32를 사용할 수 있어요. 이 경우 좌표가 32비트 정수로 저장돼 메모리·디스크를 절약하고 계산이 빨라질 수 있어요.

CREATE VIRTUAL TABLE int_idx USING rtree_i32(id, x1, x2, y1, y2);

보조 함수

SQLite 3.24.0부터는 R*Tree를 검증·점검하는 보조 함수가 추가되었어요.

rtreecheck() — R*Tree의 구조적 무결성을 검사해요.
rtreenode() — R*Tree의 내부 노드를 살펴봐요.
rtreematches() — 쿼리와 매치되는 노드 수를 반환해요.

SELECT rtreecheck('demo_index');
-- 문제가 없으면 'ok' 반환

제약 사항

R*Tree 테이블은 다른 테이블과 조인할 수 있어요.
R*Tree는 보조 인덱스를 만들 수 없지만, id로 다른 테이블과 조인하는 패턴이 일반적이에요.
기본 rtree 모듈은 원본 구현이고, rtree_i32는 정수 최적화 버전이에요.

SQLite R*Tree 모듈