Discussion: Flat representation of R-tree

(Sorry for abusing the issue tracker for what is actually a discussion/request for comments.)

I am working on a flat representation of an R-tree over at https://github.com/adamreichold/sif-rtree. This enables using memory maps as the backing store without going through the complications of the as yet unstable allocator API. It does have the significant downside of practically forcing the data structure to be immutable as far as I can see though.

The performance of spatial queries seems to be equal to or within a few percent of the rstar crate itself. (It can be brought to exactly the same level by using unchecked indexing but that would force unsafe code usage and validation issues with deserialized data structures.) The construction builds exactly the same trees as our RTree::bulk_load function here.

The two observations I made while working on that which I would like to discuss here are:

[ ] I wonder whether the two Iterator impls used in the bulk_load are actually helping as I think a straight-forward implementation using loops might be easier to understand. (Both iterators are immediately consumed after construction via collect and extend respectively.)
[ ] I think that we could provide an immutable flat-representation variant of RTree in this crate which would directly integrate with the existing trait infrastructure. I do wonder this is seen as useful though due to somewhat specialized scope of such a data structure. (I think we could actually implement this as a conversion from RTree to e.g. FlatRTree to avoid reimplementing the construction logic. Theoretically, we could also use internal traits to re-use the query logic but I am not sure if the result would be maintainable.)

georust / rstar

Discussion: Flat representation of R-tree #132