Индексы на основе использования битовых шкал
Начнем с определения списка RID. Каждой строке в таблице приписывается RID, который можно рассматривать как указатель на строку на диске. Обычно RID состоит из номера страницы на диске и номера позиции записи на этой странице. Набор строк с данным свойством может быть представлен как список RID этих строк. В большинстве СУБД используются 4-байтовые RID (хотя в Oracle RID имеет длину по крайней мере 6 байт). Традиционно списки RID использовались в индексах для определения набора строк, ассоциированных с каждым значением некоторого индексируемого столбца. Если предположить потребность в индексе на таблице SALES, содержащей 100 миллионов строк и включающей столбец department c 40 разными значениями, то для каждого значения этого столбца мы получим список RID, который в среднем будет соответствовать 2.5 миллионам строк.
При наличии громадного числа RID, ассоциированных с каждым значением department, трудно рассчитывать, что удастся целиком переместить список RID в основную память. Список разбивается на фрагменты по несколько сотен RID, которые могут быть помещены в последовательные листовые узлы B-дерева. Для каждого фрагмента можно хранить в B-дереве только одно значение department, так что критически остается лишь потребность в хранении 100 миллионов 4-байтовых RID.
Теперь мы готовы ввести идею битовой индексации. В таблице, для которой используется эта техника, все строки должны быть перенумерованы: 0, 1, 2, ..., N-1. Нумерация строк должна производиться в соответствии с порядком их RID (физически последовательно относительно расположения строк на диске). Требуется метод преобразования номера строки в RID и наоборот. Теперь, если имеется последовательность из N бит, установим k-тый бит в 1, если строка с номером k входит в набор строк, а в противном случае - в 0. Битовый индекс на SALES по столбцу department аналогичен тому, который основан на RID, но вместо фрагментов RID в нем используются соответствующие битовые фрагменты. Каждый битовый фрагмент будет занимать 12.5 Мб, так что вполне вероятно разместить его на последовательных страницах диска.
Отношение числа битов, установленных в 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-фрагмент. В других подходах используется техника кодирования битовых шкал. В этом случае становится сложно эффективно выполнять перечисленные выше операции между сжатой и несжатой шкалами. Потребность нахождения техники сжатия, которая бы не тормозила выполнение этих операций, является наиболее важной проблемой битовой индексации.
