Реферат: Физическая организация баз данных на машинных носителях

Хеширование

Этот метод используется тогда, когда все множество ключей заранее известно и на время обработки может быть размещено в оперативной памяти. В этом случае строится специальная функция, однозначно отображающая множество ключей на множество указателей, называемая хеш-функцией (от английского "to hash" - резать, измельчать). Имея такую функцию можно вычислить адрес записи в файле по заданному ключу поиска. В общем случае ключевые данные, используемые для определения адреса записи организуются в виде таблицы, называемой хеш-таблицей.

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

Для более продвинутого пользователя можно привести следующее определение:

Хеширование (иногда хэширование, англ. hashing) — преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или дайджестом сообщения (англ. message digest).

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

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

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

Недостатки методов хеширования: 1) последовательность расположения в памяти записей не совпадает с последовательностью, определяемой первичным ключом; 2) возможность коллизий, когда для двух различных записей (с разными значениями ключе) вычисляется один и тот же адрес памяти.

Заключение

По мере написания данной работы автором было выяснено несколько важных моментов:

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

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

Естественно, что такое широкое распространение БД требует их и СУБД постоянного совершенствования и развития.

Список литературы:

1. К. Дж. Дейт Введение в системы баз данных = Introduction to Database Systems. — 8-е изд. — М.: «Вильямс», 2006. — 1328 с. — ISBN 0-321-19784-4

2. Кузнецов Сергей Дмитриевич Основы баз данных. — 1-е изд. — М.: «Интернет-университет информационных технологий - ИНТУИТ.ру», 2005. — 488 с. — ISBN 5-9556-00028-0

3. Когаловский М.Р. Энциклопедия технологий баз данных. — М.: Финансы и статистика, 2002. — 800 с. — ISBN 5-279-02276-4

4. http://www.kopabori.ru/index56.htm

5. http://www.mstu.edu.ru/education/materials/zelenkov/toc.html