I suspect that thinking in trie terms is the way to go, where each node chooses its preferred representation.
The top level should usually use a grid, though uniform-density children can also use one. The grid scale should be chosen to maximize low-density children while minimizing empty children.
For low-density children, just store an unsorted bunch of items, or maybe sort them on just one axis (preferably the outermost axis used for rendering). If your outer level is actually uniform, all of its children will be this (or empty).
For high-density children, use a quadtree/octree ... or just treat them as opaque objects to be handled recursively. These still suck for all the memory-walking they do, but since you've handled the outer part using the grid, the overhead is smaller. These can do "nearby" queries if your implementation is good, but many implementations suck. Making them mutable just means you need to either implement rebalancing or just stick to fixed planes.
Comments
I suspect that thinking in trie terms is the way to go, where each node chooses its preferred representation.
The top level should usually use a grid, though uniform-density children can also use one. The grid scale should be chosen to maximize low-density children while minimizing empty children.
For low-density children, just store an unsorted bunch of items, or maybe sort them on just one axis (preferably the outermost axis used for rendering). If your outer level is actually uniform, all of its children will be this (or empty).
For high-density children, use a quadtree/octree ... or just treat them as opaque objects to be handled recursively. These still suck for all the memory-walking they do, but since you've handled the outer part using the grid, the overhead is smaller. These can do "nearby" queries if your implementation is good, but many implementations suck. Making them mutable just means you need to either implement rebalancing or just stick to fixed planes.