B-Tree 한계를 극복한 2D Spatial Indexing 최적화 전략

Context

위도와 경도를 독립적으로 처리하는 B-Tree 기반 Index 구조로 인한 2D 공간 쿼리 효율 저하 문제 발생. 단순 Range Scan 시 전 지구적 띠 형태의 불필요한 데이터 세트가 반환되어 필터링 부하가 증가하는 구조적 한계 노출.

Technical Solution

• Geohash: 2D 좌표를 1차원 문자열로 변환하여 물리적 인접성을 문자열 접두사 공유로 구현한 설계
• Quadtree: 데이터 밀도에 따라 영역을 4분할하여 세분화하는 가변 해상도 기반의 계층 구조 채택
• R-tree: 데이터 클러스터 기반의 MBR(Minimum Bounding Rectangle) 중첩 구조를 통한 공간 탐색 범위 최소화
• 데이터 근접성 유지: 물리적으로 가까운 지점을 인덱스 상에서도 인접하게 배치하여 I/O 효율을 극대화한 접근 방식
• Index Intersection 오버헤드 제거: 두 개의 독립 인덱스를 병합하는 대신 단일 공간 인덱스를 통한 직접 접근 구조 설계