title: How are the data structures which are created for making searches fast in a system design actually stored?
body: <p>Suppose I am designing a system for restaurant recommendations like Yelp. Some of the basic things I need to implement would be like:</p>
  
  <ol>
  <li>Users should be able to add/delete/update Places.</li>
  <li>Given their location (longitude/latitude), users should be able to find all nearby places within a given radius.</li>
  <li>Users should be able to add feedback/review about a place. The feedback can have pictures, text, and a rating.</li>
  </ol>
  
  <p>From the storage perspective, I decide to have fields like LocationId for each place, Latitude, Longitude, Name, Description and Rating. Assuming around 8 bytes for each LocationId and Latitudes and Longitudes, if I design the system for 500 million locations, I come up with ~ 500 x 10^6 MB of storage requirement. So far, so good.</p>
  
  <p>For getting the location query result faster, I decide to use Quadtree as shown in the image consisting of grids, where each grid consists of 500 locations. If a grid exceeds 500 locations, it is split to form another grid, with max grids at each level to be 4. Lets say I have created the Quadtree as well. I am not sure that after creating the Quatree, <strong>where</strong> and <strong>how</strong> are we storing this tree?</p>
  
  <p><a href="https://i.stack.imgur.com/cCfxE.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/cCfxE.png" alt="QuadTree created for storing data for Yelp type of system design"></a></p>
  
  <p>One possible way that I could think of is that I would serialize the Quadtree and on some similar lines like we serialize an n-ary tree and store it in a text file. Considering that I keep LocationId, Longitude and Latitude details in the nodes of my tree, I would need to store 24kb of data for every location if each field is of 8 bytes. For 500 such location, the total memory requirement for my tree would be ~24 * 500M = 12 GB. Whenever my machine restart, I would just de-serialize the stored tree and perform query operations as requested by server. </p>
  
  <p>One problem I see with this approach is that I would need to update my file every time after some regular intervals in order to keep the latest information about locations.</p>
  
  <p>Can anyone suggest in what other ways can store the QuadTree and where will I store it? I believe there are much better ways to store the QuadTree as I suggested above.</p>