지오해시(GeoHash)란?

지오해시(GeoHash)

지오해시 예시

지오해시는 위도(Latitude)와 경도(Longitude)라는 2차원의 좌표 데이터를 1차원의 문자열(또는 숫자)로 변환하는 기술입니다.

전 세계 지도를 격자(Grid)로 나눕니다. 그리고 그 격자에 고유한 이름을 붙이는 방식입니다.

 

특징

• 문자열의 길이가 길수록 더 좁은 범위를 나타냅니다(더 정밀함).
• 앞부분이 같은 문자열로 시작하면, 지리적으로 서로 가까운 위치에 있을 확률이 높습니다.
• DB 인덱스 스캔에 최적화된 이유입니다.

🤔 그렇다면 지오해시는 어떻게 만들어질까요?

지오해시는 Z-Order Curve(Morton Order) 알고리즘을 기반으로 합니다. 과정을 설명하면 다음과 같습니다.

 

1. 범위 나누기 

• 경도(-180° ~ 180°)를 절반으로 나눕니다. 위치가 왼쪽(-180° ~ 0°)이면 0, 오른쪽(0° ~ 180°)이면 1을 부여
• 위도(-90° ~ 90°)도 똑같이 절반으로 나눠 위쪽이면 1, 아래쪽이면 0을 부여
• (절반으로 나눠서 어느 쪽에 있나를 묻는 이진 탐색과 똑같다)

2. 비트 교차

• 나누기 과정을 반복해서 얻은 경도 비트와 위도 비트를 하나씩 번갈아 가며 섞습니다. (예: 경위경위경위...)
• 경도 비트: a1 a2 a3
• 위도 비트: b1 b2 b3
• 지오해시 비트: a1 b1 a2 b2 a3 b3

3. Base32 인코딩

• 이렇게 만들어진 비트 나열을 5비트씩 끊어서 사람이 읽기 쉬운 문자(0-9, a-z 중 일부 제외)로 변환합니다.
• 5비트 단위로 끊어서 문자로 변환하기 때문에, 지오해시 문자열의 앞 글자가 같다는 것은 최소한 앞쪽 비트들이 대거 일치한다는 뜻

🤔 비트를 경도 하나, 위도 하나 번갈아 섞는 이유

약 경도 비트 10개를 다 쓰고, 그 뒤에 위도 비트 10개를 붙인다고 가정해 봅시다. 이렇게 하면 앞부분 비트(경도)가 같으면 세로로 긴 띠(Strip) 모양의 영역이 잡힙니다. "내 주변"을 찾고 싶은데, 인덱스는 "나랑 같은 경도에 있는 저 멀리 북한이나 남극 데이터"까지 일단 다 훑게 됩니다. 이에 불필요한 행 스캔이 일어납니다. 반대로 비트를 하나씩 번갈아 섞는다면(경-위-경-위...), 비트가 하나 추가될 때마다 검색 범위가 가로 한 번, 세로 한 번 번갈아가며 좁혀집니다. 결과적으로 인덱스에서 wydm으로 시작하는 데이터를 찾으면, 특정 세로 띠가 아니라 정사각형에 가까운 격자(Grid) 공간만 쏙 골라낼 수 있게 됩니다.

---

위치 데이터 검색

[위도 37.566, 경도 126.978]이나 [37.567, 126.979]는 아주 가까우니까 소수점 둘째 자리에서 반올림하면 모두 (37.57, 126.98)이라는 동일한 그룹으로 묶이지 않을까?"라는 생각에서 출발해 위치 데이터를 검색하기 위해 가장 먼저 떠오르는 방법은 위경도 좌표를 특정 소수점 자리에서 반올림하여 격자 형태로 그룹화하는 것입니다. 실제로 구현 경험 상 별도의 복잡한 알고리즘 없이 기존 DB의 컬럼 두 개(latitude, longitude)에 반올림 로직만 적용하면 되므로 매우 쉽고 직관적이였습니다.

 

B+TREE 구조

하지만 이 방식은 데이터 양이 늘어날수록 B+Tree 인덱스의 물리적 구조라는 벽에 부딪히게 됩니다. 단순히 "느리다"가 아니라 불필요하게 많이 읽는다"는 것이 문제였습니다.

 

