The data structures you are interested in are metric trees. That is, they support efficient searches in metric spaces. A metric space is formed by a set of objects and a distance function defined among them satisfying the triangle inequality. The goal is then, given a set of objects and a query element, to retrieve those objects close enough to the query.
Since search problems are literally everywhere in computer science, there is a huge amount of different metric trees. However, they can be divided at least into two groups: pivot-based and clustering based (and surely there are hybrids as well). A good survey is E. Chavez et al., Searching in Metric Spaces, 2001. See for example Chapter 5: Current Solutions to Metric Spaces, page 283.
There, in Table 1, Chavez et al. consider 16 different metric trees. They present space complexity, construction complexity, claimed query complexity and extra CPU query time for each (if known). If you don't care about the construction complexity too much, the query complexity for the BK-tree is $O(n^\alpha)$, where $0 < \alpha < 1$ depending on the range of the search and the structure of the space. Or if you don't have a huge number of elements, have a look at AESA (approximating eliminating search algorithm). It is unacceptedly slow to build and store for huge spaces ($O(n^2)$ time and space), but it has been shown experimentally to have $O(1)$ query time.
Chavez et al. also give a nice overview of the other trees, and naturally more references if any one in particular sparks your interest. In practice, the performance of different trees is often evaluated experimentally. This I think depends a lot on the structure of the space. Therefore it is hard to say which tree in particular would be the most efficient in your case. Nevertheless, I think it is a good idea to go with the easiest one first. If BK-trees are the easiest one to build, try them out first. If they don't satisfy your requirements, invest time (and perhaps programming time) into gathering more facts about your space that could help you make more informed decisions.