Индексно-последовательный метод.
Базы данных
Для суперЭВМ чаще всего используется иерархическая модель данных в силу ее высокого быстродействия. Для персональных компьютеров широчайшее распространение получила реляционная модель данных, по которой проведены значительные прикладные и теоретические исследования. В последнее время реляционную модель существенно потеснила объектно-ориентированная модель данных. Записи хранятся в произвольном… Читать ещё >
Индексно-последовательный метод. Базы данных (реферат, курсовая, диплом, контрольная)
Индексный файл упорядочен по первичному ключу (главному атрибуту физической записи). Индекс содержит ссылки не на каждую запись, а на группу записей (рис. 9.3). Последовательная организация индексного файла допускает в свою очередь его индексацию — многоуровневая индексация (рис. 9.4).
Рис. 9.3. Индексно-последовательный метод.
Рис. 9.4. Многоуровневая. индексация Процедура добавления возможна в двух видах.
- 1. Новая запись запоминается в отдельном файле (области), называемой областью переполнения. Блок этой области связывается в цепочку с блоком, к которому логически принадлежит запись. Запись вводится в основной файл.
- 2. Если места в блоке основного файла нет, запись делится пополам и в индексном файле создается новый блок.
Наличие индексного файла большого размера снижает эффективность доступа. В большой БД основным параметром становится скорость выборки первичных и вторичных ключей. При большой интенсивности обновления данных следует периодически проводить реорганизацию БД. Эффективность хранения зависит от размера и изменяемости БД, а эффективность доступа — от числа уровней индексации, распределения памяти для хранения индекса, числа записей в БД, уровня переполнения.
При произвольных методах записи физически располагаются произвольно.
Индексно-произвольный метод
Записи хранятся в произвольном порядке. Создается отдельный файл, хранящий значение действительного ключа и физического адреса (индекса). Каждой записи соответствует индекс. Общая схема показана на рис. 9.5. Идея метода отражена на рис. 9.6: между вырабатываемым (относительным) адресом и физической записью (абсолютным адресом) существует взаимооднозначное соответствие.
Разновидностью этого метода является наличие плотного индекса: кроме главного файла создается вспомогательный файл, называемый плотным индексом. Он состоит из записи (v, р) для любого значения ключа v в главном файле, где р — указатель на запись главного файла со значением ключа v.
Рис. 9.5. Индексно-произвольный метод.
Рис. 9.6. Идея метода кэширования: ПР — программа рандомизации.
Прямой метод
Имеется взаимооднозначное соответствие между ключом записи и ее физическим адресом (рис. 9.7). Выделяют два вида адресов (рис. 9.8): относительный и абсолютный.
В этом методе необходимо преобразование и надо четко знать исходные данные и организацию памяти. Ключи должны быть уникальными.
Эффективность доступа равна 1, а эффективность хранения зависит от плотности ключей.
Если не требовать взаимооднозначности, то получается разновидность метода с использованием кэширования — быстрого поиска данных, особенно при добавлении элементов непредсказуемым образом.
Рис. 9.7. Прямой метод.
Рис. 9.8. Абсолютный и относительный адреса.
Кэширование — метод доступа, обеспечивающий прямую адресацию данных путем преобразования значений ключа в относительный иди абсолютный физический адрес.
Адрес является функцией значения поля и ключа записи. Записи, приобретающие один адрес, называются синонимами. В качестве критериев оптимизации алгоритма кэширования могут быть: потеря связи между адресом и значением поля, минимум синонимов. Память делится на страницы определенного размера, и все синонимы помещаются в пределах одной страницы или в область переполнения. Механизм поиска синонимов — цепочечный.
Любой элемент кэш-таблицы имеет особый ключ, а само занесение осуществляется с помощью кэш-функции, отображающей ключи на множество целых чисел, которые лежат внутри диапазона адресов таблицы.
Кэш-функция должна обеспечивать равномерное распределение ключей по адресам таблицы, однако двум разным ключам может соответствовать один адрес. Если адрес уже занят, возникает состояние, называемое коллизия, которое устраняется специальными алгоритмами: проверка идет к следующей ячейке до обнаружения своей ячейки. Элемент с ключом помещается в эту ячейку.
Для поиска используется аналогичный алгоритм: вычисляется значение кэш-функции, соответствующее ключу, проверяется элемент таблицы, находящийся по указанному адресу. Если обнаруживается пустая ячейка, то элемента нет.
Размер кэш-таблицы должен быть больше числа размещаемых элементов. Если таблица заполняется на шестьдесят процентов, то, как показывает практика, для размещения нового элемента проверяется в среднем не более двух ячеек. После удаления элемента пространство памяти, как правило, не может быть использовано повторно.
Простейшим алгоритмом кэширования может являться функция f(k) = A:(mod 10), где к — ключ, целое число (табл. 9.3). Такая функция не дает равномерного распределения, и потому используют более подходящие функции, например f= сумма цифр ключа (mod 10) + 1.
" Платой" за скорость поиска и обновления в режиме 2 является нарушение упорядоченности файла, потеря возможности выполнять пакетную обработку по первичному ключу. Время обработки в режиме 1 велико.
Эффективность хранения и эффективность доступа при использовании кэширования зависит от распределения ключей, алгоритма кэширования и распределения памяти.
Таблица 9.3
Прямой метод доступа
Исходные ключи. | Преобразованные объектные ключи. | Адрес хранения (относительный N блока). |
Х101. | 01 XI01. | |
XI02. | 02 XI02. | |
XI03. | 03 Х103. | |
Х199. | 99 Х199. | |
Y500. | 100 Y501. | |
Y50I. | 101 Y501. |
Следует отдельно поговорить о методах поиска данных [9, 10] и выдаче результатов (в промежуточную память, на терминал) для последовательных методов обработки. Здесь используют поиск с помощью дерева (бинарное В-, В±деревья). Бинарное дерево является разновидностью В-дерева. В-дерево допускает более двух ветвей, исходящих из одной вершины. Любая вершина состоит из совокупности значений первичного ключа, указателей индексов и (ассоциированных) данных. Указатель индекса используется для перехода на следующий, более низкий уровень вершин (рис. 9.9). «Хранимые» в вершине данные фактически представляют собой совокупность указателей данных и служат для физической организации данных, определения положения данных, ключевое значение которых хранится в этой вершине индекса. Физическая организация ветвящейся вершины В-дерева подобна физической последовательной структуре. Алгоритм работы бинарного дерева (в вершинах) представлен на рис. 9.10.
Этот метод дает хорошее использование памяти, обладает малым числом подопераций. Включение и удаление данных достаточно просто и эффективно.
Рис. 9.9. Использование В-дерева.
Рис. 9.10. Алгоритм поиска по В-дереву: КЗ — ключ запроса; КД — ключ данных Более распространенным вариантом В-дерева является В±дерево. Здесь возможно использовать двунаправленные указатели, а в промежуточных вершинах имеет место дублирование ключей. Если происходит деление вершины, то в исходную вершину пересылается значение среднего ключа. Фактически В±дерево есть индекс (указатель всех записей файла) вместе с В-деревом, как многоуровневым указателем на элементы последнего индекса.
В В±дереве его копия помещается в левую часть правого листа, что позволяет упростить операции добавления и удаления [8].
Подводя некоторые итоги, можно сделать следующие предварительные выводы.
Для суперЭВМ чаще всего используется иерархическая модель данных в силу ее высокого быстродействия. Для персональных компьютеров широчайшее распространение получила реляционная модель данных, по которой проведены значительные прикладные и теоретические исследования. В последнее время реляционную модель существенно потеснила объектно-ориентированная модель данных.