k nearest neighbors query in 3-space

Question

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)