1. 인덱스의 사전식 정렬 한계

저희가 (위도, 경도) 복합 인덱스를 생성한다고 가정할 때 B+Tree는 이를 마치 국어사전처럼 정렬합니다. a 로 시작하는 단어를 다 찾은 뒤에야 b 로 넘어가듯, 인덱스는 아래와 같이 위도 값이 같은 데이터들을 먼저 쭉 정렬한 뒤 그 안에서 경도를 정렬합니다.

 

즉, 복합 인덱스는 위도를 기준으로 먼저 정렬된 후 경도가 정렬되는 사전식 구조를 가집니다. 이 때문에 주변 영역을 검색할 때 인덱스는 특정 위도 범위에 속한 모든 경도 데이터를 스캔하는 Wide Range Scan을 수행하게 됩니다. 비록 반올림으로 데이터 양을 줄였을지라도, 위도 띠(Strip) 전체를 훑어야 하는 구조적 비효율 때문에 스캔 행 수 높게 나타납니다.

순서	위도 (1순위 정렬)	경도 (2순위 정렬)	데이터 위치 (가정)
1	37.51	126.01	인천 부근
2	37.51	126.98	서울 강남 부근
3	37.51	127.15	하남 부근
4	37.52	126.10	인천 부근
5	37.52	126.97	목표 지점 A
6	37.52	126.98	목표 지점 B
7	37.52	127.10	하남 부근
8	37.53	126.98	서울 강북 부근

• 1순위- 위도 순서대로 정렬
• 2순위- 위도가 똑같을 때만 경도 순서대로 정렬

2. 가로 띠(Strip) 스캔 현상

자, 이제 사용자가 서울 강남 근처(위도 37.52, 경도 126.97~126.98) 에 있는 상점을 찾는다고 해봅시다. 사용자가 찾고 싶은 데이터는 특정 지점 주변의 작은 사각형 영역입니다. 하지만 복합 인덱스에 범위 검색을 던지면 인덱스는 우리가 원하는 작은 사각형뿐만 아니라, 해당 위도 범위에 속한 수평 방향의 전체 데이터를 훑게 됩니다. 이유는 다음과 같습니다.

 

먼저 DB는 인덱스에서 위도 37.52 구역에 진입하면, 인덱스는 해당 위도에 속한 모든 경도 데이터를 순서대로 읽게 됩니다. 이때 사용자가 찾고자 하는 경도 범위인 126.97~126.98에 해당하는 5번, 6번 행은 유효한 결과로 확보되지만, 뒤이어 나타나는 7번 행(경도 127.10)처럼 조건에 맞지 않는 데이터도 인덱스 구조상 위도가 같기 때문에 일단 물리적으로 읽어 들일 수밖에 없습니다.

• 순차 탐색 (Sequential Scan): 인덱스가 옆으로 이동하며 데이터를 하나하나 읽는 행위
• 인덱스 필터링 (Index Filtering): 인덱스를 읽긴 했지만 WHERE 조건에 맞지 않아 버려지는 과정
• 데이터 응집도 (Data Locality): 내가 찾는 데이터들이 물리적으로 모여 있는 정도

위의 예시에서는 데이터가 몇 개 없지만, 실제 전국 단위 데이터라면 위도가 37.52인 지점은 서해안 끝(인천 서쪽)부터 동해안 끝(강릉)까지 가로로 길게 이어집니다. 복합 인덱스는 위도가 같으면 경도순으로 줄을 세우기 때문에, 내가 찾는 강남역 주변 데이터를 찾으려면 같은 위도(37.52)에 걸쳐 있는 인천, 부천, 광명 등의 데이터를 인덱스 리프 노드에서 일단 다 읽어야 합니다. 읽고 나서 "아, 이건 경도가 강남이 아니네?" 하고 버리는 것 입니다.

 

3. 지오해시 방식

