프론트엔드
R-tree를 사용한 가까운 마커 찾기 기능 구현과 개선기
두줄요약
지도에서 드래그 중인 마커의 최근접 마커를 찾는 기능을 구현하고, R-tree와 knn으로 탐색을 최적화했습니다. 최적화 후 CPU 사용률이 줄어들어 지도 UI 성능이 개선되었습니다.
문제 상황
- 지도에서 드래그 중인 마커 기준 500m 이내의 가장 가까운 마커를 찾아 UI를 갱신해야 하는 요구사항
- 마커 수가 늘어날수록 매 드래그 이벤트마다 전체 마커와의 거리 계산이 발생하는 구조
해결 방법
- 카카오맵 드래그 이벤트와 거리 계산으로 초기 기능 구현
- 500m 박스로 후보를 줄이는 R-tree(Rbush) 적용
- 최근접 탐색 rbush-knn으로 후보 탐색 범위를 더 축소
성능/운영 포인트
- 전체 순회 방식은 마커 1000개 수준에서 연산량 급증
- 최적화 후 CPU 평균·최대 사용률 감소
- 지도처럼 무거운 UI에서 체감 성능 개선 가능