PostGIS Cookbook - Second Edition

How it works...

What makes this magic possible is that PostGIS uses an R-tree index. This means that the index itself is sorted hierarchically based on spatial information. As demonstrated, we can leverage the structure of the index in sorting distances from a given arbitrary location, and thus use the index to directly return the sorted records. This means that the structure of the spatial index itself helps us answer such fundamental questions quickly and inexpensively.

More information about KNN and R-tree can be found at http://workshops.boundlessgeo.com/postgis-intro/knn.html and https://en.wikipedia.org/wiki/R-tree.