This data structure will have frequent insertions and lookups. In addition, it needs to be able to return a null pointer if it is indexed by a 3D point that has not had an insertion associated with it. Up to millions of pointers will be inserted into this structure.
At first glance some form of associative array seems appropriate, but the 3D component complicates things. So I'm not sure if i need to use spatial partitioning with this or not.
If its any help, the ranges for the x and y components are integers from 1 to 100,000+. For the z component it will range from 1 to 1,000+. The points that index this structure will be near each other. A distance of more than 1000 between any points used here is unlikely.
Memory usage and speed are both important in this case.
If there isn't a clear winner for a data structure to use, feel free to name several candidates.