Geohash·Quadtree·H3 비교: 위치 검색에 맞는 공간 인덱스 고르기

위도와 경도를 그대로 저장하는 것만으로는 “내 주변 2km”, “이 지도 화면 안”, “이 구역별 주문 수” 같은 질의를 효율적으로 풀기 어렵다. 위치를 검색 가능한 cell이나 tree node로 바꾸는 공간 인덱싱이 필요한 이유다.

Geohash, Quadtree, H3는 모두 공간을 나누지만 같은 종류의 도구는 아니다.

• Geohash는 좌표를 계층적인 문자열 cell로 encoding한다.
• Quadtree는 2차원 영역을 재귀적으로 네 구역으로 나누는 data structure 계열이다.
• H3는 지구 표면을 주로 육각형 cell로 나누는 discrete global grid system이다.

이름만 비교해 하나를 고르기보다 실제 query가 prefix 검색인지, viewport 탐색인지, 인접 지역 집계인지부터 봐야 한다.

Geohash: 문자열 prefix로 공간을 묶는다

Geohash는 경도와 위도 범위를 번갈아 이분하고 그 결과 bit를 Base32 문자열로 표현한다. 문자열이 길수록 더 작은 cell을 가리킨다.

짧은 prefix            더 긴 code
wydm        →          wydm6dt
넓은 영역              더 좁은 영역

PostGIS의 ST_GeoHash 문서도 짧은 Geohash를 point를 포함하는 덜 정밀한 box로 설명한다. 문자열이 정렬 가능하고 prefix로 검색할 수 있다는 점은 cache key, partition 후보, 단순 bucket 집계에 편리하다.

다만 “가까운 두 점은 항상 비슷한 prefix를 가진다”는 설명은 정확하지 않다. cell 경계 양쪽에 있는 두 점은 실제 거리가 매우 가까워도 처음부터 다른 code를 가질 수 있다. 반대로 같은 prefix는 같은 box 안에 있다는 뜻이지 두 점 사이의 실제 거리가 가깝다는 보장은 아니다.

nearby search에서는 보통 현재 cell만 조회하지 않는다.

1. 검색 반경과 precision에 맞는 cell 크기를 정한다.
2. 중심 cell과 경계에 닿는 이웃 cell을 함께 조회한다.
3. 후보를 얻은 뒤 실제 구면 거리로 다시 걸러낸다.

Geohash prefix는 후보를 줄이는 1차 filter이지 정확한 거리 계산의 대체재가 아니다. 위도에 따라 실제 cell 폭도 달라지므로 precision을 “몇 km”라는 고정값처럼 취급하면 안 된다.

Quadtree: 데이터가 필요한 곳을 더 잘게 나눈다

Quadtree는 하나의 2차원 영역을 네 자식 영역으로 재귀 분할한다.

┌───────────────┐
│       │       │
│   0   │   1   │
│───────┼───────│
│   2   │   3   │
│       │       │
└───────────────┘

point quadtree, region quadtree, PR quadtree처럼 세부 형태는 여럿이다. 위치 서비스에서 자주 쓰는 방식은 한 node의 point 수가 기준을 넘을 때만 더 나누는 식이다. 데이터가 몰린 도심은 깊게, 드문 지역은 얕게 유지할 수 있어 공간 분해를 밀도에 맞출 수 있다.

이 구조는 다음 query와 잘 맞는다.

• 지도 viewport와 겹치는 node만 방문하기
• 직사각형 range 안의 point 찾기
• zoom level에 따라 다른 깊이의 node 사용하기
• 충돌 검사나 2차원 object 후보 줄이기

대신 운영 설계가 필요하다. 분할 기준과 최대 깊이, skewed data에서의 tree 높이, update와 rebalance, node를 여러 shard에 배치할 때의 경계를 정해야 한다. “Quadtree를 쓴다”는 말만으로 query complexity가 자동으로 좋아지는 것은 아니다.

H3: 이웃과 영역 집계에 유리한 global cell

H3는 지구를 icosahedron에 투영한 뒤 계층적인 cell index를 부여한다. cell은 대부분 육각형이지만 구를 완전히 육각형만으로 덮을 수 없어 각 resolution에 12개의 pentagon이 존재한다.