지오해시는 2차원 공간을 이미 1차원 문자열(wydm%)로 응축해 놓았기 때문에, 인덱스는 내가 원하는 격자가 모여 있는 아주 짧은 구간만 딱 읽고 스캔을 종료합니다. B+Tree 인덱스의 성능은 "찾는 데이터들이 얼마나 옆으로 나란히 붙어 있는가"에 결정됩니다. 지오해시는 가까운 지점들이 비슷한 문자열을 가지므로, B+Tree의 리프 노드 상에서 물리적으로 거의 붙어 저장됩니다. DB 입장에서는 페이지 한두 개만 읽으면 주변 상권 데이터가 다 튀어나오니 디스크 I/O가 극적으로 줄어듭니다.

 

또한, DB 엔진 입장에서도 복합 컬럼보다 단일 컬럼을 다루는 것이 훨씬 가볍습니다. 복합 인덱스는 두 컬럼의 상관관계를 계산해야 하지만, 지오해시는 LIKE 'wydm%' 또는 BETWEEN 'wydm0' AND 'wydmz' 같은 단순한 Prefix Scan(접두어 스캔)으로 처리됩니다.

 

🤔 지오해시는 왜 가까운 곳끼리 앞글자가 같을까?

지오해시는 지도를 재귀적으로 이등분하여 위치를 특정하는 이진 분할 방식을 사용하기 때문입니다. 특히 위도와 경도 비트를 하나씩 교차하여 섞는 알고리즘을 통해 2차원 평면상의 인접한 지점들을 1차원 선형 구조에서도 최대한 가깝게 배치합니다. 이 덕분에 같은 격자 내에 있는 데이터들은 동일한 비트 접두어(Prefix)를 가지게 되고, 이것이 Base32 문자로 변환되었을 때 비슷한 문자열로 나타나게 되는 것입니다. 즉, 지오해시의 특징은 같은 부모 격자에서 태어난 자식 격자들은 같은 비트 접두어를 공유한다는 점입니다. 마치 우리가 주소를 쓸 때 서울특별시 강남구...라고 쓰면, 강남구 안에 있는 모든 집은 앞부분이 똑같은 것과 같은 원리입니다.

 

지오해시가 유리한 본질적인 이유는 다차원 공간의 인접성을 1차원 B+Tree 인덱스의 정렬 순서와 일치시켰기 때문입니다. 반올림 방식은 인덱스를 타더라도 불필요한 데이터를 대량으로 읽어 들이는 '인덱스 필터링' 부하가 컸지만, 지오해시는 Index Skip Scan 이나 Wide Range Scan 없이 최소한의 리프 노드만 접근하여 결과를 가져올 수 있습니다.

---

R-tree

R-Tree는 이름 그대로 Rectangle(사각형)을 기반으로 한 트리 구조입니다. 단순한 데이터 정렬을 넘어 공간상의 포함 관계를 효율적으로 찾아내기 위해 설계된 자료구조입니다. 지오해시와 R-Tree는 공간 데이터를 다룬다는 목적은 같지만, DB 엔진 레벨에서 데이터를 바라보는 철학이 완전히 다릅니다.

R-Tree 예시(출처 : Wikipedia)

R-Tree는 모든 공간 데이터를 그것을 감싸는 최소 경계 사각형(MBR, Minimum Bounding Rectangle)으로 관리합니다. R-Tree의 핵심인 MBR은 복잡한 형태의 공간 데이터를 효율적으로 관리하기 위해 도입된 개념입니다. 우선 모든 공간 데이터는 그 모양이 점이든, 구불구불한 선이든, 복잡한 다각형이든 상관없이 해당 도형을 완전히 포함하는 가장 작은 사각형인 MBR로 변환되어 인덱스에 저장됩니다. 이렇게 생성된 개별 MBR들은 공간적 인접성에 따라 계층적으로 그룹화됩니다. 가까운 거리에 있는 여러 개의 MBR을 묶어 이를 모두 포함하는 더 큰 상위 MBR로 감싸고, 이러한 과정을 최상단의 루트 노드에 도달할 때까지 반복하여 트리 구조를 형성합니다. 결과적으로 하위 노드의 작은 사각형들이 모여 상위 노드의 커다란 사각형 영역을 구성하는 체계적인 계층 구조가 만들어집니다.

 

