Обстоятельный разбор Эндрю Галланта показывает, как конечные автоматы хранят упорядоченные множества и словари. Строка становится последовательностью переходов, а общие состояния используются повторно. Проверка ключа требует не больше шагов, чем в нём символов, независимо от размера набора.
Далее библиотека
fst на Rust и опыты. Индекс 16 млн заголовков Wikipedia объёмом 384 МБ построился за 18,3 секунды и занял 157 МБ. Поиск по регулярному выражению занял 0,023 секунды, нечёткий поиск с двумя правками: 0,094 секунды. Финал: более 1,6 млрд URL из Common Crawl объёмом 134 ГБ.В лонгриде Эндрю Галланта разобраны границы: нужен быстрый доступ к произвольному участку файла, а структура не универсальна. Читать разработчикам поиска и словарей, чтобы оценить вариант индекса.