Физическая организация баз данных на машинных носителях (стр. 3 из 3)

Рис. 1.2

Таблица 1.1

студент	балл
Иванов	3,4
Васильев	4,2
Кузнецов	3,5
Петров	3,2
Сидоров	4,6
Тихомиров	3,8

Заметим, что здесь используется следующее правило сравнения строковых переменных: считается, что значение символа соответствует его порядковому номеру в алфавите. Поэтому "И" меньше "К", а "К" меньше "С". Если текущие символы в сравниваемых строках совпадают, то сравниваются символы в следующих позициях.

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

Бинарное дерево называют сбалансированным (balanced), если высота левого поддерева каждого узла отличается от высоты правого поддерева не более чем на 1.

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

В-деревом порядка n называется сильно ветвящееся дерево степени 2n+1, обладающее следующими свойствами:

· Каждый узел, за исключением корня, содержит не менее n и не более 2n ключей.

· Корень содержит не менее одного и не более 2n ключей.

· Все листья расположены на одном уровне.

· Каждый нелистовой узел содержит два списка: упорядоченный по возрастанию значений список ключей и соответсвующий ему список указателей (для листовых узлов список указателей отсутствует).

Для такого дерева:

· сравнительно просто может быть организован последовательный доступ;

· все листья расположены на одном уровне;

· при добавлении и изменении ключей все изменения ограничиваются, как правило, одним узлом.

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

R-дерево (R-Tree) это индексная структура для доступа к пространственным данным, предложенная А.Гуттманом (Калифорнийский университет, Беркли). R-дерево допускает произвольное выполнение операций добавления, удаления и поиска данных без периодической переиндексации.

Хеширование

Этот метод используется тогда, когда все множество ключей заранее известно и на время обработки может быть размещено в оперативной памяти. В этом случае строится специальная функция, однозначно отображающая множество ключей на множество указателей, называемая хеш-функцией (от английского "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