R* 트리의 기본 개념
데이터 처리 분야에서 R* 트리(R*-tree)는 공간 정보(spatial information)를 인덱싱하기 위해 고안된 R-트리(R-tree)의 변형입니다. 일반적인 R-트리와 비교했을 때, R* 트리는 데이터 재삽입(reinsertion) 과정이 필요할 수 있어 구축 비용이 다소 높지만, 그 대가로 훨씬 우수한 질의(query) 성능을 얻을 수 있습니다.
표준 R-트리와 마찬가지로 R* 트리 역시 점(point) 데이터와 공간(spatial) 데이터를 모두 저장할 수 있습니다. R* 텔리의 개념은 1990년 노르트 베크만(Norbert Beckmann), 한스페터 크리겔(Hans-Peter Kriegel), 랄프 슈나이더(Ralf Schneider), 베른하르트 지거(Bernhard Seeger)에 의해 처음 제안되었습니다.
R* 트리와 R-트리의 차이점
R* 트리는 반복적인 삽입(insertion) 방식으로 구축됩니다. 이 과정에서 노드 간의 겹침(overlap)이 거의 발생하지 않기 때문에 우수한 질의 성능을 유지할 수 있습니다.
R-트리 계열 자료구조에서 커버리지(coverage)와 겹침의 최소화는 성능에 결정적인 요소입니다. 데이터 영역이 서로 겹쳐 있으면, 삽입이나 질의 수행 시 트리의 여러 분기를 동시에 탐색해야 하기 때문입니다. 반면 커버리지가 최소화되면 탐색 범위를 효과적으로 줄일(pruning) 수 있어, 특히 조건에 맞지 않는 결과를 걸러내는 부정적 범위 질의(negative range query)에서 페이지 전체를 검색 대상에서 제외하는 일이 잦아집니다.
R* 트리는 이 두 가지 요소를 모두 줄이기 위해 개선된 노드 분할(split) 알고리즘과 노드 오버플로우 시 강제 재삽입(forced reinsertion)이라는 개념을 도입했습니다. 이러한 설계는 R-트리 구조가 항목(entry)의 삽입 순서에 매우 민감하다는 관찰에 기반합니다. 즉, 순차 삽입 방식(대량 적재가 아닌 방식)으로 만들어진 구조는 최적 상태에 못 미칠 가능성이 높으며, 기존 항목을 삭제 후 재삽입함으로써 트리 내에서 더 적합한 위치를 '찾도록' 할 수 있습니다.
알고리즘과 복잡도
- R* 트리는 질의(query) 및 삭제(delete) 연산에 대해 일반 R-트리와 유사한 알고리즘을 사용합니다.
- 삽입 시에는 복합 전략을 적용합니다. 리프(leaf) 노드에서는 겹침을 최소화하고, 내부(inner) 노드에서는 확장(enlargement)과 면적(area)을 최소화합니다.
- 분할 시에는 주변부 길이(perimeter)를 기준으로 분할 축(split axis)을 선택한 뒤 겹침을 최소화하는 위상학적 분할(topological split) 방식을 사용합니다.
- 개선된 분할 전략 외에도, B-트리의 균형(balance) 개념에서 착안하여 객체와 서브트리를 트리에 재삽입함으로써 분할 자체를 회피하려 시도합니다.
따라서 최악의 경우 질의 및 삭제 연산의 복잡도는 일반 R-트리와 유사합니다. 삽입 전략의 경우, R* 트리는 M개 객체를 담는 페이지 크기를 기준으로 선형 분할(linear split, O(M))보다는 O(M log M)으로 더 복잡하지만, 이차 분할(quadratic split, O(M2))보다는 단순하며 전체 복잡도에는 큰 영향을 주지 않습니다.
전체 삽입 복잡도 역시 R-트리와 비슷한 수준을 유지합니다. 재삽입은 트리의 최대 한 개 분기에만 영향을 미치므로 O(log n)번의 재삽입이 발생하며, 이는 일반 R-트리에서 분할(split)을 한 번 수행하는 것과 맞먹는 비용입니다. 결론적으로 R* 트리의 전체 복잡도는 일반 R-트리와 유사하지만, 실제 질의 성능은 더욱 뛰어나다고 평가됩니다.