k nearest neighbors query in 3-space

I have a data set stored in database table that includes a position in 3-space. I need to retrieve the k nearest neighbors in an efficient manner. My datastore does not include native spacial indexes for 3 dimensions. How do I simulate a spacial index in the client.

This question might be rephrased, How can KD-Trees be implemented for date stored in a database?

(开发者_如何学运维if it makes a difference, the actual databases used are MongoDB and Redis)

Maybe that could interest you:

http://en.wikipedia.org/wiki/Octree

I suppose it could play nicely with algorithms such as Map-Reduce.