Reducing search iteration over millions of data
You are on the right track. In an interview situation, this should be a good answer.  Another answer would be to pre-calculate list of 20 stores in ETL (or CRUD services or DB triggers) and store list of N closest stores in master-detail table.

I have implemented these two solutions in projects :


In database, create indices on lat and lon columns AND add a where clause with a bounding box. 

SELECT distance_function(cur_lat,cur_lon,lat,lon) as distance

WHERE (lat between cur_lat -1 and cur_lat +1) AND (lon between cur_lon
      -1 and cur_lon +1)

(+Order by, top 20 rows clause depending on SQL dialect)


This solution cuts search space to a bounding box. This operation in log(n) in time complexity (due to B+ tree indices in DB)

For 100 million rows, results should be available in less than 1 ms. 

Choice of +-1 four bounding box is arbitrary in this example. In reality, you will have to store this box with each row (1000s of stores in 1 mile in NYC, London etc; 1 store in 100 miles in other locations)


Implement QuadTree https://en.wikipedia.org/wiki/Quadtree . In this context it is similar to your solution but takes care of extreme cases where density of stores varies across geographical regions.