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

Question

Мне при вызове метода приходят кординаты некоей точки O: это O1, O2, O5, каждый раз разные, и некое число d, радиус куба по естественно выбранной норме.

Мне нужно уметь быстро выбирать из таблицы все объекты, у которых O1 -d x1 O1 + d и O2 -d x2 O2 + d и т. д. по всем пяти кординатам.
Как лучше индексировать е? Таблица меняется редко, объекты из не выбираются часто.

В таблице около 10 миллиардов записей, в выборку по маленькому пятимерному кубу в среднем попадает около 10 записей. Объекты таблицы имеют равномерное распределение в большом пятимерном кубе и независимы.

Answer 1

я бы для начала попробовал, как сама СУБД выполнит такой запрос, они часто достаточно умные.

в аналогичной задаче без СУБД можно применить К-дерево. делим все точки на 2 равных подмножества по первой кординате, потом - каждое делим так по второй, дале - так по кругу, пока не останутся куски точек по 100-200. Можно при делении отслеживать. по какой кординате подмножество наиболе протяженное и делить по ней (хотя бы и получится деление подряд по одной дважды) .

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

работает реально быстро, по крайней мере на С+.

да, разделение на подмножества делается за O (n) через nthelement