Указатель нужен (в книгах был, в конце).
Из него делаем "дерево": А, Б, В, ....АА, АБ, АВ,..., и с каждого потом: АБА, АББ,.... и т.д. по всем "цепочкам" букв, встречающихся в словах указателя.
При поиске - делаем спуск по "дереву" для каждого слова.
Чем больше слов поискового запроса попало на одну запись, тем она релевантнее запросу.
Это будет точно менее 150мс.