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.