Rtree

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

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

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

See also

• Tree

Favorite site

• Wikipedia (en) R-Tree에 대한 설명
• R-Trees 샘플 소스코드 ¹
• An Analysis of Minecraft-like Engines | 0 FPS (R-Tree에 대한 내용)

References