Support for Data Warehouses - часть 2

ассоциированных с каждым значением некоторого индексируемого

столбца. Если предположить потребность в индексе на таблице

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 Мб внешней памяти, т.е.