Here I would like to share a data structure that I use for navigation in 3D space of a game. In essence it is a binary tree build out of linked lists.
It attempts to combine best of the two worlds 1.Linked Lists and 2.Binary Trees. So you can find a specific item in log(n) time or explore near by items in n time. This is very useful in a game where you always need to know what is near the camera, but once in a while you have to find a specific object. Below you can see the basic schema of the structure:
This pictures only one single dimension. In a game I use three dimensions but the structure allows N dimensions.