R* 트리
위키백과 ― 우리 모두의 백과사전.
R* 트리는 다차원의 공간 데이타를 저장하는 R 트리의 최적화된 자료구조이다. R* 트리는 R 트리에 비해 빠른 검색 속도를 제공하나, 업데이트 속도는 매우 느리다. 비록 R 트리와 이름을 달리하나, 내부 자료 구조체는 모두 동일하며 다만 노드 분리 알고리즘 (node split)과 오버플로우(overflow)를 해결하는 방법만이 다르다.
[편집] R 트리와의 차이점
최소 경계 사각형(MBR, Minimum Bounding Rectangle)의 넓이와 다른 MBR과의 겹칩(overlap) 영역의 최소화는 서로 상충하는 경우가 있다. R 트리는 MBR의 넓이만을 최소화하고자 시도한 반면 R* 트리는 겹침 영역 또한 줄이고자 시도한다. 즉, R* 트리는 꽉찬 노드가 분리되어야 하는 경우에 그 노드의 자식 노드들 중 일부를 루트 노드에 다시 삽입하는 강요된 재삽입 (forced reinsertion)을 시도하여 노드의 겹침을 최소화하고자 한다.
