Базы данных. Лекции БД. Лекция 5 Основные понятия информационных систем 5 История развития компьютеризации информационных процессов и систем. 5

• Название: Лекция 5 Основные понятия информационных систем 5 История развития компьютеризации информационных процессов и систем. 5
• Анкор: Базы данных
• Дата: 05.01.2022
• Размер: 1.07 Mb.
• Имя файла: Лекции БД.doc
• Тип: Лекция; #324711
• страница: 18 из 24

9.2.Хеширование

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

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

NZ =F(К),

где NZ — номер записи, К — значение ключа, F( ) — функция.

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



Рис. 9.5. Пример линейной функции пересчета значения ключа в номер записи
Однако далеко не всегда удается построить взаимно-однозначное соответствие между значениями ключа и номерами записей.

Часто бывает, что значения ключей разбросаны по нескольким диапазонам. В этом случае не удается построить взаимно-однозначную функцию, либо эта функция будет иметь множество незадействованных значений, которые соотвествуют недопустимым значениям ключа. В подобных случаях применяют различные методы хэширования (рандомизации) и создают специальные хэш-функции. Суть методов хэширования состоит в том, что мы берем значения ключа ( пли некоторые его характеристики) и используем его для начала поиска, то есть мы вычисляем некоторую хэш-функшпо h(k) и полученное значение берем в качестве адреса начала поиска. То есть мы не требуем полного взаимно-однозначногосоответствия, но, с другой стороны, для повышения скорости мы ограничиваем время этого поиска (количество дополнительных шагов) для окончательного поучения адреса. Таким образом, мы допускаем, что нескольким разным ключам может соответствовать одно значение хэш-функцин (то есть один адрес). Подобные ситуации называются коллизиями. Значения ключей, которые имеют одно и то же значение хэш-функции, называются синонимами. Поэтому при использовании хэширования как метода доступа необходимо принять два независимых решения:

• 
  выбрать хэш-функцню;
  
• 
  выбрать метод разрешения коллизий.
  

Существует множество различных стратегий разрешения коллизий, но мы для примера рассмотрим две достаточно распространенные,

9.2.1.Стратегия разрешения коллизий с областью переполнения

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

• 
  основную область;
  
• 
  область переполнения.
  

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

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

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

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

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

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

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

9.2.2.Организация стратегии свободного замещения

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

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

После перемещения «незаконной» записи вновь вносимая запись занимает свое законное место и становится первой записью в новой цепочке синонимов.

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

Если удаляемая запись является первой записью в цепочке синонимов, то после удаления на ее место перемещается следующая (вторая) запись из цепочки си­нонимов и проводится соответствующая корректировка указателя третьей запи­си в цепочке синонимов, если таковая существует.

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