Database Programming & Design
c 40 разными значениями, то
ассоциированных с каждым значением некоторого индексируемого
столбца. Если предположить потребность в индексе на таблице
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 Мб внешней памяти, т.е.
