Как поисковик успевает подобрать подсказки, пока вы не дописали слово

Вы набрали «face», и под строкой появились пять вариантов. На всё про всё около 50 мс, а выбрать пятёрку надо из сотни миллионов уже заданных кем-то запросов. И так на каждую букву: пока вы печатаете «*facebook», сервис отвечает восемь раз.

Хеш-таблица не подойдёт. «*facebook» в ней находится мгновенно, а «всё, что начинается на face» она искать не умеет в принципе: придётся прочитать все сто миллионов ключей.

Поэтому берут префиксное дерево. Запросы разложены по буквам, и все, кто начинается одинаково, идут общим путём от корня: дойти до «face» это ровно четыре шага. Но под этим узлом всё равно висят тысячи вариантов, поэтому пятёрку самых частых считают заранее и кладут прямо в узел. Пересчитывают пачками: отставание на пару часов никто не замечает.

Как дерево разносят по серверам и что кешируют в CDN, в разборе.

#алгоритмы

*Компания Meta и её продукты признаны экстремистскими, их деятельность запрещена на территории РФ.