H3 resolution은 0부터 15까지다. 숫자가 커질수록 cell이 작아진다. 모든 cell 면적이 정확히 같지는 않고, H3 공식 통계도 icosahedron vertex와의 위치에 따라 면적이 달라진다고 설명한다.

육각형 grid는 일반적으로 인접 방향과 중심 간 거리가 비교적 균일해서 다음 작업을 표현하기 좋다.

• 중심 cell에서 k칸 이내 이웃 찾기
• 지역별 수요·이벤트 수 집계
• 서로 다른 dataset을 같은 cell index로 join
• 이동 흐름과 인접 영역 분석

다만 hierarchy를 실제 polygon 포함 관계와 동일시하면 안 된다. H3는 parent-child의 논리적 containment를 제공하지만 cell 경계의 기하학적 containment는 근사적이다. finer cell polygon이 coarse parent polygon 안에 완전히 들어간다고 가정해 정확한 geometry 연산을 대신하면 오차가 생길 수 있다.

현재 h3-py API로 확인하기

h3-py v4에서는 v3의 geo_to_h3 같은 함수명이 크게 바뀌었다. 현재 API는 다음처럼 사용한다.

import h3

latitude = 37.5665
longitude = 126.9780
resolution = 9

cell = h3.latlng_to_cell(latitude, longitude, resolution)
boundary = h3.cell_to_boundary(cell)
neighbors = h3.grid_disk(cell, 1)

print(cell)
print(boundary)
print(neighbors)

latlng_to_cell은 (lat, lng) 순서를 받는다. GeoJSON의 coordinate 순서인 (lng, lat)와 반대이므로 변환 지점에서 뒤집힘을 명시해야 한다.

또한 grid_disk(cell, 1)은 중심을 포함해 grid distance가 1 이하인 cell 집합을 반환한다. 결과를 실제 반경 1km라고 해석하면 안 된다. 선택한 resolution과 위치에 따라 cell 크기가 다르므로 거리 조건은 별도로 검증한다.

세 방식을 query 기준으로 비교하기

기준	Geohash	Quadtree	H3
기본 표현	Base32 문자열 cell	재귀적 4분할 tree	64-bit 계층 cell index
분할 형태	위·경도 구간의 box	보통 사각 영역	대부분 육각형, 일부 pentagon
밀도 적응	precision을 달리할 수 있으나 자체 tree 운영은 별개	분할 기준으로 적극 적응 가능	동일 resolution grid는 전역적으로 정해짐
잘 맞는 query	prefix·bucket·범위 후보	viewport·rectangle·밀도 적응	이웃·ring·지역 집계·cell join
주의점	경계와 실제 거리, 위도별 왜곡	skew·깊이·update·sharding	면적 차이, pentagon, 기하학적 hierarchy 근사

선택 순서

문자열 prefix가 이미 storage model의 중심인가

단순한 key-value lookup이나 prefix partition이 핵심이고, 정확한 거리 filter를 뒤에 둘 수 있다면 Geohash가 작고 이해하기 쉽다.

화면 영역과 데이터 밀도에 맞춰 나누고 싶은가

지도 viewport나 object range query가 중심이고 밀집 지역만 세밀하게 분할하고 싶다면 Quadtree가 자연스럽다. 대신 tree lifecycle을 운영할 책임도 생긴다.

인접 지역과 동일 cell 단위 집계가 핵심인가

배달 수요, 이동량, heatmap처럼 여러 dataset을 공통 cell로 묶고 이웃을 자주 탐색한다면 H3가 강하다. 사용할 resolution은 평균 cell 면적만 보고 정하지 말고 query 정확도, row 수, cardinality와 비용을 함께 측정한다.

실제 database에서는 한 가지만 쓰지 않을 수도 있다. 예를 들어 B-tree나 문자열 index로 후보를 줄이고 정확한 geometry 함수로 후처리하거나, H3 cell로 집계한 뒤 원본 좌표로 최종 거리를 계산할 수 있다. DB가 Full Scan과 B+Tree로 데이터를 찾는 과정과 단일 인덱스의 동작을 함께 보면 공간 key가 storage index 위에서 어떻게 검색되는지도 연결된다.

참고 자료

• PostGIS: ST_GeoHash
• H3 4.x introduction
• H3 indexing functions
• H3 cell statistics by resolution
• h3-py API quick reference
• Hanan Samet, The Quadtree and Related Hierarchical Data Structures