Типичный программист | IT, программирование, разработка, ИИ
IT и технологии · 24 августа 2026 г.
Как поисковик успевает подобрать подсказки, пока вы не дописали слово — 24 августа 2026 г. в 15:36:38.448
Как поисковик успевает подобрать подсказки, пока вы не дописали слово Вы набрали «face», и под строкой появились пять вариантов. На всё про всё около 50 мс, а выбрать пятёрку надо из сотни миллионов уже заданных кем-то запросов. И так на каждую букву: пока вы печатаете «*facebook», сервис отвечает восемь раз. Хеш-таблица не подойдёт. «*facebook» в ней находится мгновенно, а «всё, что начинается на face» она искать не умеет в принципе: придётся прочитать все сто миллионов ключей. Поэтому берут префиксное дерево. Запросы разложены по буквам, и все, кто начинается одинаково, идут общим путём от корня: дойти до «face» это ровно четыре шага. Но под этим узлом всё равно висят тысячи вариантов, поэтому пятёрку самых частых считают заранее и кладут прямо в узел. Пересчитывают пачками: отставание на пару часов никто не замечает. Как дерево разносят по серверам и что кешируют в CDN, в разборе. #алгоритмы *Компания Meta и её продукты признаны экстремистскими, их деятельность запрещена на территории РФ.