메뉴

문서정보

Rtree

R-Tree는 지리 좌표, 직사각형, 폴리곤과 같은 다차원 정보를 색인하기 위해서 사용하는 트리 데이터 구조다. R-Tree는 1984년 Antonin Guttman이 제안 했으며, 이론은 실제 상황에서도 중요하게 사용하고 있다. R-Tree의 일반적인 사용 용도는 해안선, 건물, 호수, 도로 등을 포함한 지도내에서 특정 객체의 위치를 신속하게 찾는 것이다. "현재 위치에서 2km 이내의 식당 찾기", "가장 가까운 주유소 찾기"등이 전형적인 예다.

아이디어

핵심 아이디어는 인접한 오브젝트를 그룹화하고 트리의 다음 상위 레벨에서 최소 경계 사각형(Minimum Bounding Rectangle)으로 오브젝트를 표현하는 것이다. 애초에 R-Tree에서 R은 Rectangle를 의미한다.

 R-Tree

 Spatial Database

참고