Как работает алгоритм выборки из БД по двум ключам?

Question

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

Answer 1

Да какая разница, какими алгоритмами? Твоё дело - написать запрос, а уже дело базы данных - выполнить его оптимальным образом. Главное - чтобы для полей были созданы индексы.

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

Кроме того, в некоторых базах данных (например PostgreSQL) есть специальные виды индексов, ориентированные на оптимизацию именно таких запросов.

Answer 2

Во-первых, одного индекса будет достаточно. После поиска по нему записей будут уже далеко не миллионы, дальше достаточно будет простой проверки по условию. Любой современный сервер вам это сделает за незаметное время. Хотя все зависит от ваших критериев по времени. И вобще от ваших задач и целей.
Во-вторых, можно предложить разбить пространство на квадраты, как у военных; составить таблицу "фигура-квадрат" (пересекает ли данная фигура данный квадрат) и проиндексировать е неуникальным индексом по квадрату. Дальше выполнять поиск по всем квадратам, которые пересекаются вашей поисковой областью. Разумется, все равно понадобится дополнительная фильтрация.