Вы хотите Древовидную Карту;в основном вам просто нужно дерево, в котором узлы сортируются динамически («самоуравновешенными») по ключам, а ваши объекты свисают с каждого узла с соответствующим ключом.
Если вы хотите «оптимальную» структуру данных, это полностью зависит от распределения шаблонов входов, которые вы ожидаете.Хорошая вещь в самобалансирующемся дереве заключается в том, что вам не нужно особо заботиться о структуре входов.Если вы действительно хотите, чтобы наилучшее предположение было как можно ближе к оптимальному, насколько нам известно, и вы не очень много знаете о конкретных последовательностях запросов, вы можете использовать http://en.wikipedia.org/wiki/Tango_tree, равное O(log(log(N))-конкурентный.Это растет настолько медленно, что для всех практических целей у вас есть что-то, что работает не хуже чем эффективный постоянный фактор из наилучшей возможной структуры данных, которую вы могли бы выбрать.
Однако это несколько шероховато реализовать, вы можетелучше использовать библиотеку для самобалансирующегося дерева.
Python: https://github.com/pgrafov/python-avl-tree/
Java: если вы просто Java, просто используйте TreeMap (красно-черное дерево на основе) и игнорировать детали реализации.Большинство языков имеют схожие структуры данных в своих стандартных библиотеках.