Битовые карты

Для таблиц небольшого объема используют организацию вспомогательной структуры данных в виде битовых карт (рис. 8.10). Для каждого значения вторичного ключа записей основного набора данных записывается последовательность битов. Длина последовательности битов равна числу записей. Каждый бит в битовой карте соответствует одному значению вторичного ключа и одной записи. Единица означает наличие ключа в записи, а ноль – отсутствие.

Основным преимуществом такой организации является простая и эффективная организация обработки сложных запросов, которые могут объединять значения ключей различными логическими предикатами. В этом случае поиск сводится к выполнению логических операций запроса непосредственно над битовыми строками и интерпретации результирующей битовой строки. Другим преимуществом является простота обновления карты при добавлении записей.

К недостаткам битовых карт следует отнести увеличение длины строки пропорционально длине файла. При этом заполненность карты единицами уменьшается с увеличением длины файла. При большой длине таблицы и редко встречающихся ключах битовая карта превращается в большую разреженную матрицу, состоящую в основном из одних нулей.

Рис. 8.10. Организация вспомогательной структуры данных в виде битовых карт.

Контрольные вопросы

1. Объясните преимущества применения хеш-таблиц для хранения данных.

2. Как вычисляется хеш-функция? Как выполняется оценка качества хеш-функции?

3. Что такое совершенное хеширование? Каковы причины возникновения коллизий?

4. Перечислите и опишите методы разрешения коллизий.

5. В чем заключается идея организации данных по первичным и вторичным ключам в таблицах?

Дата добавления: 2014-01-07