ЛЕКЦИИ

Лекция на тему

ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ БАЗ ДАННЫХ

Разработчик: ст. преподаватель Черепица Л.С.

План лекции

1. Физический доступ к базе данных

2. Индексирование и хеширование

3. Сжатие данных

Литература

Глоссарий

&

3. СЖАТИЕ ДАННЫХ

3.1. Технология сжатия: сжатие на основе различий,
иерархическое сжатие

Сжатие базы данных отличается от сжатия с помощью архиваторов и состоит в освобождении места на диске от удаленных объектов базы данных и записей таблиц. В СУБД Access сжатие базы данных выполняется командой Сервис/Служебные программы/ Сжать. Далее в диалоговом окне необходимо выбрать базу данных для сжатия и подтвердить сжатие.

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

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

Используются следующие технологии сжатия данных в базах данных:

§  сжатие на основе различий;

§  иерархическое сжатие;

§  кодирование Хаффмана.

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

Один из способов применения сжатия на основе различий – это удаление повторяющихся символов в начале каждой записи с указанием их количества, т. е. переднее сжатие.

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

Следующим способом уменьшения объема занимаемого данными места является иерархическое сжатие.

При иерархическом сжатии учитывается следующее. Хранимая иерархическая запись состоит из двух частей: постоянной и переменной. Набор значений переменного количества внутри одной записи называется группой повторения. Иерархическое сжатие применяют и для индекса, в котором несколько последовательно расположенных значений содержат одни и те же повторяющиеся значения данных, но раз­личные значения указателей.

Аналогичным образом можно применять иерархическое сжа­тие на основе межфайловой кластеризации.

3.2. Кодирование Хаффмана

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

Предположим, что некоторые данные написаны с помощь символов А, Б, В, Г, Д, тогда с учетом относительной частоты с которой эти символы встречаются, у них различные коды (табл. 1).

Таблица 1

Коды символов

Символ А встречается чаще остальных, и потому имеет самый короткий код, состоящий из одного бита. Все остальные коды должны быть длиннее, однако нельзя использовать код на основе одного нуля, так как он будет совпадать с начальной частью дру­гих, более длинных кодов. Оценочно можно сказать, что в сред­нем общая длина закодированного текста на 40% меньше, чем при отсутствии кодирования.