The inverted file index: k-means splits the points into lists, one per centre; a search compares the query with the centres and measures only the points in the nprobe nearest lists. Fast, and now and then it misses the true nearest neighbour across a border.
This interactive visualization needs JavaScript.