To roll your own: - Interleave the bits of the coordinates to form a "z-value". - Index the z value. - "X miles around a" is a circle. Approximate with a

To roll your own: - Interleave the bits of the coordinates to form a "z-value". - Index the z value. - "X miles around a" is a circle. Approximate with a bounding box if you'd like. - Generate 1-d search regions to yield a set of z ranges, and search the index using it. For more details, look up z-order, or see books by Hanan Samet. But a spatial index will probably do something reasonably close to this. One big thing to watch out for: The spatial index or z-value index should be clustering, so that the points you retrieve are packed tightly into pages. If the index is not clustering, your index lookup will be fast but you'll pay a lot of IO to bring in all the pages containing the qualifying points.