There are many metric-based data structures, such as M-tree, Vantage Point Tree, etc. They all suffer from the same major problem: they all rely on triangle inequality to speed up search by pruning impossible paths. But this doesn't ever result in an easily measurable complexity guarantee (like say, the guaranteed log(N) of a balanced binary search tree), so it's very common for certain datasets to result in severe performance degradation, particularly when the data is high-dimensional.
Metric-based data structures face the peculiar problem that the identity of each data point itself is not an actual "key", in the way that a data point in a hash-table or binary tree is a key. Rather, each data point in a metric tree is only "indexed" with relation to it's distance from all other keys. This makes it hard to get easily measured performance guarantees.
This issue also gets mentioned in the sklearn documentation [0]. The "curse of dimensionality" explains how high dimensional data tends to be close together, making efficient indexing on a distance metric difficult.
I feel like the poster-child for the frequency illusion. There was an article on 538 a few weeks ago that caught my interest which used cosine similarity (a non-metric distance function). I dove in, and started wondering if there were any ways to find nearest neighbors using cosine similarity efficiently. A week later, Facebook's Faiss implements something of a general purpose toolkit for indexing metric and not metric spaces to minimize storage. And now this. It's like the world is trying to tell me something!
EDIT: Deleted calculation about approximating arccos(z) <= arccos(x) + arccos(y) by cos(arccos(z)) <= cos(arccos(x) + arccos(y)) <= xy - (1-x^2)(1-y^2), completely disregarding that cos is a decreasing function in the relevant interval.
Bingo! We tested BK trees and found them to break down on lots of data sets. The search speedup never overcame the additional cost of building the trees (although these were one-off sets, a search heavy workload could definitely benefit from them).
An ordered binary tree still can fail to N if you allow duplicates.
(AFAICT: Most of these trees have a "typical" case search time of some root of N based on dimensionality. The easiest way to visualize this is to consider a walk from the perimeter to a cell in Voroni space, and how many cells that will search.)
Metric-based data structures face the peculiar problem that the identity of each data point itself is not an actual "key", in the way that a data point in a hash-table or binary tree is a key. Rather, each data point in a metric tree is only "indexed" with relation to it's distance from all other keys. This makes it hard to get easily measured performance guarantees.