Understanding usage of quadtree to store location data

Question

I was reading this article, which talks about storing location-based information. The author says that while Latitude and Longitude info for the locations can be stored in a SQL database, retrieving and searching through that information using SQL queries can be expensive, even with Latitude and Longitude mapped to their own indexes in the DB. So far so good.

To address this, the author divides the map into a 4 block grid, where each block is further divided into more blocks in such a fashion that each block contains some threshold number of locations. This is represented via a Quadtree. This will indeed make the search simpler, but what I am not clear is a couple of things:

1. Is the grid i.e. Quadtree a separate table in the SQL database, or is it simply a data-structure in the application-servers memory? (Given the grid is used in the sample query that the author shows later, perhaps it's a table in the same SQL database?:

Select * from Places where Latitude between X-D and X+D and Longitude 
between Y-D and Y+D and GridID in (GridID, GridID1, GridID2, …, GridID8)

2. If so, then how can a Quadtree be stored as a SQL table? Or is it not a table but a type of index that databases use (eg. B-Trees). But then how is it included in the query?
3. If neither, then where exactly is Quadtree used in this system design?
4. A little different question, one way the Quadtrees can be represented is using Hilbert Curves. Where does this fit into the picture?

Answer 1

That is a few questions. Its generally best to ask one, and if you want to ask another, to ask it seperately.

But to the answers...

1. Its a data structure, but you can map each leaf to an id, and store that id against each co-ordinate in the database. When you've decided which leaves you want to investigate, its simple to list all co-ordinates with the given leaf ids. Similarly you can store the branches like (branch id, child id 1, child id 2, child id 3, child id 4, vertical divide, horizontal divide).

2. Some database (like geo databases) do indeed provide this kind of store for free, just identify the co-ordinate columns. Some database (like most relational) do not have this support baked in.

3. Usually it is used to speed up queries that are looking for similarity across multiple dimensions, they don't have to be spatial, you just need a way of calculating how far along each dimension potentially relevant records live.

4. Multi-Dimensional Arrays are usually laid out row or column major. This leads to all cells in a row or column respectively being next to each other but very far away from the column or row cells that are next to them on the other dimension. Hilbert curves are a way of laying out cells so that dimensionally close cells are also close in memory. This can provide dramatic speed ups when most of the data you want is in those nearby cells.