Быстрый поиск всегда осуществляется по индексу - специально подготовленному набору данных, содержащему только ключевые для задачи поиска данные, в сжатом формате, и размеченные определенным образом для быстрого доступа к записи.
Индексы сегодня полностью обслуживают специальные поисковые движки, коих на рынке много. Велосипеды тут не нужны.
Индексов может быть много - так можно изолировать непересекающиеся наборы данных, и избежать больших "общих" индексов.
Если производительности одного сервера не хватает, применяют кластеры - поиск по индексам хорошо поддается кластеризации.
Чтобы обновлять индексы нужно периодически выполнять переиндексацию - вычитывать полный набор данных и заполнять ими индекс. Это очень тяжелый процесс, поэтому обычно его делают редко и в малонагруженное для сервиса время.
Чтобы можно было искать с учетом всяких прав и статусов сообщений, эти права и статусы сохраняются в тот же индекс как атрибуты, и участвуют в поисковом запросе. Так можно персонифицировать поиск.
Чтобы индексы работали как в реальном времени и соответствовали данным приложения, на приложение навешивают хуки: пользователь скрыл сообщение - сработал хук и переиндексировал только одно это сообщение, что практически не дает нагрузки.
