R‐tree를 활용한 길 추가 로직 10,000 ms 에서 200ms 최적화
우리 서비스에서는 새로운 길을 추가할 때 기존의 길과 겹치는지를 확인하는 로직이 필요했습니다. 기존 방식에서는 모든 길을 탐색하며 겹침 여부를 판단하는 방식이었고, 이 과정에서 O(N^2)의 연산이 발생하여 총 20,000ms(20초)의 시간이 소요되었습니다. 이는 서비스 성능 저하를 야기하며 사용자 경험에도 부정적인 영향을 미쳤습니다.
길 겹침 판별의 속도를 개선하기 위해 공간 데이터 검색에 강점을 가진 R-tree를 도입했습니다. R-tree는 공간적으로 가까운 객체들을 그룹화하여 계층적으로 저장하는 트리 구조로, 특정 영역 내의 객체를 빠르게 검색할 수 있도록 도와줍니다.
R-tree는 2차원 공간에서 객체(예: 선, 다각형, 점 등)를 효율적으로 관리하기 위한 트리 구조의 데이터 구조입니다.
- 공간을 계층적으로 분할하여 Bounding Box 단위로 저장합니다.
- 특정 위치와 겹치는 객체를 탐색할 때, 모든 객체를 순차적으로 탐색하는 것이 아니라, 해당 영역과 연관 있는 Bounding Box만을 검색합니다.
- 탐색, 삽입, 삭제 성능이 O(log N) 수준으로 개선됩니다.
- 기존의 길 데이터를 R-tree에 삽입하여 저장했습니다.
- 새로운 길이 추가될 때, 해당 길의 Bounding Box를 생성했습니다.
- R-tree를 활용하여 겹칠 가능성이 있는 후보 길들만 빠르게 탐색했습니다.
- 탐색된 후보 길들과만 실제 겹침 여부를 판별하여 최종 판단했습니다.
기존 O(N^2)의 탐색 방식에서는 20,000ms(20초)가 소요되었으나, R-tree를 적용한 후에는 O(log N) 수준으로 최적화되어 200ms로 성능이 획기적으로 개선되었습니다.
공간 데이터를 다룰 때 단순한 반복 탐색보다는 적절한 인덱싱 기법을 활용하는 것이 중요합니다. 이번 최적화를 통해 R-tree가 공간 검색 문제에서 강력한 성능을 발휘할 수 있음을 확인했으며, 향후 유사한 공간 연산이 필요한 서비스에서도 적극적으로 활용할 계획입니다.