Thanks! I did try a 1-dimension R-tree but the performance tended to be much worse than an ordered map.

Priority trees could be really interesting. I did consider them early on but wasn't sure how well they'd apply here, so I'll take another look.