Суть методов хеширования состоит в том, что надо брать значения ключа (или некоторые его характеристики) и использовать его для начала поиска, то есть вычислить некоторую хэш-функцию h(k) и полученное значение необходимо брать в качестве адреса начала поиска. Таким образом, нескольким разным ключам может соответствовать одно значение хеш-функции (то есть один адрес). Подобные ситуации называются коллизиями. Значения ключей, которые имеют одно и то же значение хэш-функции, называются синонимами.
Поэтому при использовании хеширования как метода доступа необходимо принять два независимых решения:
1. выбрать хеш-функцию;
2. выбрать метод разрешения коллизий.
Существует множество различных стратегий разрешения коллизий, но мы для примера рассмотрим две достаточно распространенные.
1. Стратегия разрешения коллизий с областью переполнения
При выборе этой стратегии область хранения разбивается на 2 части:
- основную область;
- область переполнения.
Для каждой новой записи вычисляется значение хэш-функции, которое определяет адрес ее расположения, и запись заносится в основную область в соответствии с полученным значением хэш-функции.
Если вновь заносимая запись имеет значение функции хеширования такое же, которое использовала другая запись, уже имеющаяся в БД, то новая запись заносится в область переполнения на первое свободное место, а в записи-синониме, которая находится в основной области, делается ссылка на адрес вновь размещенной записи в области переполнения. Если же уже существует ссылка в записи-синониме, которая расположена в основной области, то тогда новая запись получает дополнительную информацию в виде ссылки и уже в таком виде заносится в область переполнения.
При этом цепочка синонимов не разрывается, но не надо просматривать ее до конца, чтобы расположить новую запись в конце цепочки синонимов, а располагаем всегда новую запись на второе место в цепочке синонимов, что существенно сокращает время размещения новой записи. При таком алгоритме время размещения любой новой записи составляет не более двух обращений к диску, с учетом того, что номер первой свободной записи в области переполнения хранится в виде системной переменной.
Необходимо рассмотреть механизмы поиска произвольной записи и удаления записи данной стратегии.
При поиске записи также сначала вычисляется значение ее хеш-функции и считывается первая запись в цепочке синонимов, которая расположена в основной области. Если искомая запись не соответствует первой в цепочке синонимов, то далее поиск происходит перемещением по цепочке синонимов, пока не будет обнаружена требуемая запись.
Скорость поиска зависит от длины цепочки синонимов, поэтому качество хеш-функции определяется максимальной длиной цепочки синонимов. Хорошим результатом может считаться наличие не более 10 синонимов в цепочке.
При удалении произвольной записи сначала определяется ее место расположения. Если удаляемой является первая запись в цепочке синонимов, то после удаления на ее место в основной области заносится вторая (следующая) запись в цепочке синонимов, при этом все указатели (ссылки на синонимы) сохраняются. Если же удаляемая запись находится в середине цепочки синонимов, то необходимо провести корректировку указателей: в записи, предшествующей удаляемой, в цепочке ставится указатель из удаляемой записи. Если это последняя запись в цепочке, то все равно механизм изменения указателей такой же, то есть в предшествующую запись заносится признак отсутствия следующей записи в цепочке, который ранее хранился в последней записи.
2. Организация стратегии свободного замещения
При этой стратегии файловое пространство не разделяется на области, но для каждой записи добавляется 2 указателя: указатель на предыдущую запись в цепочке синонимов и указатель на следующую запись в цепочке синонимов.
Отсутствие соответствующей ссылки обозначается специальным символом, например нулем. Для каждой новой записи вычисляется значение хэш-функции, и если данный адрес свободен, то запись попадает на заданное место и становится первой в цепочке синонимов. Если адрес, соответствующий полученному значению хэш-функции, занят, то по наличию ссылок определяется, является ли запись, расположенная по указанному адресу, первой в цепочке синонимов. Если да, то новая запись располагается на первом свободном месте и для нее устанавливаются соответствующие ссылки: она становится второй в цепочке синонимов, на нее ссылается первая запись, а она ссылается на следующую, если таковая есть.
Если запись, которая занимает требуемое место, не является первой записью в цепочке синонимов, значит, она занимает данное место "незаконно" и при появлении "законного владельца" должна быть "выселена", то есть перемещена на новое место. Механизм перемещения аналогичен занесению новой записи, которая уже имеет синоним, занесенный в файл. Для этой записи ищется первое свободное место и корректируются соответствующие ссылки: в записи, которая является предыдущей в цепочке синонимов для перемещаемой записи, заносится указатель на новое место перемещаемой записи, указатели же в самой перемещаемой записи остаются прежние.
После перемещения "незаконной" записи вновь вносимая запись занимает свое законное место и становится первой записью в новой цепочке синонимов.
Механизмы удаления записей во многом аналогичны механизмам удаления в стратегии с областью переполнения. Однако опишем их.
Если удаляемая запись является первой записью в цепочке синонимов, то после удаления на ее место перемещается следующая (вторая) запись из цепочки синонимов и проводится соответствующая корректировка указателя третьей записи в цепочке синонимов, если таковая существует.
Если же удаляется запись, которая находится в середине цепочки синонимов, то производится только корректировка указателей: в предшествующей записи указатель на удаляемую запись заменяется указателем на следующую за удаляемой запись, а в записи, следующей за удаляемой, указатель на предыдущую запись заменяется на указатель на запись, предшествующую удаляемой.
ЗАКЛЮЧЕНИЕ
Рассмотрев и изучив физические модели баз данных, основанные на файловых структурах, можно сказать что в каждой СУБД по-разному организованы хранение и доступ к данным, однако существуют некоторые файловые структуры, которые имеют общепринятые способы организации и широко применяются практически во всех СУБД.
В результате работы были рассмотрены и изучены физические модели баз данных, основанные на файловых структурах. Физические модели баз данных определяют способы размещения данных в среде хранения и способы доступа к этим данным, которые поддерживаются на физическом уровне. Особую роль играют методы хеширования с помощью которых вычисляется хэш-функция. Самыми распространенными стратегиями разрешения коллизий являются стратегия разрешения коллизий с областью переполнения и стратегия свободного замещения, которые отличаются механизмом организации файлового пространства.
Использование баз данных и файловых структур очень важно для развития современного информационного пространства, так как все это используется почти во всех сферах деятельности и на этом основано множество IT-разработок.
СПИСОК ЛИТЕРАТУРЫ
1. Марков А.С., Лисовский К.Ю. Базы данных. Введение в теорию и методологию.: Учебник. – М.: Финансы и статистика, 2004. – 512с.
2. Моисеенко Н.А., Алисултанова Э.Д. Информационные технологии.- Грозный, 2006.-99с.
3. Хомоненко А.Д., Цыганков В.М., Мальцев М.Р. Базы данных: Учебник для высших учебных заведений/Под ред. Проф. А.Д. Хомоненко. – М.: Бином – Пресс; СПб.:Корена принт, 2006. – 736с.
