This discussion is incomplete without mentioning space-filling curves. These curves map the data into a 1-d space and then you can use
any conventional search structure -- sorted array with binary search, balanced tree, skiplist, b-tree, etc. This allows you great flexibility, including the use of 3rd party libraries of data structures.
(A quadtree is basically the z-order space-filling curve combined with a trie of degree 4. Octtree -- degree 8.)
This approach also handles non-point data very cleanly. A non-point object gives rise to multiple index entries. (You can tune the number of index entries quite easily.)
Space-filling curves also leads to a very nice kNN algorithm: To find the k nearest neighbors of p, first search the index for p. Find k neighbors along the space-filling curve, (these are adjacent in the index), and of these, pick the point q maximizing distance(p, q). All k nearest neighbors of p must be in a circle centered at p with radius distance(p, q). Now search your index again using this circle and pick the k points n1, ..., nk minimizing distance(p, ni).
(A quadtree is basically the z-order space-filling curve combined with a trie of degree 4. Octtree -- degree 8.)
This approach also handles non-point data very cleanly. A non-point object gives rise to multiple index entries. (You can tune the number of index entries quite easily.)
Space-filling curves also leads to a very nice kNN algorithm: To find the k nearest neighbors of p, first search the index for p. Find k neighbors along the space-filling curve, (these are adjacent in the index), and of these, pick the point q maximizing distance(p, q). All k nearest neighbors of p must be in a circle centered at p with radius distance(p, q). Now search your index again using this circle and pick the k points n1, ..., nk minimizing distance(p, ni).