Database Programming & Design
основанный на RID. Однако ситуация
больше, чем индекс,
основанный на 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-индексами не только в
связи с нагрузкой на процессор, но и по причине большого числа
обменов с внешней памятью. Для решения обеих проблем требуется
какой-либо метод сжатия, который позволил бы сократить расходы
внешней памяти, но в то же время позволил бы по-прежнему быстро
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий