Postgresql – Does PostgreSQL/PostGIS use R-Tree or R*-Tree

database-internalsindexpostgispostgresqlspatial

PostgreSQL and PostGIS offer to create indexes over GiST with pretty much the same code. On 2D items, "This gives R-tree behavior" is what it says in the PostgreSQL source comments. However, it is a bit different than the original R-Tree, an observation being that the split technique is the Korotkov split. Furthermore, on PostGIS source, there are comments suggesting R*-tree ideas. I am somewhat unsure…

So my question is: is the "R-Tree behaviour" offered in PostgreSQL the vanilla R-Tree? If not, what are some of the differences? Is this data loaded insert by insert or is there a bulk loading mechanism in place?

Best Answer

I'm not sure what is the vanilla R-Tree but there is internal citations inside the source file you linked. Also, the R-Tree inside of PostGIS is directly copied from PostgreSQL with these minor modifications (as in the FAQ),

Why aren't PostgreSQL R-Tree indexes supported?

Early versions of PostGIS used the PostgreSQL R-Tree indexes. However, PostgreSQL R-Trees have been completely discarded since version 0.6, and spatial indexing is provided with an R-Tree-over-GiST scheme.

Our tests have shown search speed for native R-Tree and GiST to be comparable. Native PostgreSQL R-Trees have two limitations which make them undesirable for use with GIS features (note that these limitations are due to the current PostgreSQL native R-Tree implementation, not the R-Tree concept in general):

  • R-Tree indexes in PostgreSQL cannot handle features which are larger than 8K in size. GiST indexes can, using the "lossy" trick of substituting the bounding box for the feature itself.

  • R-Tree indexes in PostgreSQL are not "null safe", so building an index on a geometry column which contains null geometries will fail. [GiST indexes are null-safe]

Related Question