1

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)
  1. 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?
  2. If neither, then where exactly is Quadtree used in this system design?
  3. A little different question, one way the Quadtrees can be represented is using Hilbert Curves. Where does this fit into the picture?

1 Answer 1

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.

4
  • Thanks! So in this case, I can have a quadtree in memory and it can be mapped to a table in the database. In the case of a relational database, as you are saying, I can literally create a column-based table that defines the quadtree eg. id, node_type, parent, child_1, child_2, child_3, child_4, location_1, location_2,.....location_100, assuming a node stores 100 locations, that is what the author seems to be doing, right? (Also asked the questions together, as I felt they were related but point noted!)
    – Ufder
    Jun 3, 2021 at 23:10
  • You can do that though it is a little clunky, It makes it hard to write queries at the data layer to extract information. It probably best to normalise it somewhat. each child can contain its leaf id. Have a separate table storing inner nodes. This allows you to process children as a list (sometimes handy), and also by region based lookup (via the quad tree).
    – Kain0_0
    Jun 3, 2021 at 23:45
  • So all the leaves will be in a separate table, and inner nodes in a separate table? If I'm traversing from the root, that won't make a difference wrt search speed, right? I think I'm missing something!
    – Ufder
    Jun 3, 2021 at 23:49
  • Not really. The data simply has different shapes. But if you are worried, prototype both and measure.
    – Kain0_0
    Jun 4, 2021 at 3:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.