Hilbert R-tree for spatial Index

[Paul Ramsey]

This would take a great deal of testing at this point, as our index implementations have been getting quite close to optimal (famous last words) so that improvments that appear to bear fruit in one use case damage performance in others. 

Just straight comparisons of the geos/jts strtree and a packed hilbert rtree have not shown there to be any huge wins, except to some extent for build speed, but with a penalty in query performance on the hilbert tree.

The main thing is that any change to the core rtree has to not degrade query performance while also not degrading index build performance. The last time we got into this work was when the GIST pre-sort code was added, and it was a tight balancing act to avoid making query worse while improving build time.

What is your plan, to try and implement a new split algorithm, or something else (also bear in mind that many potential index improvements are not available to us due to the restrictions that using the GIST API layer on top of our code).

P

> On Jun 26, 2025, at 9:19 AM, Vedic Chawla <chawlavedic8 at gmail.com> wrote:
> 
> Hi PostGIS community,
> 
> I was doing a feasibility study/survey for optimal Geospatial Index when I came across this concept. 
> 
> Currently, POSTGIS uses R-tree on top of GiST to implement Geospatial Index. and there has been this GSOC Task[1] to implement Z sort to make this indexing faster, This should also have the effect of Increasing MSU, and making query faster as this would benefit from the same concept as Packed Hilbert R tree[2] used by FlatGeoBuf[3]. I would suggest that we use Hilbert ordering instead of Z sort, as PostGIS has since switched its sort to Hilbert and it is also used by flatgeobuf.
> We can probably do both too.
> 
> Extending upon that we can also implement Dynamic Hilbert R-Tree[4] if we store Largest Hilbert Value for each of the Nodes. 
> 
> I would love to know your views on this!
> Regards
> Vedic
> 
> [1] : https://trac.osgeo.org/postgis/wiki/GoogleSummerCode2021
> [2] : https://en.wikipedia.org/wiki/Hilbert_R-tree#Packed_Hilbert_R-trees
> [3] : https://github.com/flatgeobuf/flatgeobuf?tab=readme-ov-file
> [4] : https://en.wikipedia.org/wiki/Hilbert_R-tree#Dynamic_Hilbert_R-trees

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20250626/feb7ed00/attachment.htm>