2 ms·
I noticed you want to do geolocation. Let's put that aside for now, just looking at key/value. 1. You need to store all your data in "pages". These are fixed-l
by zamalek 13y ago
I noticed you want to do geolocation. Let's put that aside for now, just looking at key/value.
1. You need to store all your data in "pages". These are fixed-length blocks (that can be chained together).
2. Use a classical "dictionary" data structure to store your index (most use B-Tree), but you place that structure on-disk instead of in-memory. Your index basically points a key to the index of the first page that contains the value.
3. You may need to store other types of data in the file, such as the free page list.
As for geo-location, B-Tree fits nicely here.
1. Intelligently lay out your B-Tree so that nearby nodes are typically within the same node-family-system. Include information about the distance spanned by descendants in the tree (you probably want to use Manhatten distance).
2. When trying to do "near" queries, first locate the node you are interested in and then start traversing up the parents until you find the ancestor that encompasses the distance you are looking for.
3. Grab all the descendants of that ancestor and re-check them against the distance.