Database Programming & Design



         

Support for Data Warehouses - часть 3


больше, чем индекс,

основанный на 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-индексами не только в

связи с нагрузкой на процессор, но и по причине большого числа

обменов с внешней памятью. Для решения обеих проблем требуется

какой-либо метод сжатия, который позволил бы сократить расходы

внешней памяти, но в то же время позволил бы по-прежнему быстро




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