Хэш-таблица read/write за O(1), хочется такую идеальную структуру. Но в реальности этому не бывать, ибо реаллокация, а главное предотвращение коллизий в виде цепочек. Так что лучше всего древовидные структуры данных, понимаю что на каждый узел приходится дёргать диспетчер памяти, но с другой стороны масштабировать намного проще.