Architecture - 근접성 서비스
in DEV on Dev, Architecture
목차
- 1. 문제 이해 및 설계 범위 확정
- 2. 개략적 설계안 제시
- 3. 상세 설계
- 4. 마무리
- 참고 사이트 & 함께 보면 좋은 사이트
1. 요구사항 및 규모 추정
근접성 서비스(Proximity Service)는 사용자의 현재 지리적 위치(위도와 경도)를 기반으로 특정 반경 내에 있는 음식점, 주유소 등의 사업장 목록을 검색하고, 정보를 제공하는 위치 기반 서비스(LBS, Location-Based Service)이다. 대표적으로 주변 식당을 찾는 ‘옐프(Yelp)’나 가까운 주유소를 검색하는 ‘구글 맵’이 이에 해당한다.
대규모 아키텍처를 설계할 때 가장 먼저 해야 할 일은 시스템의 한계와 범위를 명확히 하는 것이다.
기획 및 기술적 제약 조건을 바탕으로 도출된 핵심 요구사항은 아래와 같다고 가정한다.
1.1. 기능 요구사항
- 위치 기반 검색
- 사용자의 GPS 좌표(위도/경도)와 선택한 반경에 매칭되는 사업장 목록을 정확하게 반환해야 한다.
- 동적 반경 변경
- 사용자는 UI에서 검색 반경을 0.5km, 1km, 2km, 5km, 20km 로 자유롭게 변경할 수 있어야 하며, 최대 허용 반경은 20km로 제한한다.
- 사업장 데이터 관리
- 사업장 소유주는 자신의 사업장 정보를 시스템에 추가/삭제/갱신할 수 있다.
- 비실시간 반영 허용
- 소유주가 수정한 정보가 검색 결고에 실시간으로 반영될 필요는 없으며, 다음 날까지만 반영되어도 무방하다.
- 상세 정보 조회
- 고객은 검색된 사업장의 상세 페이지를 조회할 수 있어야 한다.
- 화면 자동 갱신 비활성화
- 사용자가 이동 중이더라도 이동 속도가 아주 빠르지 않으므로, 현재 위치 기준으로 화면을 상시 자동 갱신할 필요는 없다.
1.2. 비기능 요구사항
- 낮은 응답 지연(Low Latency)
- 사용자가 주변 검색을 할 때 답답함을 느끼지 않도록 매우 신속하게 결과를 반환해야 한다.
- 고가용성 및 규모 확장성
- 인구 인집 지역(예: 강남역)에서 특정 시간대(점심/퇴근 시간)에 트래픽이 급증해도 시스템이 동작해야 한다.
- 데이터 보호 및 사생활 보장
- 사용자 위치 정보는 민감한 개인정보이므로, 이를 안전하게 보호하고 관련 법령을 준수해야 한다.
GDPR(General Data Protection Regulation)
GDPR(유럽 일반 개인정보보호법)은 유럽연합(EU)이 제정한 세계에서 가장 강력한 개인정보 보호 법령이다.
사용자의 위치 데이터와 같은 민감 정보는 GDPR의 핵시 규제 대상이다.
- 핵심 원칙: 기업은 사용자의 위치 정보를 수집할 때 명시적 동의를 받아야 하며, 목적 달성 후에는 지체 없이 파기 또는 익명화해야 한다.
- 잊힐 권리(Right to Forgotten): 사용자가 요청하면 시스템 내에 저장된 사용자의 위치 이력 등 모든 개인 데이터를 완전히 삭제할 수 있는 구조를 아키텍처 설계 단계부터 반영해야 한다.
1.3. 개략적 규모 추정(Back-of-the-envelope calculation)
시스템 인프라의 규모를 결정하기 위해 대략적인 트래픽과 처리량(QPS)를 산정해본다.
- 기본 가정 수치
- 일일 능동 사용자 수(DAU, Daily Active User): 1억명(\(10^8\))
- 총 등록 사업장 수: 2억 개(\(2 * 10^8\))
- 사용자당 일평균 검색 횟수: 5회
- QPS(Query Per Second) 계산
- 하루 시간인 86,400초룰 계산 편의상 \(10^5\)초로 올림하여 계산한다.
- 하루 총 검색 수 = \(10^8\)명 * 5회 = 5 * \(10^8\)회
- 평균 QPS = \(\frac{5 * 10^8회}{10^5초} = 5,000\)
최종적으로 시스템은 평균 5,000 QPS를 처리할 수 있어야 하며, 트래픽 피크 타임을 고려하면 이보다 2~3배 높은 대역폭을 감당할 수 있는 확장성이 필요하다.
이 시스템은 전형적인 읽기 중심(Read-heavy) 시스템으로, 초당 5,000번 이상의 읽기 요청을 지연 없어 처리하는 것이 핵심이다.
위치 정보는 GDPR/CCPA 규정을 철저히 준수하도록 설계 단계부터 보안 및 익명화 전략을 수립해야 한다.
데이터의 실시간 동기화 요구사항이 낮으므로(익일 반영), DB 쓰기 부하보다는 조회 성능 최적화와 캐싱 전략에 집중해야 한다.
2. 개략적 설계안 제시
여기서는 아래의 내용을 논의한다.
- API 설계
- 데이터 모델
- 개략적 설계안
- 주변 사업장 검색 알고리즘
2.1. API 설계
- GET /v1/search/nearby (페이징 필요)
- parameters
- latitude(검색할 위도): Decimal
- longitude(검색할 경도): Decimal
- radius(반경): optional, 기본값 5km: (Int)
response
{ "total": 10, "businesses": [ { business object } // 검색 결과 페이지에 표시될 모든 정보 ] }
- parameters
- GET /v1/businesses/:id
- POST /v1/businesses
- PUT /v1/businesses/:id
- DELETE /v1/businesses/:id
장소나 사업장 검색 관련하여 실제 사용되는 API는 아래를 참고하면 된다.
- 구글 장소 API: https://developers.google.com/maps/documentation/places/web-service/legacy/search?hl=ko
- 옐프 사업장 API: https://docs.developer.yelp.com/reference/v3_business_search
2.2. 데이터 모델
- 읽기/쓰기 비율
- 스키마 설계
2.2.1. 읽기/쓰기 비율
주변 사업장 검색과 사업장 정보 확인 API 로 인해 읽기 연산이 굉장히 자주 수행된다.
한편, 사업장 정보 추가/삭제/편집은 빈번하지 않으므로 쓰기 연산 실행은 낮다.
읽기 연산이 압도적인 시스템에서는 MySQL 같은 관계형 데이터베이스가 바람직할 수 있다. (궁금증)왜 읽기 연산이 압도적인 시스템에서는 MySQL 같은 관계형 데이터베이스가 바람직할 수 있는 거지? 다른 DB는 읽기에 불리한 것인가? MongoDB나 Redis 가 답이 될 수 있지 않나? 아니면 Oracle, Mssql에 비해서 MySQL이 바람직하다는 건가?
2.2.2. 데이터 스키마
테이블은 business 테이블과 지리적 위치 색인 테이블(geospatial index table)이 있다.
business 테이블은 사업장 상세 정보를 담으며, business_id가 PK 이고, 주소, 도시, 이름 등은 각 컬럼으로 구성한다.
지리적 위치 색인 테이블은 위치 정보 관련 연산의 효율성을 높이는데 쓰인다. Geohash에 대한 지식이 필요하므로 이 내용은 2.4.3. 지오해시(Geohash) 와 3.1. 데이터베이스 규모 확장성 에서 다룬다.
2.3. 개략적 설계안
이 시스템은 위치 기반 서비스(LBS)와 사업장관련 서비스, 두 부분으로 구성된다.
graph TD
%% 스타일 정의
classDef userStyle fill:#fff,stroke:#333,stroke-width:2px;
classDef lbStyle fill:#fff,stroke:#333,stroke-width:1.5px;
classDef serviceStyle fill:#fff,stroke:#333,stroke-width:1.5px;
classDef masterDbStyle fill:#777,stroke:#333,stroke-width:2px,color:#fff;
classDef replicaDbStyle fill:#fff,stroke:#333,stroke-width:1.5px;
%% 노드 배치
User((사용자))
LB[로드밸런서]
LBS[LBS]
BizService[사업장 서비스]
subgraph DB_Cluster [데이터베이스 클러스터]
direction LR
Replica1[(사본 데이터베이스)]
Replica2[(사본 데이터베이스)]
Replica3[(사본 데이터베이스)]
Master[(주 데이터베이스)]
end
%% 스타일 적용
class User userStyle;
class LB lbStyle;
class LBS,BizService serviceStyle;
class Master masterDbStyle;
class Replica1,Replica2,Replica3 replicaDbStyle;
%% 흐름 연결
User --> LB
LB -->|/search/nearby| LBS
LB -->|"/businesses/{:id}"| BizService
LBS -->|읽기| Replica1
LBS -->|읽기| Replica2
LBS -->|읽기| Replica3
BizService -->|쓰기| Master
%% 복제 흐름 (주 -> 사본)
Master -.->|복제| Replica1
Master -.->|복제| Replica2
Master -.->|복제| Replica3
2.3.1. 위치 기반 서비스(LBS)
주어진 위치와 반경 정보를 이용해 주변 사업장을 검색한다.
- 쓰기 요청이 없고, 읽기 요청만 빈번히 발생한다.
- QPS가 높으며, 특정 시간대의 인구 밀집 지역일수록 그 경향이 심하다.
- stateless 서비스이므로 Scale-out 이 쉽다.
2.3.2. 사업장 서비스
사업장 서비스는 두 종류의 요청을 처리한다.
- 사업장 소유주가 사업장 정보를 생성/갱신/삭제한다.
- 기본적으로 쓰기 요청이며, QPS는 높지 않다.
- 고객이 사업장 정보를 조회하며, 특정 시간대에 QPS가 높아진다.
2.3.3. 데이터베이스 클러스터
복제에 걸리는 시간 지연 때문에 primary DB와 secondary DB 데이터 사이에 차이가 있을 수 있지만, 사업장 정보가 실시간으로 갱신될 필요가 없으므로 문제되지 않는다.
2.3.4. 사업장 서비스와 LBS의 규모 확장성
사업장 서비스와 LBS 모두 stateless 이므로 점심 시간 등 특정 시간대에 집중적으로 트래픽이 몰릴 때는 자동으로 서버를 추가하고, 야간 시간대에는 서버를 삭제하도록 구성 가능하다.
2.4. 주변 사업장 검색 알고리즘(핵심)
실제로 많은 회사가 레디스 지오해시(Geohash in Redis)나 PostGIS 확장을 설치한 Postgres DB를 활용한다.
이제 주변 사업장 검색 방법들을 몇 가지 살펴본 후 각 방안에 어떤 trade-off가 존재하는지 알아본다.
- 2차원 검색
- 균등 격자
- Geohash
- 쿼드트리
- 구글 S2
2.4.1. 2차원 검색
주어진 반경으로 그린 원 안에 놓인 사업장을 검색하는 방법이다. 지나치게 단순하다는 단점이 있다.
SELECT business_id, latitude, longitude
FROM business
WHERE (longitude BETWEEN {:my_lat} - radius AND {:my_lat} + radius)
AND (latitude BETWEEN {:my_long} - radius AND {:my_long} + radius)
위 질의는 테이블 전부를 읽어야 하므로 효율적이지 않다.
위도와 경도에 인덱스를 만들어도 데이터가 2차원적이므로 컬럼별로 가져온 결과도 여전히 엄청난 양이다.
위도 컬럼의 데이터 집합 1과 경도 컬럼의 데이터 집합 2는 빠르게 추출 가능하지만, 주어진 반경 내 사업장을 얻으려면 두 집합의 교집합을 구해야 하는데, 이 연산은 각 집합에 속한 데이터의 양 때문에 효율적일 수 없다.
이렇게 인덱스를 하는 것의 문제는 오직 한 차원의 검색 속도만 개선할 수 있다는 것이다. (궁금증) 위도와 경도를 복합키로 만들면 되지 않을까?
그럼 자연스럽게 2차원 데이터를 1차원에 대응시킬 방법이 있을까? 를 알아보기 전에 인덱스를 만드는 방법들부터 알아보자.
지리적 정보에 인덱스를 만드는 방법을 두 종류이다.
graph TD
Idx[인덱스]
%% 1단계 분류 (선으로 연결)
Idx --- Hash(해시 hash)
Idx --- Tree(트리 tree)
%% 해시 기반 방안
Hash --- Grid[균등 격자<br>even grid]
Hash --- Geohash[지오해시<br>Geohash]
Hash --- Cartesian[카르테시안 계층<br>Cartesian tiers]
%% 트리 기반 방안
Tree --- Quad[쿼드트리<br>Quadtree]
Tree --- S2[구글 S2]
Tree --- RTree[R 트리<br>R-tree]
%% 4개 노드 진한 색상 강조
style Grid fill:#444,stroke:#222,color:#fff
style Geohash fill:#444,stroke:#222,color:#fff
style Quad fill:#444,stroke:#222,color:#fff
style S2 fill:#444,stroke:#222,color:#fff
각 색인법은 구현 방법은 다르지만 지도를 작은 영역으로 분할하고, 고속 검색이 가능하도록 색인을 만든다는 아이디어는 같다.
2.4.2. 균등 격자(Even grid)
지도를 작은 격자 또는 구획으로 나누는 단순한 접근법이다. <균등 격자의="" 문제점=""> 1. 사업장 분포가 균일하지 않음 1. 서울엔 많은 사업장이 있지만 사막에 사업장이 있을 리 없는데 전 세계를 동일한 크기의 격자로 나누면 데이터 분포는 전혀 균등하지 않음 2. 이상적으로는 인구 밀집 지역에는 작은 격자를, 그렇지 않은 지역에는 큰 격자를 사용하는 것이 좋음 2. 주어진 격자의 인접 격자를 찾기 까다로울 수 있다. 1. 다른 방안들과 달리 격자 식별자 할당에 명확한 체계가 없기 때문이다. --- ### 2.4.3. 지오해시(Geohash) 2차원의 위도,경도 데이터를 1차원의 문자열로 반환한다. 비트를 하나씩 늘려가면서 재귀적으로 세계를 더 작은 격자로 분할해나간다. 먼저 전 세계를 본초 자오선과 적도 기준 사분면으로 나눈다. (궁금증) 본초 자오선에 대해 간략히 설명해줘. - 위도 범위 [-90, 0]은 0에 대응 - 위도 범위 [0, 90]은 1에 대응 - 경도 범위 [-180, 0]은 0에 대응 - 경도 범위 [0, 180]은 1에 대응 그 격자를 또 다시 사분명으로 나누고, 이 때 각 격자는 경도와 위도 비트를 위처럼 순서대로 반복한다. 이 절차를 원하는 정밀도(precision)를 얻을 때까지 반복한다.  지오해시는 통상적으로 base32 표현법을 사용한다. 예) 구글 본사 지오해시 (길이 = 6) 1001 10110 01001 10000 11011 11010 (base32 이진 표기) → 9q9hvu (base32) 지오해시는 12단계의 정밀도를 갖는데, 이 정밀도가 격자 크기를 결정한다. [지오해시 길이와 격자 크기] | 지오해시 길이 | 격자 너비 × 높이 | | --- | --- | | 1 | 5,009.4km × 4,992.6km (지구 전체) | | 2 | 1,252.3km × 624.1km | | 3 | 156.5km × 156km | | 4 | 39.1km × 19.5km | | 5 | 4.9km × 4.9km | | 6 | 1.2km × 609.4m | | 7 | 152.9m × 152.4m | | 8 | 38.2m × 19m | | 9 | 4.8m × 4.8m | | 10 | 1.2m × 59.5cm | | 11 | 14.9cm × 14.9cm | | 12 | 3.7cm × 1.9cm | 그럼 최적 정밀도는 어떻게 정할까? 사용자가 지정한 반경으로 그린 원을 덮는 최소 크기 격자로 만드는 지오해시 길이를 구해야 한다. [검색 반경과 지오해시 길이] | 반지름 (킬로미터) | 지오해시 길이 | | --- | --- | | 0.5km (0.31마일) | 6 | | 1km (0.62마일) | 5 | | 2km (1.24마일) | 5 | | 5km (3.1마일) | 4 | | 20km (12.42마일) | 4 | --- #### 2.4.3.1. 격자 가장자리 이슈 지오해시는 해시값의 공통 prefix가 긴 격자들이 서로 더 가깝게 놓이도록 보장한다.  하지만 그 역은 참이 아닐 수 있다. 아주 가까운 두 위치가 어떤 공통 접두어도 갖지 않을 수도 있다. 두 지점이 적도의 다른 쪽에 놓이거나, 자오선 상의 다른 반쪽에 놓이는 경우다. 예를 들어 a 상점은 지오해시 u000 이고, b 상점은 지오해시 ezzz 값을 갖고, 두 상점은 30km 밖에 떨어져있지 않지만 두 지오해시 사이에는 어떤 공통 prefix도 없다. 이런 문제점 때문에 아래와 같이 단순한 prefix 기반 SQL 질의문을 사용하면 주변 모든 사업장을 가져올 수 없다. ```sql SELECT * FROM geohash_index WHERE geohash LIKE 'u17e0%'; ``` 격자 가장자리의 또 다른 문제는 두 지점이 공통 prefix 길이는 길지만 서로 다른 격자에 놓이는 경우이다.  이 때 가장 흔히 사용되는 해결책은 현재 격자에 인접한 모든 격자의 모든 사업장 정보를 가져오는 것이다. 특정 지오해시의 주변 지오해시를 찾는 것은 상수 시간(constant time)에 가능한 연산이고, 상세 내용은 [지오해시](https://www.movable-type.co.uk/scripts/geohash.html)를 참고하면 된다. --- #### 2.4.3.2. 표시할 사업장이 충분하지 않은 경우 현재 격자와 주변 격자를 다 보아도 표시할 사업장이 충분하지 않으면 어떻게 해야할까? 1. 주어진 반경 내 사업장만 반환한다. 1. 구현하지 쉽지만 사용자의 욕구를 만족하기 충분한 수의 사업장 정보를 반환하지 못함 2. 검색 반경을 키운다. 1. 지오해시의 마지막 비트를 삭제하여 얻은 새 지오해시 값을 사용하여 주변 사업장을 검색한다. 2. 그래도 사업장 수가 충분하지 않으면 또 한 비트를 지워서 범위를 다시 확장한다. --- ### 2.4.4. 쿼드트리(Quadtree) 쿼드트리는 격자의 내용이 특정 기준을 만족할 때까지 2차원 공간을 재귀적으로 사분면 분할하는데 흔히 사용되는 자료 구조이다. 예) 격자에 담긴 사업장 수가 100 이하가 될 때까지 분할 쿼드트리를 사용한다는 것은 결국 질의에 답하는 데 사용될 트리 구조를 메모리 안에서 만드는 것이다. 쿼드트리는 메모리 안에 놓이는 자료 구조일 뿐 DB가 아니라는 것에 유의하자. 이 자료구조는 각각의 LBS 서버에 존재해야 하며, 서버가 시작되는 시점에 구축된다. 전 세계에 백만개의 사업장이 있다고 해보자.  그 과정을 좀 더 자세히 시각화하면 아래와 같다.  쿼드트리 구축 트리의 루트 노드는 세계 전체 지도이고, 이 루트 노드를 사분면 각각을 나타내는 하위 노드로, 어떤 노드도 사업장 100개를 너지 않을때까지 재귀적으로 분할한다. ```kotlin fun buildQuadtree(node: TreeNode) { if (countNumberOfBusinessesInCurrentGrid(node) > 100) { node.subdivide() for (child in node.children) { buildQuadtree(child) } } } ``` --- #### 2.4.4.1. 쿼드트리를 저장하는데 필요한 메모리는? 이 질문에 답하려면 어떤 데이터가 쿼드트리에 보관되는지 먼저 알아야 한다. - Leaf Node에 저장되는 데이터 - 격자를 식별하는데 사용할 좌상단과 우하단 꼭짓점 좌표: 32 byte(8 byte * 4) → (궁금증)좌상단과 우차단 꼭짓점 좌표인데 왜 곱하지 4이지? - 격자 내부 사업장 ID 목록: ID당 8 byte * 100 (한 격자에 허용되는 사업장 수의 최댓값) - 총 832 byte - Internal Node에 저장되는 데이터 - 격자를 식별하는데 사용할 좌상단과 우하단 꼭짓점 좌표: 32 byte(8 byte * 4) - 하위 노드 4개를 가리킬 포인터: 32 byte(8 byte * 4) - 총 64 byte 한 격자에 허용되는 사업장 수의 최대값에 좌우되기는 하지만 그 값은 트리안에 저장하지 않아도 된다. 데이터베이스가 이미 그 최대값을 고려하여 분할되어 있기 때문이다. → (궁금증) “한 격자에 허용되는 사업장 수의 최대값에 좌우되기는 하지만 그 값은 트리안에 저장하지 않아도 된다. 데이터베이스가 이미 그 최대값을 고려하여 분할되어 있기 때문이다.” 이 문장이 이해가 안됨. 데이터베이스가 이미 최대값을 고려하여 어떻게 분할되어 있다는 것인지? 이제 각 노드가 어떤 데이터를 저장하는지 알았으니 메모리를 계산해보자. 전 세계에는 이백만개의 사업장이 있다고 가정한다. - 격자 안에는 최대 100개의 사업장이 있을 수 있음 - Leaf node의 수 =~ $\frac{200m}{100}$ =~ 2백만(2m) - Internal node의 수 = 2m * $\frac{1}{3}$ =~ 0.67m - Internal node의 수가 왜 Leaf node 수의 $\frac{1}{3}$ 인지는 [쿼드트리에는 얼마나 많은 Leaf node가 있는가](https://stackoverflow.com/questions/35976444/how-many-leaves-has-a-quadtree) 를 참고하면 된다. - 총 메모리 요구량 = 2m * 832byte + 0.67m * 64byte =~ 1.71GB 트리를 구축하는데 드는 부가적인 메모리를 감안하더라도 총 메모리 요구량은 꽤 작다. 쿼드트리 인덱스가 메모리를 적게 사용하지만 읽기 연산 양이 많아지면 서버 한 대의 CPU나 네트워크 대역폭으로는 감당하기 어려워지므로 읽기 연산을 여러 대 쿼드트리 서버로 분리하는 것이 좋다. --- #### 2.4.4.2. 쿼드드리 구축에 소요되는 시간은? 각 Leaf node에는 대략 100개의 사업장 ID가 저장된다. 전체 사업장 수를 n이라 하면 트리를 구축하는 시간 복잡도는 $\frac{n}{100}\log\frac{n}{100}$ 이다. 200m개의 사업장 정보를 인덱싱하는 쿼드트리 구축에는 몇 분 정도가 소요될 수 잇다. (궁금증) 왜 시간 복잡도는 $\frac{n}{100}\log\frac{n}{100}$ 인거지? --- #### 2.4.4.3. 쿼드트리로 주변 사업장을 검색하려면? - 메모리에 쿼드트리 인덱스를 구축한다. - 검색 시작점이 포함된 Leaf node를 만날 때까지, 트리의 루트 노드부터 탐색한다. 해당 노드에 100개의 사업장이 있는 경우에는 해당 노드만 반환한다. 그렇지 않은 경우에는 충분한 사업장 수가 확보될 때까지 인접 노드도 추가한다. --- #### 2.4.4.4. 쿼드트리 운영 시 고려사항 1. 서버를 시작할 때 트리를 구축하면서 서버 시작 시간이 길어질 수 있다. 쿼드트리를 만들고 있는 동안 서버는 트래픽을 처리할 수 없기 때문에 blue/green 배포 방식을 택해야 한다. 단, 배포 시 각 서버에 200m개의 사업장 정보를 DB에서 동시에 읽게 되어 시스템에 큰 부하가 갈 수 있다는 점을 유의해야 한다. 1. 사업장이 추가/삭제되었을 때 쿼드트리를 갱신하는 문제가 생긴다. 가장 쉬운 방법은 점진적으로 갱신하는 것이다. 클러스터 내의 모든 서버를 한 번에 갱신하는 대신 점진적으로 몇 개씩만 갱신하는 것이다. 짧은 시간 동안 낡은 데이터가 반환될 수 있지만 요구사항이 엄격하지 않다면 일반적으로 용인할 수 있으며, 새로 추가한 사업장의 정보가 다음날 반영되어도 된다면 문제가 되지 않는다. 밤 시간에 캐시를 일괄 갱신하면 되기 때문이다. 이 접근법의 한가지 문제는 수많은 key가 한 번에 무효화되어 캐시 서버에 큰 부하가 가해질 수 있다는 것이다. 쿼드트리를 실시간으로 갱신하는 것도 가능하지만 그러면 설계가 복잡해진다. 여러 스레드가 쿼드트리 자료 구조를 동시 접근하는 경우엔 더욱 그렇다. 그런 상황을 처리하려면 lock 메커니즘을 사용해야 하기 때문이다. --- #### 2.4.4.5. 실제 사용되는 쿼드트리 사례 아래는 [실제 사용되는 쿼드트리 구축 사례](https://www.educative.io/answers/what-is-a-quadtree-how-is-it-used-in-location-based-services)이다. 인구 밀집 지역에는 작은 격자를, 그렇지 않은 지역에는 큰 격자를 사용한다.  --- ### 2.4.5. 구글 S2 [구글 S2 기하(geometry) 라이브러리](https://s2geometry.io/)는 아주 유명한 솔루션이다. 쿼드트리처럼 구글 S2도 메모리 기반이다. 지구를 [힐베르트 곡선(Hilbert curve)](https://en.wikipedia.org/wiki/Hilbert_curve)이라는 공간 채움 곡선(space-filling curve)을 사용하여 1차원 색인화하는 방식이다. 힐베르트 곡선 상에서 인접한 두 지점은 색인화 이후 1차원 공간 내에서도 인접한 위치에 있다. 1차원 공간 내에서의 검색은 2차원 공간에서의 검색보다 훨씬 효율적이다.
