Как я могу использовать подразумеваемый запрос ИЛИ на B-дереве?

Question

Я хочу использовать b-дерево для индекса, но не могу придумать решение для запроса OR.

Для запроса OR я имею в виду что-то вроде select * из таблицы, где id от 1 до 5ИЛИ идентификатор между 10 и 15;

если я использую идентификатор в качестве ключа в b-дереве, то как я могу выполнить запрос, аналогичный приведенному выше, для b-дерева?

при поискеb-дерево, предположим, что ключ меньше 6 и больше 6 находится на разных поддеревьях, чем когда путь поиска проходит через поддерево, связанное с ключом меньше 6, т. е. от 1 до5 можно извлечь, но как насчет идентификатора, который между 10 и 15?

Должен ли я использовать дерево b +, и когда я нашел ключ, указывающий на идентификатор 1, я просто продолжил сканирование листаузлы один за другим, пока я не нашел ключ, который указывает на идентификатор 15?Это плохое решение для этого типа запроса: выберите * из таблицы, где идентификатор от 1 до 5 ИЛИ идентификатор от 10000000 до 10000005 ???

Или есть другие решения?

Спасибоочень сильно!

Answer 1

Ключевое слово ИЛИ является распространенной проблемой. С точки зрения индекса, как правило, лучше всего сделать два поиска (например, как UNION).

Однако существуют исключения. Ваш первый пример (идентификатор от 1 до 5 или идентификатор от 10 до 15) лучше всего выполнить в одном поиске по индексу от 1 до 15, отбрасывая значения 6-9. Однако это зависит от объема данных! Второй пример (от 1 до 5 ИЛИ с идентификатором от 10000000 до 10000005) не выглядит хорошим кандидатом для такого подхода. Однако это зависит от количества строк, а не от количества идентификаторов.

Относительно И : ваш пример противоречит (идентификатор от 1 до 5 И идентификатор от 10000000 до 10000005), запрос не будет возвращать никаких строк. Некоторые оптимизаторы могут «видеть» это.

И условия для разных столбцов должны решаться с помощью составных индексов.

Взгляните на мою веб-книгу Используйте Индекс, Люк! для получения более подробной информации.

Answer 2

Операция ИЛИ подразумевает, что необходимо выполнить два поиска и объединить результаты.