1. 근접성 서비스

- 2차원 검색 : 모든 사업장정보 좌표를 가진 DB에 현재위치 + 반경 n 을 더한 범위로 쿼리.
    - x,y 축 교집합을 구해야하므로 인덱스가 있더라도, x축, y축 한 컬럼의 속도만 개선될뿐. 조회속도에 비효율적일 수 있다.

- 해시기반 : 균등 격자
    - 정의 : 균등한 크기의 격자로 구역을 나눈다.
    - 장점 : 단순하다.
    - 단점 : 사업장 분포가 균등하지않아 인덱스가 비효율적일 수 있다.
- 해시기반 : Geohash
    - 정의 : 위도,경도 좌표를 해시한 1차원 문자열로 변환한다. 비트를 하나씩 늘려가며 재귀적으로 더 작은 격자로 분할해나간다.
        - ex) geohash의 길이가 6 = 1.2km*609m 격자 크기 -> 특정 좌표기준 반경 0.5km 를 조회할 수 있다. ex) 9q9hvu (base32)
    - 장점 : 구현 비용이 쉽다. 다양한 격자 크기로 조회할 수 있다.
    - 단점 
        - 인구밀도에 따라 동적으로 격자 크기를 조정할 수 없다.
        - index 갱신이 쉽다. (geohash-business_id 매핑 테이블에서 row하나를 삭제하는 격)
        - 격자 가장자리 이슈 1 : 공통 접두어를 가진것은 가까이 모여있지만, 역은 성립하지 않는다. 따라서 접두어 기반 쿼리를 할 수 없다.
        - 격자 가장자리 이슈 2 : 인접한 사업장이지만 다른 격자에 있을 수 있어 인접한 격자까지 조회되어야 한다.
    - 작은 격자에서 충분한양의 쿼리 결과가 조회되지 않은경우, 마지막 비트를 삭제하여 격자 크기를 키워 조회해야한다.
    - 사용회사 : Redis, MongoDB, ElasticSearch
- 트리기반 : QuadTree
    - 정의 : 특정 기준을 만족할때까지 재귀적으로 사분면을 분할하여 트리구조에 저장한다. 
        - ex) 말단 노드는 100개의 사업장을 가지고, 내부 노드는 분할된 사분면에 해당한다.
            - 메모리 추정 : p.20 노드별 사이즈를 추정하여 총 메모리 요구량이 2GB 미만으로,  로컬 서버 메모리에 올리면 충분한 데이터로 판단한다.
            - 트리 구축 소요시간 추정 : n/100 log(n/100) 
                > ??어떻게 나온 숫자인지
    - 장점 : 격자별 균등한 사업장 분포.
        - k번째로 가까운 사업장까지의 목록을 구할 수 있다. 
    - 단점 : 트리구축 소요시간이 길고, 구현난이도가 있다.
        - 서버 시작시간이 길어질 수 있어 여러 서버 동시배포시 고려되어야한다.
        - 사업장 추가/삭제된경우 트리 갱신 비용 : 트리구축 소요시간을 고려하여 서버들을 동시에 갱신하면 장애발생가능.
            - 색인갱신 시간복잡도는 O(log n), 다중 스레드인경우 lock을 사용해야함.
            - 특정 기준을 만족하지 못하는경우 트리를 다시 짜는 리밸런싱이 필요한데, 
    - 사용 회사 : ElasticSearch
- 구글 S2
    - 힐베스트 곡선이라는 공간 채움 곡선을 사용하여 1차원 색인화한다.
        - 힐베스트 곡선 상에서 인접한 두 지점은 색인화 이후 1차원 공간 내에서도 인접한 위치에 있다.
    - geofence : 실세계 지리적 영역에서 설정한 가상의 경계이며(비정형), s2로 구현할 수 있다.
        - ex) 구글, tinder에서 사용된다.
        - 특정 경계를 벗어난 사용자에게 알림을 보낼 수 도 있다.

- geohash redis cache로 조회한 목록 수는 상대적으로 데이터 양이 적을것이므로, 일단 조회하여 필터링한다.