실제 탐색 과정에서는 이 계층 구조를 활용해 검색 범위를 획기적으로 줄입니다. 사용자가 특정 영역을 검색하면 루트 노드부터 시작하여 "현재 검색 사각형이 이 부모 MBR과 겹치는가?"를 먼저 확인합니다. 만약 부모 영역과 전혀 겹치지 않는다면 그 내부에 포함된 수많은 하위 MBR들은 확인할 필요조차 없으므로 탐색 대상에서 즉시 제외하며, 오직 겹치는 영역을 가진 가지(Branch)만을 따라 내려가며 최종 데이터를 찾아냅니다. 이러한 탐색 방식은 대량의 공간 데이터 중에서 검색 범위와 관련 없는 구역을 통째로 무시할 수 있게 해주어 성능을 극대화합니다.

 

🤔 JPA에서 공간 함수를 쓸 수 있을까?

가능하지만 일반적인 JPA(Hibernate)만으로는 부족하고, Hibernate Spatial이라는 라이브러리를 추가로 사용해야 합니다.

1. 의존성 추가

implementation 'org.hibernate:hibernate-spatial'

• build.gradle에 hibernate-spatial 라이브러리를 추가

2. DB 방언(Dialect) 변경

spring:
  jpa:
    database-platform: org.hibernate.spatial.dialect.mysql.MySQL8SpatialDialect

• application.yml에서 일반 MySQL 방언을 MySQL8SpatialDialect로 교체해야 합니다.

3. 엔티티(Entity) 수정

import org.locationtech.jts.geom.Point;

@Entity
public class Store {
    @Id @GeneratedValue
    private Long id;

    // columnDefinition에 명시적으로 geometry(또는 point)를 적어줍니다.
    @Column(columnDefinition = "GEOMETRY")
    private Point coordinates; 
}

• 일반적인 위경도 값을 Double이 아닌 Geometry 또는 Point라는 특수 객체 타입으로 선언해야 합니다.

4. DB 스키마 변경

-- 1. 기존 테이블에 POINT 타입 컬럼 추가 (위도, 경도를 담는 객체)
-- SRID 4326은 전 세계 표준 위경도 좌표계(WGS84)를 의미합니다.
ALTER TABLE locations ADD COLUMN coords POINT NOT NULL SRID 4326;

-- 2. (선택사항) 기존에 위도, 경도 값이 있었다면 POINT 컬럼에 채워넣기
-- ST_GeomFromText는 텍스트를 좌표 객체로 변환하는 함수입니다.
UPDATE locations 
SET coords = ST_GeomFromText(CONCAT('POINT(', longitude, ' ', latitude, ')'), 4326);

-- 3. SPATIAL INDEX(R-Tree) 생성
-- 일반 INDEX가 아닌 SPATIAL 키워드를 반드시 붙여야 R-Tree로 생성됩니다.
CREATE SPATIAL INDEX idx_location_coords ON locations(coords);

• 기존 테이블에 위치 정보를 저장할 POINT 타입의 컬럼을 추가하고, 여기에 공간 인덱스를 생성하는 과정입니다.
• DB에 접속해서 해당 컬럼의 타입을 변경하고, SPATIAL INDEX를 직접 생성해줘야 합니다.

5. R-Tree를 사용할 때 JPA 환경에서 쓰이는 Repository 쿼리

@Query(value = "SELECT * FROM locations l " +
       "WHERE ST_Distance_Sphere(" +
       "  l.coords, " + // 1. DB의 포인트 컬럼 (인덱스 대상)
       "  ST_GeomFromText(:wkt, 4326)" + // 2. 기준점 예: POINT(127.0 37.5))
       ") <= :radius", // 3. 검색 반경 (미터 단위)
       nativeQuery = true)
List<Location> findNearby(@Param("wkt") String wkt, @Param("radius") double radius);

• Native Query 사용
• DB의 공간 함수(MySQL 기준 ST_Contains, ST_Distance_Sphere 등)를 직접 호출하는 방식
• ST_Distance_Sphere: 두 지점 사이의 실제 지구 곡면 거리를 미터(m) 단위로 계산

@Query("SELECT l FROM Location l WHERE within(l.coords, :filterArea) = true")
List<Location> findWithin(@Param("filterArea") Geometry filterArea);

• 라이브러리를 설치하고 방언(Dialect) 설정을 마쳤다면, SQL이 아닌 JPQL 객체 지향 쿼리로도 공간 연산이 가능
• within: 첫 번째 인자가 두 번째 영역(MBR) 안에 포함되는지 확인하는 공간 함수

