R-Tree 및 Quadtree 비교

Question

지형 공간 데이터에 대해 R-Tree와 Quadtree를 비교하고 싶습니다. 저기서 문학이있는 동안 나는 진짜 기본 비교를 다루는 문서를 찾기 위해 애 쓰고 있습니다. 그래서 나는이 질문을하기로 결정했다.

제 생각에는 R-Tree가 균형을 이루는 이점이 있고 트리에 빈 잎이 없습니다. 단점으로 삽입 또는 삭제와 같은 기본 작업은 전체 색인을 재구성 할 수 있습니다.

Quadtree는 반대쪽이며 균형이 맞지 않고 잎이 비어 있지만 재구성 할 필요가 없습니다.

그래서 나는 R-Tree가 최소한의 메모리 만 필요로하고 최소 높이 때문에 검색하는 것이 더 빠르다고 말합니다. 많은 업데이트 작업이있을 때 quadtree가 더 좋지만 결과 트리가 언밸런스 될 수 있습니다.

의견이 맞습니까? 이 주제를 다루는 훌륭한 문서가 있습니까?

안녕히 Wiedersehen, 앙드레

Answer 1

는 "전체 인덱스 구조 조정". 아니요. R- 트리 재구성은 "전체"색인이 아닌 단일 경로로 제한됩니다. 실제로 B- 트리와 유사하게 작동합니다.

두 가지를 모두 구현하고 벤치 마크를 직접 수행하여 실적을 실제로 파악하는 것이 좋습니다. 이론을 사용하지 마십시오.

변경 빈도가 높은 균일하게 분포 된 데이터에서 4 분법이 더 잘 작동합니다. 디스크에서 R-tree는 분명한 장점이 있습니다.

Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data

약간의 차이 : 여기

Answer 2

는 쿼드 트리와 R 나무의 꽤 좋은 비교가 종이의

쿼드 트리의 성능을 최적화하기 위해 적절한 타일링 레벨을 선택하여 미세 조정이 필요

• . R-Trees에는 특정 튜닝이 필요하지 않습니다.
• Quadtree는 기존 B- 트리 위에 구현할 수 있습니다. R-Tree -cannot
• 쿼드 트리 색인은 R-tree보다 빠르게 생성됩니다.
• R-trees는 가장 가까운 이웃 쿼리에 대해 Quadtree보다 훨씬 빠릅니다.
• R-나무 "내부"와 같은, 창 쿼리에 대한 쿼드 트리보다 훨씬 더 빨리, "포함", "포함"등 "전체 인덱스 구조 조정"