R+ 트리
R+ treeR+ 트리는 위치(종종 (x, y) 좌표)와 지표면 상의 위치를 사용하여 데이터를 검색하는 방법입니다.1개의 번호로 검색하는 것은 해결된 문제입니다.두 개 이상의 번호로 검색하는 것과 x와 y의 양쪽 방향으로 가까운 위치를 확인하는 것은 보다 교묘한 알고리즘이 필요합니다.
기본적으로 R+ 트리는 공간 정보를 인덱싱하기 위해 사용되는 R 트리의 변형인 트리 데이터 구조입니다.
R+ 트리와 R 트리의 차이
R+ 트리는 R-tree와 kd-tree를 절충한 것입니다.필요에 따라 오브젝트를 여러 리프에 삽입함으로써 내부 노드의 중복을 방지합니다.커버리지란 관련된 모든 직사각형을 커버하는 전체 영역입니다.오버랩은 2개 이상의 [1]노드에 포함되는 전체 영역입니다.커버리지를 최소한으로 억제하면, R-트리의 노드에 의해서 커버되는 「데드 스페이스」(빈 영역)의 양을 줄일 수 있습니다.중복이 최소화되면 리프로의 검색 경로 세트가 줄어듭니다(최소한의 커버리지보다 액세스 시간에 더 중요).효율적인 검색을 위해서는 최소한의 커버리지와 중복이 필요합니다.
R+ 트리는 R 트리와는 다릅니다.노드는 적어도 절반이 채워지는 것을 보증하지 않으며 내부 노드의 엔트리가 중복되지 않으며 오브젝트 ID가 여러 리프 노드에 저장될 수 있습니다.
이점
노드가 서로 겹치지 않기 때문에 모든 공간 영역이 최대 1개의 노드로 커버되므로 포인트 쿼리 성능이 향상됩니다.단일 경로를 따르며 R-트리를 사용하는 경우보다 적은 수의 노드가 방문됩니다.
단점들
직사각형은 중복되므로 R+ 트리는 동일한 데이터 세트에 구축된 R 트리보다 클 수 있습니다.R+ 트리의 구축과 유지보수는 R 트리 및 기타 변형 R 트리의 구축과 유지보수에 비해 복잡합니다.
메모들
- ^ Härder, Rahm, Theo, Erhard (2007). Datenbanksysteme (2., überarb. Aufl. ed.). Berlin [etc.]: Gardners Books. pp. 285, 286. ISBN 978-3-540-42133-7.
