Индексы и их использование для ускорения извлечения данных

Для реализации в СУБД таких функций как автоматическая сортировка записей, контроль за отсутствием повторений значений в ключевых полях записей и повышение скорости выполнения операций поиска в таблице применяют индексирование.

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

Индекс (index) – средство ускорения операции поиска записей в таблице, а также выполнения других операций, использующих поиск: извлечение, модификация, сортировка и т.д. Индексный файл (index file) – это файл, в котором хранится информация индекса. Он является файлом особого типа, в котором каждая запись состоит из двух значений: данных и указателя номера записи. При этом данные необходимы для индексного поля из индексированного файла, а указатель – для связывания с соответствующей записью индексированного файла.

На практике для создания индекса для некоторой таблицы базы данных пользователь указывает поле таблицы, которое требует индексации.

Термин «индекс» тесно связан с понятием «ключ», хотя между ними есть и некоторое отличие.

Если индексирование организовано на основе ключевого поля, то индекс называется первичным. Ключевые поля, как правило, индексируются автоматически.

Если индекс организован на основе другого поля, то он называется вторичным. Индекс, организованный на основе ключевого поля или другого ключа, называется уникальным.

На практике индексы можно использовать двумя разными способами:

• последовательного доступа к индексированному файлу, т. е. в последовательности, заданной значениями индексного поля;

• прямого доступа к отдельным записям индексированного файла на основе заданного значения индексного поля.

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

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

Индекс, в котором не содержатся указатели на все записи индексиро­ванного файла, называется неплотным. Одним из преимуществ неплотных индексов яв­ляется их малый размер по сравнению с плотными индексами. т. к., они содержат меньшее число записей. Это часто позволяет просматривать содержимое БД с большей скоростью, но нельзя выполнить проверку наличия некоторого значения.

 

Особенности технологии хеширования

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

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

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

Основные особенности технологиихеширования:

• каждая хранимая запись БД размещается по адресу, который вычисляется с помощью специальной хеш-функции на основе значения некоторого поля данной записи, т.е. хеш-поля, а вычисленный адрес называется хеш-адресом;

• для сохранения записи в СУБД сначала вычисляется хеш-адрес новой записи, после чего Диспетчер файлов помещает эту запись по вычисленному адресу;

• для извлечения нужной записи по заданному значению хеш-поля в СУБД сначала вычисляется хеш-адрес, а затем Диспетчеру файлов посылается запрос на извлечение записи по вычисленному адресу.

Технология хеширования имеет свои недостатки.

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

Таблица 1

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

 

Символ	Частота, %	Код
А
В
Г
Д
Б

 

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

Глоссарий

 

Диспетчер дисков	Программное обеспечение, контролирующее перемещение данных между оперативной памятью и диском
Диспетчер файлов	Программное обеспечение, управляющее размещением данных на диске и структурами данных
Индекс	Средство ускорения операции поиска записей в таблице, а также выполнения других операций, использующих поиск: извлечение, модификация, сортировка и т.д.
Индексный файл	Файл, в котором хранится информация индекса
Кодирование Хаффмана	Технология кодирования символов, которая может быть эффективной для сжатия различных символов, встречающихся с разной частотой
Сжатие на основе различий	Технология сжатия данных в БД, которая предусматривает замену некоторого значения сведениями о его отличиях от предыдущего значения
Словарь данных	Часть СУБД, определяющая структуру пользовательских данных и возможности их использования
Стратегический селектор	Программное обеспечение, преобразующее требование пользователя в эффективную для исполнения форму
Транзакция	Последовательность операций над БД, рассматриваемых СУБД как единое целое
Хеширование	Технология быстрого прямого доступа к хранимой записи на основе заданного значения некоторого поля, при этом, поле не обязательно должно быть ключевым

⇐ Предыдущая12

Поделиться:

Воспользуйтесь поиском по сайту: