Зависит от того, сколько это "достаточно много" и сколько есть оперативной памяти под эту задачу (ПК, смартфон, эмбедед разработка?).
Если память позволяет, то самым быстрым будет два бинарных дерева (либо два сортированных массива-списка, но тогда после добавления элемента придётся пересортировывать или искать место вставки).
Если A и Value сами по себе большие и/или сложные объекты, которые нельзя продублировать, то можно сделать две индексных таблицы, ссылающихся на оригинальные данные.
Самое быстрое - два отсортированных массива, в каждом из которых и А и Value.
Самое удобное, но чуточку менее быстрое - два бинарных дерева.
