Главная » SQL, Базы данных » МЕТОДЫ СЖАТИЯ БАЗЫ ДАННЫХ

0

Методы сжатия используются для уменьшения объема памяти, необходимого для хранения определенной коллекции данных. Очень часто результатом такого сжатия становится не только экономия пространства памяти, но и сокращение количества операций ввода-вывода  на диске (причем, возможно, еще более значительное по сравнению с экономией памяти). Дело в том, что если данные занимают меньше места, то для доступа к ним требуется меньше операций ввода-вывода. С другой стороны, требуется дополнительная обработка для  восстановления данных (преобразования сжатых данных в исходный формат) после их выборки. Но в конечном итоге достигнутое сокращение количества операций ввода—вывода чаще всего перевешивает недостатки такой дополнительной обработки.

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

Поэтому один из широко применяемых методов сжатия состоит в том, что каждое отдельное значение данных заменяется некоторым обозначением различия между ним и непосредственно предшествующим ему значением. В этом заключается метод дифференциального сжатия (differential compression). Но следует отметить, что для успешного применения такого метода требуется, чтобы доступ к рассматриваемым данным осуществлялся последовательно, поскольку, чтобы распаковать любое конкретное значение, необходимо знать непосредственно предшествующее ему хранимое значение. Поэтому метод дифференциального сжатия главным образом применяется в таких ситуациях, когда доступ к данным должен всегда  осуществляться последовательно, как  в случае (например) использования элементов одноуровневого индекса. Однако необходимо учитывать, что именно в случае индекса  может  быть предусмотрено сжатие не только данных, но и указателей, поскольку, если логическое упорядочение данных, которым характеризуется индекс, является таким же или близким к физическому упорядочению файла с данными, то подряд идущие значения указателей в индексе будут весьма аналогичными друг другу, в связи с чем может оказаться выгодным и сжатие указателей. В действительности, индексы почти всегда позволяют добиться  определенного выигрыша благодаря использованию сжатия, по меньшей мере, применительно к данным, если не к указателям.

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

Roberton Robertson Robertstone Robinson

Допустим также, что поле фамилий служащих имеет длину 12 символов, поэтому каждая из этих фамилий должна рассматриваться (в распакованном виде) как дополненная справа соответствующим количеством пробелов. Один из способов применения дифференциального сжатия к этому множеству значений состоит в том, что символы в начале каждого  элемента,  совпадающие с символами в предыдущем элементе индекса, заменяются числом, указывающим количество совпадающих символов. Такой метод сжатия называется префиксным сжатием (front compression). В результате применения этого метода к указанным выше данным,  будет получено следующее (теперь заключительные пробелы показаны явно с помощью знаков " + ").

О Roberton++++

6  son+++

7  tone+

3 inson++++

Еще один возможный метод сжатия для этого набора данных состоит в том, что могут быть просто удалены все заключительные пробелы (при том условии, что они снова заменяются числом, указывающим количество удаленных пробелов). Такой метод представляет собой пример суффиксного сжатия (rear compression). Эффективность суффиксного сжатия можно  дополнительно повысить, удалив все символы справа от того, который требуется, чтобы  отличить рассматриваемый элемент от двух его непосредственных соседей, как показано ниже.

О  7     Roberto

6    2     so

7    1     t

3  1     i

В данном случае первое из двух чисел в каждом элементе остается таким же, как и в предыдущем примере, а второе представляет собой количество зарегистрированных символов (предполагается, что Следующий элемент после его восстановления не будет иметь подстроку "Robi" в качестве своих первых четырех символов). Но следует отметить, что в этом индексе фактически потеряна некоторая информация. Поэтому после его восстановления он будет выглядеть следующим образом (где "?" обозначает неизвестный символ).

Символ  Е  имеет  максимальную  частоту  и  поэтому  ему  присваивается  самый  короткий  код, состоящий из одного бита, скажем, бита 1. Поэтому все другие коды должны начинаться  с  бита 0 и иметь длину не меньше 2 битов (единственный бит 0 нельзя использовать в качестве кода, поскольку его невозможно будет отличить от начальной части любого другого кода).  Символу А присваивается код с длиной на единицу больше по сравнению с самым коротким  кодом, скажем, 01, поэтому все другие коды  должны  начинаться  с  00.  Аналогичным  образом,  символам  D,  С  и  в  присваиваются  коды, соответственно, 001, 0001 и 0000.

Упражнение. Какие английские слова закодированы в приведенных ниже строках?

00110001010011

010001000110011

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

0 , 3 5   *   1   +   0 , 3 0   *   2   +   0 , 2 0    *   3   +   0 , 1 0   *   4   +   0 , 0 5   *   4   =   2 , 1 5   битов

Если  бы  каждому  символу  было  назначено  одинаковое  количество  битов,  как  в  обычной  схеме кодирования символов, то потребовалось бы 3 бита в расчете на символ (чтобы можно было охватить все эти пять вариантов).

Г .8 .  РЕЗЮ МЕ

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

Ниже в данном резюме приведен краткий обзор некоторых основных тем, затронутых в  настоящем приложении. Прежде всего, был описан метод кластеризации, основная идея которого состоит в том, что записи, часто используемые совместно, должны храниться физически достаточно близко друг от друга. В нем также показано, что в качестве внутреннего обозначения записей  широко применяются идентификаторы  записей  (Record  ID  —  RID).  Затем  были  описаны  наиболее  важные  структуры  хранения, используемые на практике.

■       Индексы (и некоторые их варианты, включая, в частности, В-деревья) и их использование как для последовательного, так и для прямого доступа.

■       Методы хэширования (включая, в частности, расширяемое хэширование) и их применение для

прямого доступа.

Цепочки указателей (называемые также родительско-дочерними структурами) и их многочисленные варианты.

В данном приложении был также описан целый ряд методов сжатия.

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

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии