Эффективная реализация AND в структурах данных, подобных базам данных

Question

Я могу представить, как реализовать простую базу данных и индексировать по некоторым столбцам - просто сохраните значения этих столбцов в сбалансированном дереве какого-то рода.

О чем этот вопрос, как эффективно реализовать AND запросы? Как бы вы реализовали что-то вроде

SELECT * FROM points WHERE x > 0 and x < 4 and y > 10 and y < 14

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

Answer 1

Вы можете очень эффективно сделать это с помощью обычного дерева поиска ...

Вы также можете сделать это в O (N), сканировать все данные, что, как я полагаю, большинство БД делают больше всеговремени.особенно с учетом стоимости индексов.

В любом случае это самый распространенный и простой вид индексов, поддерживаемый в большинстве БД: http://en.wikipedia.org/wiki/B-tree, поэтому, если вы ищете диапазон в индексе, его относительнолегко оптимизировать ...

Кстати, учтите также, что вы ожидаете, что БД поймет, что вы ищете диапазоны, и оптимизируйте в соответствии с этим, потому что AND обычно символизирует, что вам просто необходимы два условия ....