The SBN spatial index is some sort of binary range tree. I've been pretty close in reproducing the indexing by using a tree method, where the input bounding box is sorted through a tree structure by alternately comparing min/max coordinate pair against each division.
However, it's always seemed like there would be some faster way to sort features based on looking at individual bits in the binary representation of the coordinate value.
For example, let's say we have a 4 bit index space ( a 16 x 16 grid). We're trying to bin a bounding box with a max coordinate of (11,9) and min of (8,7).
Using the tree method, we would first look at the first split which occurs at an x of 8. Since xmin is equal to or greater than 8 that would sort the bounding box into the right bin. Next we would look at a y value of 8 for the second division. In this case the y value splits the bounding box, so the box cannot be sorted further and remains in the third bin.
We can also do this bitwise. What we first do is reverse the bin