@TJ_Singh, yes we do need to search the neighboring grids. This all depends upon the searching radius and the grid size. Uber design is based on Yelp design, please see Yelp design for most of the discussion around your questions:
What could be a reasonable grid size? Grid size could be equal to the distance we would like to query since we also want to reduce the number of grids. If the grid size is equal to the distance we want to query, then we only need to search within the grid which contains the given location and neighboring eight grids.
Please see Yelp design for answer to both of your questions.
@Thape_Samthree, assuming you know how to iterate a doubly linked list, let’s discuss how will we build the doubly linked list and how to break a node into four nodes.
We can easily find the next leaf node of a given leaf node through parent pointer, here is some relevent text from Yelp design:
We can keep a pointer in each node to access its parent, and since each parent node has pointers to all of its children, we can easily find siblings of a node.
We can keep searching the next leaf node by going up. Since each node has pointers to its next and previous leaf node, so while breaking it into four nodes, we can easily connect first and the fourth node with the previous and next leaf node respectively.