Меню
Главная
УСЛУГИ
Авторизация/Регистрация
Реклама на сайте
Индексный методИндексно-трендовый методИндексный метод
Индексный методИндексно-трендовый методИндексный метод
Прямые методыМетод прямого сравненияМетод прямой капитализации доходов
ЗУ с последовательным доступомРежимы свободного и ограниченного доступа к информационным ресурсам....Обновление основных фондов
 
Главная 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
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Предметы
Агропромышленность
Банковское дело
БЖД
Бухучет и аудит
География
Документоведение
Журналистика
Инвестирование
Информатика
История
Культурология
Литература
Логика
Логистика
Маркетинг
Медицина
Менеджмент
Недвижимость
Педагогика
Политология
Политэкономия
Право
Психология
Религиоведение
Риторика
Социология
Статистика
Страховое дело
Техника
Товароведение
Туризм
Философия
Финансы
Экология
Экономика
Этика и эстетика