Best spatial indexing tree ?

[jolan]

I'm looking for the best way to acces an object, which is basicaly an box, given an XYZ position.

I have thousands of non-overlapping boxes per grid, I tried G3D's AABSPTree , played with several balance() parameters, but I dont get one box per leaf. Instead I get a node with several, sometime hundreds of boxes. I think AABSPTree is not the right class to use here.

I'm looking for fast search, insertion time is not that important.

I think perhaps R-Tree would do the job...

what do you think ? do you know a better option ? do you know a good c++ GPL implementation ?