R+Tree로 공간 인덱스 중첩을 줄이는 방법

겹친 MBR이 늘리던 탐색 경로를 줄이는 인덱스

R+Tree는 R-Tree를 변형한 공간 인덱스다. R-Tree와 비슷하게 노드와 분할 연산을 사용하지만, 내부 노드의 최소경계사각형(MBR, Minimum Bounding Rectangle)이 같은 레벨에서 겹치지 않도록 하거나 중첩을 가능한 한 작게 만드는 데 초점을 둔다.

영역이 겹치면 하나의 질의가 여러 서브트리로 내려갈 수 있다. R+Tree는 객체 또는 MBR을 복제하거나 클리핑해 하위 노드에 나눠 배치함으로써 이 경로를 줄인다. 범위 질의와 포인트 질의에서 I/O 및 비교 연산을 줄이려는 선택이다.

구조적으로는 중첩을 허용하고 복제를 거의 하지 않는 R-Tree와, 축 정렬 공간 분할을 사용하는 KD-Tree의 중간에 놓인다. R-Tree의 유연한 노드 구성을 유지하면서 KD-Tree의 비중첩 분할 특성을 취한다.

노드에 중첩 제약을 적용하는 방식

내부 노드는 자식 포인터와 각 자식 영역의 MBR을 보관한다. R+Tree에서는 이 영역들이 가능한 한 서로 분리된 분할 집합이 되도록 관리한다. 리프 노드에는 실제 객체의 MBR과 데이터 참조가 들어가며, 복제 정책에 따라 동일한 객체 참조가 여러 리프에 존재할 수 있다.

삽입할 때는 중첩 증가가 가장 작은 자식 분기를 고른다. 중첩 제약을 만족하지 못하면 객체의 MBR을 클리핑하거나 복제해 여러 리프에 배치한다. 노드가 용량을 넘으면 분할을 수행하고, 이 분할은 상위 노드로 전파된다. 전파 과정에서도 중첩 제약은 유지돼야 한다.

삭제에서는 복제된 객체의 참조를 고려해야 한다. 리프 언더플로우가 발생하면 재삽입 또는 병합으로 균형을 되찾고, 중첩 제약이 깨지면 국소 재분할로 구조를 복구한다. 최근접 질의(NN)는 우선순위 큐 기반 탐색과 결합할 수 있으며, 이때 가지치기 효율을 높일 수 있다.

⤢✕

분할이 연쇄적으로 발생하면 상위 노드에서 중첩 제약이 깨질 수 있다. 이 경우 국소 재분할 또는 재삽입이 필요하다.

R-Tree와 KD-Tree 사이에서 보는 선택지

지표	R-Tree	R+Tree	KD-Tree
범위 질의 성능	데이터 편향 시 브랜치 다중 탐색 증가	중첩 최소화로 브랜치 감소, 평균 향상	축 정렬 분할, 직교 범위에 강점
노드 중첩	허용(상당)	동일 레벨에서 최소/불허 지향	없음(공간 분할)
공간 오버헤드	낮음(복제 거의 없음)	복제/클리핑으로 증가 가능	낮음
삽입/삭제 비용	보통, 단순	분할/복제 존재하나 브랜치 수 절감으로 실효 비용 우수	삽입/재균형 비용 증가 가능
차원 확장성	중간(차원 증가 시 성능 저하)	중간(중첩 완화로 이점)	고차원에서 성능 급락(축 분할 한계)
운영 편의	구현 용이	구현 복잡도 증가	구현 단순, 튜닝 난이도 낮음

공간 질의가 반복되는 시스템에서의 활용

위치 기반 서비스에서는 지오펜싱, 반경 검색, 근접 상점 탐색에 사용할 수 있다. 동시 질의가 많은 환경이라면 브랜치 수 감소가 지연 시간 안정화에 도움이 된다.

GIS, 도시계획, 측량 분야에서는 대규모 폴리곤과 폴리라인의 범위 질의가 대상이다. 레벨 간 중첩을 줄이면 디스크와 캐시 미스를 낮추는 방향으로 작동한다. 게임과 시뮬레이션에서는 충돌 감지를 위한 광상자(culling)의 1차 필터에 적용할 수 있으며, 프레임 안에서 질의가 반복될 때 예측 가능한 성능을 확보하는 데 쓰인다.

CAD와 EDA 레이아웃 탐색에서는 레이어·셀 범위 선택과 DRC 후보 영역 추출에 활용할 수 있다. 이 경우 복제로 생기는 공간 오버헤드를 감수하더라도 탐색 효율이 우선일 수 있다.

분할 정책과 복제 정책을 함께 설계한다

페이지 크기와 최대 자식 수(M)는 디스크·캐시 라인 정렬, MBR 저장 크기, 포인터 수를 고려해 정한다. fan-out을 크게 확보하는 것이 설계의 한 축이다.

복제 상한은 예를 들어 객체당 k개 리프로 둘 수 있다. 대형 MBR이 과도하게 복제되지 않도록 클리핑을 우선하는 규칙도 필요하다. 분할에서는 중첩 최소화를 우선 기준으로 두고 면적 증가 최소화를 보조 기준으로 사용할 수 있다. 엔트로피 기반 방식이나 SAH(표면적 휴리스틱) 변형도 적용 가능하다.

읽기가 많은 워크로드라면 중첩 제약을 강화하고 복제를 더 허용할 수 있다. 쓰기 비중이 높다면 복제 상한을 낮추고 분할 비용을 제한하며 배치 삽입을 도입하는 편이 맞다.

노드 보호에는 경량 래치(latch)를 사용하고, 분할 연쇄에는 lock coupling을 적용한다. 트리 구조가 바뀌는 구간은 짧은 상위 락으로 원자성을 확보한다. 삭제 이후 희소 노드를 재삽입하는 주기를 두고, 통계 수집으로 데이터 분포 변화를 감지해 재구성 윈도우를 운영한다.

성능 이점과 감수해야 할 비용

데이터 분포와 페이지 크기에 따라 범위·포인트 질의의 평균 탐색 브랜치 수는 2050% 감소할 수 있다. 디스크·캐시 I/O 절감은 P95 지연 시간을 1535% 개선할 것으로 기대된다.

데이터 편향이나 클러스터링이 있는 환경에서는 스루풋의 일관성을 높이고, 대량 읽기가 동시에 발생하는 경우 큐잉 지연을 완화할 수 있다. 반면 복제와 클리핑 때문에 공간 오버헤드는 10~30% 증가할 수 있다. 총 TCO 감소 효과는 데이터 크기, 객체 크기, 복제 상한에 의존한다.

읽기 중심 워크로드에는 중첩 최소화의 이점이 크지만, 인덱스 크기 증가와 분할 비용, 구현 복잡도도 함께 커진다. 대형 MBR 비율이 높다면 클리핑을 먼저 적용하고, 초기 구축은 배치 삽입(Bulk-load)으로 수행할 수 있다. Hilbert/Space-filling curve 기반으로 정렬한 뒤 삽입하면 분할을 줄일 수 있다.

운영에서는 노드 평균 중첩 비율, 평균 브랜치 수, 리프 점유율, 복제율을 함께 추적한다. R+Tree는 공간 질의가 읽기 중심이고 데이터 분포가 편향됐으며 동시 탐색이 많은 조건에서 우선 검토할 수 있는 구조다.