19.03.2026
Это интерактивное введение в структуру данных "quadtree" (четвертичное дерево). Тут объясняется, почему оно используется в картах Uber.
Автор наглядно показывает, как наивный подход к поиску ближайших объектов, например, перебор всех точек, становится крайне неэффективным при масштабировании до миллионов записей. Вместо этого quadtree рекурсивно делит пространство на четыре квадранта, адаптируясь к плотности данных: в областях с большим количеством точек создаются мелкие ячейки, а пустые пространства остаются крупными
