дерева карты с несколькими ключами и поддержкой поиска диапазона

Question

мне нужна эффективная структура данных, которая содержит отображение пар для значений

(x,y) => v 

и позволяет найти пары ключа-значения соответствия выражения 2d диапазона:

x1 < x < x2 && y1 < y < y2 

быстрее, чем полный поиск. У меня есть какое-то решение, хотя его сложно реализовать. Есть ли стандартный алгоритм/подход для такой задачи? Я считаю, что разработчикам БД пришлось решить эту проблему, обращаясь к проблеме сложных индексов.

Answer 1

Если вы хотите очень простое решение, попробуйте следующее:

• держать ключи, упорядоченные по х;

• заданный диапазон запросов, найдите первую точку в диапазоне x по дихотомии;

• петля на x до конца диапазона x и проверка на y.

Предполагая, что ваши ключи равномерно распределены, если х-диапазон занимает фракция Fx всей области является ускорение по сравнению с перебором является 1/Fx (не 1/Fx.Fy, к сожалению).

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

---

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

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

quad-tree Структура данных можно рассматривать как адаптивную версию сетки.