| Some variant on the ternary search tree might be helpful. Here is a nice introduction.
Otherwise, you could consider having every node store a hash table of records with the same key, the hash function being computed via the secondary key.
(I assume you have some sort of secondary key that you use to pick out a unique record, e.g. first name when disambiguating "smith", otherwise you do need to cycle through every record anyway, because your definition of a 'target' record becomes unclear).
A third option is to incorporate your secondary key into the <=> function, so that every record does get a unique key when passed to the binary tree's comparator. Could be something as simple as the standard "if (key1a == key1b) return (key2a <=> key2b)".
HTH
zem | 
