R* 트리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

R* 트리는 다차원의 공간 데이터를 저장하는 R 트리의 최적화된 자료 구조이다. R* 트리는 R 트리에 비해 빠른 검색 속도를 제공하지만, 업데이트 속도는 매우 느리다. 비록 R 트리와 이름은 다르지만, 내부 자료 구조체는 모두 동일하며 다만 노드 분리 알고리즘 (node split)과 오버플로(overflow)를 해결하는 방법만이 다르다.

R 트리와의 차이점[편집]

최소 경계 사각형(MBR, Minimum Bounding Rectangle)의 넓이와 다른 MBR과의 겹칩(overlap) 영역의 최소화는 서로 상충하는 경우가 있다. R 트리는 MBR의 넓이만을 최소화하고자 시도한 반면 R* 트리는 겹침 영역 또한 줄이고자 시도한다. 즉, R* 트리는 꽉찬 노드가 분리되어야 하는 경우에 그 노드의 자식 노드들 중 일부를 루트 노드에 다시 삽입하는 강요된 재삽입 (forced reinsertion)을 시도하여 노드의 겹침을 최소화하고자 한다.

참고 문헌[편집]

바깥 고리[편집]