Методы сортировки и поиска



Индексы на основе использования битовых шкал - часть 2


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

В этом случае полный битовый индекс требует на листовом уровне чуть больше 500 Мб внешней памяти, т.е. больше, чем индекс, основанный на RID. Однако, ситуация меняется, если индексируемый столбец содержит мало различных значений. Если, например, таблица SALES содержит столбец gender (пол) со всего двумя значениями M и F, то для листового уровня битового индекса потребуется всего 25 Мб, в то время как для RID-индекса по-прежнему было бы нужно иметь 400 Мб. Для индексов с менее, чем 32 значениями битовые индексы позволяют экономить память.

Однако, наиболее важным свойством неупакованных битовых индексов является не экономия памяти, а возможность существенно повысить скорость выполнения операций AND, OR, NOT и COUNT. Предположим, что имеются два битовых фрагмента B1 и B2, где B1 представляет свойство gender = 'M', а B2 - department = 'sports'. Тогда для получения битового фрагмента, соответствующего свойству B1 & B2, требуется всего лишь выполнить поразрядное логическое умножение B1 и B2.

Для выполнения операции AND над двумя списками RID требуется более сложная техника: слияние с пересечением. Нужно использовать два курсора, каждый из которых продвигается по одному из списков, и в результирующем списке остаются те RID, которые встречаются в каждом из исходных списков.

Конечно, если списки-операнды включают только по несколько десятков RID, то цикл со списками RID окажется более эффективным, чем цикл, в котором выполняется логическое умножение битовых шкал, длина каждой из которых равна общему числу строк в таблице. Но при плотности битовой шкалы большей, чем 1/100, алгоритм на основе битовых шкал работает быстрее. Аналогично обстоят дела с алгоритмами для выполнения операций OR, NOT и COUNT.

Если битовая шкала становится очень разреженной, то битовые индексы работают плохо по сравнению с RID-индексами не только в связи с нагрузкой на процессор, но и по причине большого числа обменов с внешней памятью.Для решения обеих проблем требуется какой-либо метод сжатия, который позволил бы сократить расходы внешней памяти, но в то же время позволил бы по-прежнему быстро выполнять операции AND, OR, NOT и COUNT. Один из подходов состоит в совместном использовании битовой и RID индексации: когда битовый фрагмент становится слишком разреженным, он заменяется на RID-фрагмент. В других подходах используется техника кодирования битовых шкал. В этом случае становится сложно эффективно выполнять перечисленные выше операции между сжатой и несжатой шкалами. Потребность нахождения техники сжатия, которая бы не тормозила выполнение этих операций, является наиболее важной проблемой битовой индексации.

 


Содержание  Назад