2D cache-friendly data structures and space-fillin

问题:

I've read that space-filling curves such as the Peano curve are useful for maintaining cache-friendly data structures in a linear address space, since they maintain physical spatial locality.

However, I'm not sure how to actually use them. Do any of these curves have formulas for quickly translating a linear address into (x,y) coordinates and vice-versa? Otherwise, how do I determine where in memory to look when looking up a certain pair of coordinates? An example would be very helpful.

回答1:

As stated in the comment translate the co-ordinate to a binary and interleave it. Then treat it a base-4 number if you want a quadkey.