[postgis-users] looking for some perf data

Martin Davis mbdavis at refractions.net
Tue Nov 21 09:12:31 PST 2006

First of all, you need to be more specific.  The performance of an index 
is related to the kinds of queries you are making on it.   If you are 
making  a simple equality query, then a B-tree on the (x,y) pair is 
probably fine.  But if you're wanting to do range searches in two 
dimensions, a B-tree does not support this kind of query, and hence 
performance will be slow compared to an access method which does support 
this (e.g. R-tree, quad-tree, etc etc).

I don't know of any reference which has a "hard verifiable" comparison 
with a simple B-tree for range queries.  I suspect this is because the 
performance difference is so obviously bad for B-trees that researchers 
haven't bothered to document it. 

You might try looking at two of the books by Hanan Samet:

Foundations of Multidimensional and Metric Data Structures
The Design and Analysis of Spatial Data Structures

You could also try the original R-tree papers, or a survey entitled 
"R-Trees are everywhere".  Also a paper entitled "Multidimensional 
Access Methods" by Gaede et al.

raphael Jacquot wrote:
> hi there
> I'm looking for some hard verifiable proof that using r-tree based 
> geometry indexes is better than using 2 columns and a btree index on 
> it, performance wise.
> has there any study done on that ?
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users

Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

More information about the postgis-users mailing list