Du must eben ausgeglichene/ausgleichende Bäume (aka AVL-Bäume, Red-Black-Trees) verwenden. Die entarten nicht.
Wieso verwendest Du nicht
a) eine TStringlist (oder schneller: THashedStringlist in IniFiles)
b) eine Hashmap
c) eine Skiplist
Bis 10.000 Einträgen reicht a) (Variante 'THashedStringlist'), danach b) oder c).
Im Anhang ein AVL-
Unit