Мы продолжаем ускорять наш веб-сервис, чтобы стандартизация контактных данных и генерация подсказок в Ахантере выполнялись максимально быстро. Это достигается за счёт разработки особых поисковых структур, индексов и деревьев, которые обычно остаются за кадром, но без которых невозможно обрабатывать запросы к сервису за считанные миллисекунды по многомиллионным базам ФИАС, ЕГРЮЛ и ЕГРИП в режиме реального времени.

Время от времени нам приходится придумывать новые индексы и виды деревьев, чтобы продолжать быстро обрабатывать новые сложные запросы к сервису. Это возможно, потому что в Ахантере у нас реализовано собственное хранилище. За последние пару месяцев в это хранилище мы добавили ещё два новых вида индексов, позволяющие быстрее решать поисковые задачи.

Разработали и внедрили новый индекс для поиска адресов по старым кодам КЛАДР. Раньше Ахантер умел искать адреса по сигнатурам, которые присваиваются объектам в рамках нашей внутренней адресной базы, а также по почтовым индексам и по ФИАС-идентификаторам. После того, как в ФНС России заменили классификатор адресов КЛАДР на систему ФИАС, коды КЛАДР постепенно утратили актуальность. Однако у наших пользователей до сих пор возникают задачи, связанные с получением адресов по этим кодам. Для этих целей мы внедрили специализированный индекс КЛАДР-кодов. В оригинале данные коды включают от 15 до 19 знаков. При построении нашего специализированного индекса для этих кодов нам удалось его сжать в 8 раз, в сравнении с SQL-реализацией. Новый индекс используется в API-команде fetch/address, когда в качества запроса этой команде передаётся не ФИАС-идентификатор, а код КЛАДР.

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

Разработали новый пространственный индекс для обратного гео-кодера и метод поиска адресов по координатам, использующий данный индекс.

Обратный гео-кодер в Ахантере позволяет искать адреса в пределах некоторого радиуса вокруг заданной точки на карте. Для выполнения такого пространственного запроса нужно перебрать все адреса в базе гео-кодера и отобрать из них те, которые находятся в рамках заданной поисковым запросом области.

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

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

Такая доработка позволила добиться одинакового эффективного поиска адресов по их координатам на любых широтах, включая полюса Земли, при этом время выполнения пространственных запросов удалось сократилось до нескольких миллисекунд.