Прямой метод доступа
Исходные ключи | Преобразованные объектные ключи | Адрес хранения (относительный № блока) | |
X101 X102 X103... X199 Y100 Y101 | 01 02 03... 99 100 101 | 01 02 03... 99 100 101 | X101 X102 X103... X199 Y500 Y501 |
. Такая функция не дает равномерного распределения, и потому используют более подходящие функции, например f = сумма цифр ключа (mod 10)+1.
Платой за скорость поиска и обновления в режиме 2 являются нарушение упорядоченности файла, потеря возможности выполнять пакетную обработку по первичному ключу. Время обработки в режиме 1 велико. Эффективность хранения и эффективность доступа при использовании хеширования зависят от распределения ключей, алгоритма хеширования и распределения памяти.
Обновление данных.
Следует отдельно поговорить о методах поиска данных и выдаче результатов (в промежуточную память, на терминал) для последовательных методов обработки. Здесь используют поиск с помощью дерева (B-, бинарное, B+-деревья). Бинарное дерево является разновидностью B-дерева. B-дерево допускает более двух ветвей, исходящих из одной вершины. Любая вершина состоит из совокупности значений первичного ключа, указателей индексов и (ассоциированных) данных. Указатель индекса используется для перехода на следующий, более низкий уровень вершин. «Хранимые» в вершине данные фактически представляют собой совокупность указателей данных и служат для физической организации данных, определения положения данных, ключевое значение которых хранится в этой вершине индекса. Физическая организация ветвящейся вершины B-дерева подобна физической последовательной структуре.
|
|
Этот метод дает хорошее использование памяти, обладает малым числом подопераций. Включение и удаление данных достаточно просто и эффективно.
Более распространенным вариантом B-дерева является B+-дерево. Здесь возможно использовать двунаправленные указатели, а в промежуточных вершинах имеет место дублирование ключей. Если происходит деление вершины, то в исходную вершину пересылается значение среднего ключа. Фактически B+-дерево есть индекс (указатель всех записей файла) вместе с B-деревом, как многоуровневым указателем на элементы последнего индекса.
В B+-дереве его копия помещается в левую часть правого листа, что позволяет упростить операции добавления и удаления.
Для суперЭВМ чаще всего используется иерархическая модель данных в силу ее высокого быстродействия. Для персональных компьютеров широчайшее распространение получила реляционная модель данных, по которой проведены значительные прикладные и теоретические исследования. Это обусловило следующие основные направления развития технологии баз данных.
Дата добавления: 2015-12-17; просмотров: 22; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!