Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Базы данных

Индексно-последовательный метод

Индексный файл упорядочен по первичному ключу (главному атрибуту физической записи). Индекс содержит ссылки не на каждую запись, а на группу записей (рис. 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

01 XI01

XI02

02

02 XI02

XI03

03

03 Х103

Х199

99

99 Х199

Y500

100

100 Y501

Y50I

101

101 Y501

Доступ к данным и их обновление

Следует отдельно поговорить о методах поиска данных [9, 10] и выдаче результатов (в промежуточную память, на терминал) для последовательных методов обработки. Здесь используют поиск с помощью дерева (бинарное В-, В+-деревья). Бинарное дерево является разновидностью В-дерева. В-дерево допускает более двух ветвей, исходящих из одной вершины. Любая вершина состоит из совокупности значений первичного ключа, указателей индексов и (ассоциированных) данных. Указатель индекса используется для перехода на следующий, более низкий уровень вершин (рис. 9.9). "Хранимые" в вершине данные фактически представляют собой совокупность указателей данных и служат для физической организации данных, определения положения данных, ключевое значение которых хранится в этой вершине индекса. Физическая организация ветвящейся вершины В-дерева подобна физической последовательной структуре. Алгоритм работы бинарного дерева (в вершинах) представлен на рис. 9.10.

Этот метод дает хорошее использование памяти, обладает малым числом подопераций. Включение и удаление данных достаточно просто и эффективно.

Использование В-дерева

Рис. 9.9. Использование В-дерева

Алгоритм поиска по В-дереву

Рис. 9.10. Алгоритм поиска по В-дереву: КЗ – ключ запроса; КД – ключ данных

Более распространенным вариантом В-дерева является В+-дерево. Здесь возможно использовать двунаправленные указатели, а в промежуточных вершинах имеет место дублирование ключей. Если происходит деление вершины, то в исходную вершину пересылается значение среднего ключа. Фактически В+-дерево есть индекс (указатель всех записей файла) вместе с В-деревом, как многоуровневым указателем на элементы последнего индекса.

В В+-дереве его копия помещается в левую часть правого листа, что позволяет упростить операции добавления и удаления [8].

Подводя некоторые итоги, можно сделать следующие предварительные выводы.

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

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы