먼저 지금의 검색을 측정하기

지도 검색이 느리다고 바로 Quadtree를 넣을 필요는 없습니다. 목록 필터링, 거리 계산, 마커 생성, 지도 타일 중 어디서 시간이 걸리는지부터 나눠 봅니다. 인덱스를 만드는 시간과 메모리도 비용이기 때문입니다.

이 글은 인덱스 도입을 결정하는 절차와 작은 예제입니다. 바쿠오 공개 서비스가 Quadtree나 Geohash를 채택했다는 설명이 아닙니다. 로컬 소스에서 찾은 관련 구현만으로 실제 사용자 환경의 개선 수치를 주장하지 않습니다.

경계 상자로 후보 고르기

우선 화면에 보이는 사각 영역 안의 점을 고르는 기준 함수를 만듭니다. 아래 예제는 인덱스 없이 전체 배열을 확인합니다. 빠른 구현을 추가하더라도 결과 비교에 쓸 단순한 기준이 있어야 누락을 찾기 쉽습니다.

function selectBox(points, box) {
  const { south, north, west, east } = box;
  if (![south, north, west, east].every(Number.isFinite)) {
    throw new TypeError('Box edges must be numbers');
  }
  if (south < -90 || north > 90 || west < -180 || east > 180
      || south > north || west > east) {
    throw new RangeError('Expected a non-wrapping geographic box');
  }
  return points.filter(point => {
    if (!Number.isFinite(point.lat) || !Number.isFinite(point.lng)
        || Math.abs(point.lat) > 90 || Math.abs(point.lng) > 180) {
      throw new TypeError('Invalid point');
    }
    return point.lat >= south && point.lat <= north
      && point.lng >= west && point.lng <= east;
  });
}

const points = [
  { id: 'inside', lat: 37.5, lng: 127 },
  { id: 'edge', lat: 37, lng: 126 },
  { id: 'outside', lat: 38.5, lng: 127 }
];
const box = { south: 37, north: 38, west: 126, east: 128 };
console.log(selectBox(points, box).map(point => point.id));
// [ 'inside', 'edge' ]

브라우저 콘솔이나 Node.js에서 실행하면 inside와 edge가 나옵니다. 경계 포함 여부를 비교 연산자로 명확하게 정했습니다. 입력은 실제 매장이 아닌 테스트용 점이며, 날짜변경선을 가로지르는 영역은 이 예제의 지원 범위 밖입니다.

사각형과 반경은 다르다

지도 화면 안의 점을 찾는 질문과 현재 위치에서 반경 안의 점을 찾는 질문은 다릅니다. 원을 둘러싼 사각형으로 먼저 고르면 모서리에 있는 점도 후보에 포함됩니다. 원형 반경 검색은 거리 계산으로 마지막 조건을 다시 확인해야 합니다.

검사 순서는 후보 검색 → 실제 거리 계산 → 반경 밖 제거 → 정렬로 잡을 수 있습니다. 검색 반경이 0인 경우도 값 자체로는 유효할 수 있습니다. 0을 기본 반경으로 조용히 대체하지 말고 제품의 입력 계약에서 허용 여부를 정합니다.

격자와 Quadtree를 비교할 때

고정 격자는 셀별 배열을 만들기 쉬운 대신 셀 크기를 골라야 합니다. 너무 작은 셀은 여러 셀을 방문하고, 너무 큰 셀은 후보가 많이 남습니다. Geohash 접두어를 이용할 때도 이웃 셀과 경계 처리를 빼먹으면 가까운 점을 놓칠 수 있습니다.

Quadtree는 영역을 재귀적으로 나누지만 점이 한곳에 몰리거나 데이터가 자주 바뀌면 구성 비용과 갱신 방식을 살펴야 합니다. 이 설명만으로 우열을 정할 수는 없습니다. 작은 목록의 단순 배열 검색을 포함해 실제 데이터 분포로 비교합니다.

개선 전후에 같은 결과 확인하기

  1. 최초 로딩과 인덱스 구성 시간을 검색 시간과 따로 측정합니다.
  2. 조밀한 지역, 점이 없는 영역, 경계 위의 점으로 결과 ID 집합을 비교합니다.
  3. 데이터가 바뀐 뒤 삭제된 점이 남거나 새 점이 누락되지 않는지 확인합니다.
  4. 마커를 그리는 시간을 포함한 화면 반응과 메모리 사용도 확인합니다.

새 구현이 빨라 보여도 기존 기준과 결과가 다르면 먼저 정확성 문제를 해결해야 합니다. 발표할 수치는 기기·브라우저·데이터·검색 조건을 함께 기록한 측정값으로 제한합니다.