Какой применить алгоритм выборки по двум ключам?

Question

Индекс понятно это отсортированный массив в котором можно быстро найти индексы нужного диапазона значений, например бинарным поиском. Но как быть если индекса два? например как на картинке выборка тех прямоугольников которые затрагивают красную область (касаются или входят в нее) . Если координаты объектов отсортированы по каждой из осей то можно не перебирая весь массив быстро найти все объекты из диапазона например от верхней до нижней границы или от левой до правой, но каким алгоритмом искать те которые удовлетворяют сразу обоим условиям?

ПС. массив часто меняется, и в общем случае таких объектов там миллионы в многомерном пространстве.

Не могу добавить картинку сюда, майл глючит, но она есть в вопросе номер 166719213

ПС. массив часто меняется, и в общем случае таких объектов там миллионы в многомерном пространстве.

Не могу добавить картинку сюда, майл глючит, но она есть в вопросе номер 166719213

Александр Балаев · Accepted Answer

"Индекс понятно это отсортированный массив" - на самом деле очень редко массив, обычно дерево, или даже битовый массив. Порядок тоже не всегда присутствует (пример - хеш-код)

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

В качестве примера извращённого индекса приведу способ определения объектов, пересекающихся с заданной областью.
1. Разбить всю область на кубики, каждый кубик занумеровать
2. Для каждого кубика хранить список объектов в которые он входит
3. Найти ВСЕ кубики, которые входят в область
4. Объединить списки объектов, которые пересекаются с кубиками на шаге 3, в один список
5. Для каждого элемента списка из пункта 4 проверить пересечение с заданной областью

Такая система будет индексом. Эффективность работы определяется количеством объектов, количеством кубиков, частотой запроса и т. п.

ЗЫ Говоря "список объектов", я не подразумеваю классический список типа "указатель на объект + указатель на следующий", это множество или даже указатели на участки памяти в которых хранятся несколько объектов. Вы ведь не отводите память под каждый объект отдельно?

Валентина · Answer

Совпал ход мыслей :) http://otvet.mail.ru/answer/1708556016