For making a Spatial DB that handles read/write depending on client's request location, we require:
- A way to measure distance between request
- Proximity: Find out closest nodes from a source.
Normal Iteration would require O(n) on all nodes. To perform operations like this efficiently, we divide 2D regions into segments
Quad Trees
A quad tree is a breakdown of 2D regions
Suppose we divide the whole world into 4 parts, and on regions where more traffic is met, nodes are places and these regions are divides into smaller sub-regions
A Quad tree is basically a 2D BST for O(log n ) searches in 2D space.
Problems: It can get quite skewed on one side and unbalanced, causing O(n) in worst case searches
Hilbert Curves - Space filling Curves
This is a way to convert a given 2-D space into a 1-D continuous line which allows simple and efficient geospatial queries\
The connections made between segments converts 2D -> 1D continous line.
Once objects are sorted into this 1D ordering, any 1D data structure can be used, such as binary search trees, B-trees and Hash Tables. for O(logn) searches
Also it is very scalable, as more orders are added, the variation of proximity between
2D -> 1D mapping changes very slightly