R-Tree and Quadtree Comparison

Question

I want to compare the R-Tree and the Quadtree for geospatial data. While there is literature out there I struggle to find documents that cover real basic comparison. So I decided to ask this question.

In my opinion, the R-Tree has the advantage of being balanced and the tree has no empty leaves. As a disadvantage, the basic operation like insert or delete could result in restructering the whole index.

The Quadtree is the opposite, it is not balanced and has empty leaves, but it does not need to be restrctured.

So as a fazit from that I would say that the R-Tree does need less memory and is faster for searching because of the minimal height. The quadtree is better when there are many update-operations, but the resulting tree could be unbalanced.

Are these points correct in your opinion? Are there any good documents out there that cover this topic?

Auf Wiedersehen, Andre

Mishnah

"restructuring the whole index". No. Restructuring is restricted to a single path, not the "whole" index. Consider implementing both, and doing some benchmarks yourself, to really know how they perform. Don't only use theory. – Autointoxication

there are many different quad tree types, so get know most of them before trying to compare. further a slight variation in implementation may deliver much different execution time (e.g passimg a Rectangle Object vs passing 4 params x,y,width,height). – Stepheniestephens

Answer 1

"restructuring the whole index". No. Restructuring the R-tree is restricted to a single path, not the "whole" index. It works similar to the B-tree, actually.

Consider implementing both, and doing some benchmarks yourself, to really know how they perform. Don't only use theory.

On uniformly distributed data with a high change frequency, quadtrees will usually work better. On disk, the R-tree has clear advantages.

Autointoxication

Answer 2

Here's paper which has pretty nice comparison of QuadTrees and R Trees:

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

Some differences:

• Quadtrees require fine-tuning by choosing appropriate tiling level in order to optimize performance. No specific tuning is required for R-Trees.
• Quadtree can be implemented on top of existing B-tree. R-Tree -cannot
• Quadtree indexes are created faster than R-tree.
• R-trees are much faster than Quadtree for nearest neighbours queries.
• R-trees are substantially faster than Quadtree for window queries, like "inside", "contains", "covers" etc.

Appalachia