기본 개념
데이터 처리의 경우 R*-트리는 공간 정보를 인덱싱하기 위해 구현된 R-트리의 변형으로 정의됩니다.
R*-트리는 데이터를 다시 삽입해야 할 수 있으므로 표준 R-트리보다 구성 비용이 약간 더 큽니다. 그러나 결과 트리는 일반적으로 더 나은 쿼리 성능을 갖습니다. 표준 R-트리와 동일하게 점 및 공간 데이터를 모두 저장할 수 있습니다. R*-tree의 개념은 1990년 Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider 및 Bernhard Seeger에 의해 제안되었습니다.
R*-트리와 R-트리의 차이점
R*-Tree는 반복 삽입으로 구성됩니다. 이 트리에는 겹치는 부분이 거의 없으므로(거의 없음) 쿼리 성능이 좋습니다. Coverage와 Overlap을 최소화하는 것은 R-tree의 성능에 매우 중요합니다. 데이터 삽입 또는 쿼리에서 겹침의 의미는 트리의 둘 이상의 분기를 확장해야 한다는 것입니다(겹칠 수 있는 영역에서 데이터가 분할되는 방식으로 인해). 최소화된 범위는 특히 음수 범위 쿼리의 경우 자주 검색에서 전체 페이지를 제외할 수 있도록 하여 정리 성능을 향상시킵니다. R*-tree는 수정된 노드 분할 알고리즘 모음과 노드 오버플로 시 강제 재삽입 개념을 구현하여 두 가지 모두를 줄이려고 시도합니다. 이 개념은 R-트리 구조가 항목이 삽입되는 순서에 매우 민감하므로 삽입 빌드(대량 로드가 아닌) 구조가 차선책일 가능성이 있다는 관찰을 기반으로 합니다. 항목을 삭제하고 다시 삽입하면 실제 위치보다 더 적절한 위치를 트리에서 "찾을" 수 있습니다.
알고리즘 및 복잡성
- R*-트리는 쿼리 및 삭제 작업을 위한 일반 R-트리와 유사한 알고리즘을 구현합니다.
- 삽입 시 R*-tree는 결합 전략을 구현합니다. 리프 노드의 경우 겹침이 최소화되고 내부 노드의 경우 확대 및 영역이 최소화됩니다.
- 분할 시 R*-tree는 둘레를 기준으로 분할 축을 선택한 다음 겹침을 최소화하는 토폴로지 분할을 구현합니다.
- 향상된 분할 전략 외에도 R*-트리는 B-트리 균형의 개념에서 영감을 받아 개체와 하위 트리를 트리에 다시 삽입하여 분할을 건너뛰려고 합니다.
따라서 최악의 쿼리 및 삭제 복잡성은 R-Tree와 유사합니다. R*-트리에 대한 삽입 전략은 R-트리의 선형 분할 전략(O(M))보다 O(M log M)이 더 복잡하지만 2차 분할 전략(O(M