Building and balancing a k-d tree is not free, either. I suspect that the GP's approach is roughly the same in terms of theoretical complexity, but effectively trades memory for smaller constants and a chance to trip over edge cases like dense groups of points.
Sounds like GeoHash lookup which is actually pretty robust if you have a good data structure for indexing. For example: https://redis.io/commands/georadius
