R 트리

R 트리B 트리와 비슷한데 다차원의 공간 데이터를 저장하는 색인이다. 이를테면, 지리학에서 R 트리는 "현재 위치에서 200km 이내의 모든 도시를 찾아라"와 같은 질의에 대해 빠르게 답을 줄 수 있다.

자료 구조는 공간을 최소 경계 사각형(MBR, Minimum Bounding Rectangle) 들로 분할하여 저장한다. MBR끼리 겹칠 수도 있고, 상위 레벨의 MBR 은 하위 레벨의 MBR들을 포함하는 계층적인 트리 구조이다. 각 노드는 미리 정의된 범위내에서 유동적인 개수의 자식 노드들의 정보 (MBR과 포인터)를 가진다.

R-트리의 저장과 삭제 알고리즘은 가까운 데이터들은 되도록 같은 단말 노드(leaf)에 두려고 한다. 그럼으로써 R 트리는 굳건하게 MBR을 유지할 수 있고, 검색 성능이 좋아지게 된다. 검색 알고리즘들(intersection, containment, nearest neighbor)이 이러한 MBR 들을 사용하여, 하위 레벨의 자식 노드를 검색할 것인지를 결정하기 때문이다.

변종 R-트리들

En otros idiomas
čeština: R-strom
Deutsch: R-Baum
English: R-tree
español: Árbol-R
עברית: עץ R
hrvatski: R-stablo
italiano: R-tree
日本語: R木
polski: R-drzewo
português: Árvores R
српски / srpski: Р-стабло
українська: R-дерево
中文: R树