Since you mentioned SIMD acceleration, did you look at things like QBVH[1]? I mean it would be kinda like a B-tree I suppose but with the min/max stuff.
Again not put a lot of though into it.
Sounds like a fun challenge though.
It might be you want to use a binary partitioning algorithm or similar for just a few levels, and then have the leaf nodes be N spans in a (sorted) list, where N is somewhat large. Then you can have some fast loop to mow through the leaf spans.