Как быстро и эффективно внедрить серверный компонент для функции автозаполнения в поле ввода html?

Я пишу сервис для автозаполнения пользовательских запросов в главном окне поиска нашего веб-интерфейса, и их результаты отображаются в раскрывающемся списке с поддержкой ajax. Данные, к которым мы выполняем запросы, - это просто большая таблица концепций, о которых знает наша система, которые примерно соответствуют заголовкам страниц в Википедии. Для этого сервиса очевидно, что скорость имеет первостепенное значение, так как отзывчивость веб-страницы важна для взаимодействия с пользователем.

Текущая реализация просто загружает все концепции в память в отсортированном наборе и выполняет простой поиск в log (n) при нажатии клавиши пользователем. Затем набор хвостов используется для обеспечения дополнительных совпадений за пределами ближайшего совпадения. Проблема этого решения в том, что оно не масштабируется. В настоящее время он работает в соответствии с ограничением пространства кучи виртуальной машины (я установил -Xmx2g, что является максимальным значением, которое мы можем использовать на наших 32-битных машинах), и это не позволяет нам расширять нашу концептуальную таблицу или добавлять больше функциональности. Переключение на 64-битные виртуальные машины на компьютерах с большим объемом памяти не является немедленным вариантом.

Я не решался начать работу над решением на основе дисков, так как опасаюсь, что время поиска диска снизит производительность. Существуют ли возможные решения, которые позволят мне масштабироваться лучше, либо полностью в памяти, либо с помощью некоторых быстрых реализаций на диске?

Редактирование:

@Gandalf: Для нашего варианта использования важно, чтобы автозаполнение было всеобъемлющим, а не просто дополнительной помощью для пользователя. Что касается того, что мы заканчиваем, это список пар типа концепт. Например, возможными записями являются [(«Microsoft», «Компания-разработчик»), («Джефф Этвуд», «Программист»), («StackOverflow.com», «Веб-сайт»)]. Мы используем Lucene для полного поиска, когда пользователь выбирает элемент из списка автозаполнения, но я еще не уверен, что Lucene будет работать хорошо для самого автозаполнения.

@Glen: базы данных здесь не используются. Когда я говорю о таблице, я имею в виду структурированное представление моих данных.

@Jason Day: моя оригинальная реализация этой проблемы заключалась в использованииTrie, но объем памяти в этом случае был на самом деле хуже, чем отсортированный набор из-за необходимости большого количества ссылок на объекты. Я прочитаю на троичных поисковых деревьях, чтобы посмотреть, может ли это быть полезным.