🤔 Geohash vs R-tree

1. 지오해시가 더 적합한 상황 - 가벼움과 범용성이 최우선일 때 선택

1. 인프라 제약이 있는 경우: 기존 RDB의 설정을 바꾸기 어렵거나, 공간 인덱스(R-Tree)를 지원하지 않는 DB를 사용 중일 때.
2. 캐싱이 중요한 경우: Redis 같은 Key-Value 저장소에 위치 데이터를 저장하고 빠르게 조회해야 할 때. (문자열이라 키값으로 쓰기 최적)
3. 단순 주변 검색이 목적인 경우: "내 주변 1km 맛집"처럼 정해진 격자 단위의 단순 조회가 주된 기능일 때.
4. 모바일/프론트엔드 연동: 서버뿐만 아니라 클라이언트에서도 위치를 격자로 관리하여 통신량을 줄이고 싶을 때.

2. R-Tree가 적합한 상황 - 정밀도와 복잡한 공간 연산이 필요할 때 선택

1. 다양한 도형(Polygon, Line)을 다룰 때: 점(Point)뿐만 아니라 "이 행정구역(면) 안에 포함된 도로(선) 찾기" 같은 복잡한 연산이 필요할 때
2. 정확한 반경 검색이 필수인 경우: 격자 단위가 아니라 "정확히 750m 이내"처럼 유동적이고 정밀한 거리 계산이 중요할 때
3. 데이터 변경이 적고 조회가 많은 경우: R-Tree는 인덱스 재구축 비용이 비싸지만, 한 번 구축해두면 복잡한 공간 검색 속도는 압도적
4. 지도 기반 전문 서비스: 우버(Uber), 배달의민족처럼 위치 자체가 서비스의 핵심이며, 고도화된 공간 함수를 활용해야 할 때.

항목	지오해시 (Geohash)	R-Tree (Spatial Index)
추천 상황	빠른 개발, 가벼운 서비스	전문적인 공간 정보 서비스
주요 장점	이식성 높음, 캐싱이 쉬움	복잡한 도형 연산 가능, 매우 정밀함
주요 단점	경계 지역 처리 로직 필요	DB 종속적, 인프라 설정 복잡
데이터 구조	단순 문자열 (B-Tree 활용)	전용 공간 객체 (R-Tree 전용)

 

📚 다른 대체 기술

1. S2 Geometry (Google) - 구글 맵스, 포켓몬 고 등에서 사용하는 기술

https://radar.com/blog/open-source-node-js-typescript-s2-library

• 지오해시가 평면 지도를 사각형으로 나눈다면, 지구 전체를 정육면체로 감싼 뒤 이를 구체로 투영
• 힐베르트 곡선(Hilbert Curve)을 사용. 지오해시의 Z-Order Curve보다 공간 인접성을 훨씬 더 잘 보존
• 지오해시처럼 문자열이 아닌 숫자(Long)로 위치를 표현해 계산 속도가 매우 빠름
• 북극이나 남극으로 갈수록 격자가 일그러지는 지오해시와 달리, 구체 모델링을 통해 오차가 적음
• 격자 크기를 31단계로 아주 세밀하게 조절 가능

2. H3 (Uber) - 우버(Uber)에서 만든 오픈소스 라이브러리로, 가장 큰 특징은 사각형이 아닌 육각형 격자를 사용

https://www.uber.com/en-KR/blog/h3/

• 특정 지점에서 반경 1km 이내를 찾을 때, 사각형보다 육각형이 실제 원형에 훨씬 가깝게 범위를 커버
• 차량 배차 최적화, 배달 수요 분석 등 데이터 밀도를 계산해야 하는 서비스에 압도적으로 유리

🤔 왜 육각형인가?

• 사각형은 중심에서 변까지와 꼭짓점까지의 거리가 다름(대각선이 더 멂)
• 반면 육각형은 인접한 6개 격자의 중심까지 거리가 모두 동일
• 사각형은 대각선 방향이 더 멀어서 오차가 생기지만, 육각형은 어느 방향으로나 거리가 비슷해 원형 범위 검색에 압도적으로 유리

---