Hi! I just wrote a small package to perform spatial queries on an STR (sort tile recursive) tree that should work for all GeoInterface geometries supporting extent: GISTRtree. Currently the implementation is a bit brute-forced, and so far only queries for intersection work. But I’m using it with 6 million polygons and the queries run in less than a millisecond, depending on the extent. I guess this could be useful for others, too, so the registration is pending 
Edit: @Lilith rightfully started a discussion on the name of the package. Opinions are welcome! Other naming options could be SortTileRecursiveTree.jl (no plural, there is just a single one with that name), GeoInterfaceSTRTree.jl or similar…