Как поисковик успевает подобрать подсказки, пока вы не дописали слово
Вы набрали «face», и под строкой появились пять вариантов. На всё про всё около 50 мс, а выбрать пятёрку надо из сотни миллионов уже заданных кем-то запросов. И так на каждую букву: пока вы печатаете «*facebook», сервис отвечает восемь раз.
Хеш-таблица не подойдёт. «*facebook» в ней находится мгновенно, а «всё, что начинается на face» она искать не умеет в принципе: придётся прочитать все сто миллионов ключей.
Поэтому берут префиксное дерево. Запросы разложены по буквам, и все, кто начинается одинаково, идут общим путём от корня: дойти до «face» это ровно четыре шага. Но под этим узлом всё равно висят тысячи вариантов, поэтому пятёрку самых частых считают заранее и кладут прямо в узел. Пересчитывают пачками: отставание на пару часов никто не замечает.
Как дерево разносят по серверам и что кешируют в CDN, в разборе.
#алгоритмы
*Компания Meta и её продукты признаны экстремистскими, их деятельность запрещена на территории РФ.
1
39
7
2
2
1
1
1
1
1
1
39
7
2
2
1
1
1
1
1
1August 24, 2026 7.8K 1 119
