Ковалевич И.А. Основы баз данных: учебное пособие
Подождите немного. Документ загружается.
больших объемов возможно создание еще нескольких уровней
индексирования (главный индекс, гипериндекс и т. д.).
Рассмотрим, как используются постоянные таблицы для поиска
записи с заданным значением первичного ключа. Например, как
разыскивается запись с ключом 210?
Первоначально система обращается к старшему индексу и,
последовательно просматривая его, ищет первую строку, ключ которой
больше искомого. Для нашего примера это вторая строка. Следовательно,
для последующего просмотра необходимо обратиться к таблице младшего
индекса с номером два.
Далее просматриваются строки младшего индекса до нахождения
первой строки с ключом, большим искомого. Найденная строка определяет
номер страницы, где содержится или должна содержаться искомая запись.
Затем просматривается соответствующая страница (в нашем случае
—страница пять). Если запись на странице не найдена, пользователь будет
об этом уведомлен системой.
Рассмотренный нами типичный пример индексирования по
первичному ключу называют также первичным индексированием. Его
отличительные особенности:
. ключ индексирования должен иметь уникальные и неизменяемые
значения;
. первоначальная загрузка должна выполняться обязательно с
предварительной сортировкой;
. формирование индексных таблиц происходит одновременно с
загрузкой записей в файл, а значения ключа индексирования влияют на
размещение записей в памяти ЭВМ.
6.3.3.ДОСТУП ПО ВТОРИЧНЫМ КЛЮЧАМ
При обработке базы данных возникает потребность извлекать записи
по значениям данных, отличных от первичного ключа. Например, может
потребоваться извлекать записи о сотрудниках по должности или по
должности и году рождения. Как минимум эта возможность обеспечивается
последовательным просмотром всех записей СОТРУДНИК (Таблица 6 .1).
Из-за большого числа записей такая обработка может оказаться
неэффективной.
Другой вариант состоит в использовании вторичного
индексирования. При нем любое данное записи можно объявить вторичным
ключом, и тогда система построит индексную таблицу, устанавливающую
соответствие между значениями вторичного ключа и КБД записей,
имеющих эти значения. Так, если для записей СОТРУДНИК объявлены
вторичными ключами данные ДОЛЖНОСТЬ и ГОД-РОЖДЕНИЯ, то
система построит таблицы, представленные в Таблица 6 .2
КБД ФИО Должность Год
рождения
1 Порхачев В. A. Инженер 1947
2 Лободин Ф. И. Бухгалтер 1948
3 Прохорова 0. М. Техник 1950
4 Грузман М. 3. Инженер 1947
5 Эйдус В. Е. Программист 1950
6 Невский П. Л. Техник 1949
7 Матюшкина М. Д. Лаборант 1950
8 Хабынина И. В. Программист 1949
9 Волкова Г. А. Бухгалтер 1948
10 Балкерей Ю. В. Техник 1947
11 Моргуновская С. X. Программист 1948
12 Терехова К. В. Лаборант 1949
… …
Таблица 6.1.
Такие таблицы называют еще инвертированными списками. Если в
Таблица 6 .1 каждому значению КБД ставятся в соответствие значения
данных, то в инвертированных списках значениям данных ставятся в
соответствие КБД. В инвертированных списках к значениям вторичного
ключа обеспечивается прямой доступ.
Теперь запрос «Найти записи о программистах с годом рождения не
ранее 1949» сводится к просмотру инвертированных списков. При
обработке первого списка система получит список КБД записей о всех
программистах; в нашем примере это 5, 8, 11. При обращении ко второму
инвертированному списку получаем список КБД записей о сотрудниках с
требуемым годом рождения: 6, 8, 12, 3, 5, 7. Построенное системой
пересечение этих двух списков дает в результате список КБД записей,
удовлетворяющих запросу: 5 и 8. Для их получения достаточно двух
обращений к страницам данных.
Должность КБД Год
рождения
КБД
Бухгалтер 2 1947 1
9 4
Инженер 1 10
4 1948 2
Лаборант 7 9
12 11
Программист 5 1949 6
8 8
11 12
Техник 3 1950 3
6 5
10 7
Таблица 6.2
Использование таблиц вторичного индексирования позволяет
существенно сократить время реакции на запросы пользователей.
Инвертированные списки занимают существенно меньшие объемы памяти и
поэтому обрабатываются быстро. Система при частых обращениях к
инвертированным спискам размещает их целиком (или значительную часть)
в оперативной памяти, существенно повышая эффективность обработки
информации.
Отметим отличительные особенности вторичного индексирования:
— вторичные ключи могут иметь неуникальные значения. Допускается
изменение значений вторичных ключей; при этом системой
автоматически будут корректироваться соответствующие
инвертированные списки;
— вторичное индексирование служит только для выборки данных и никак
не используется при размещении записей в памяти ЭВМ;
— таблицы вторичного индексирования можно создавать не только при
первоначальной загрузке, но и в любое другое время. Для этой цели в
состав СУБД входит специальная сервисная программа. Попутно
отметим, что администратор БД может легко отменить вторичный ключ;
эта процедура также выполняется сервисной программой и состоит в
уничтожении соответствующего инвертированного списка.
Организация индексных таблиц. Как мы видим, при использовании
первичного или вторичного индексирования необходима поддержка в
системе индексных таблиц. Причем организация этих таблиц должна
обеспечивать быстрое нахождение по значению ключа индексирования
адреса записи.
Один из механизмов индексирования нами рассмотрен. Он
ассоциируется с иерархией индексных таблиц и последовательным
просмотром внутри таблицы. Этот механизм индексирования работает
только, если записи перед загрузкой накапливаются и упорядочиваются.
Если же загрузка БД происходит в реальном масштабе времени одиночными
записями, то этот механизм индексирования если не неприемлем, то уж
наверняка неэффективен.
6.3.4.БИНАРНЫЕ ДЕРЕВЬЯ
Индексная таблица при этом механизме индексирования состоит из
множества записей, связанных адресными ссылками в иерархическую
структуру; такие записи назовем индексными.
Каждая индексная запись содержит значение ключа записи, адрес
этой записи (КБД), а также две адресные ссылки. Первая призвана
адресоваться к индексной записи с ключом меньшим, а вторая—к
индексной записи с ключом большим, чем данный. Рассмотрим применение
адресных ссылок и ключей.
При этом механизме индексирования не требуется, чтобы записи
предварительно накапливались и упорядочивались. Каждой записи БД
соответствует одна индексная запись. Первая индексная запись становится
корневой.
При запоминании любой последующей индексной записи система
определяет ее логическое расположение, начиная просмотр с корня дерева.
Если новая запись имеет ключ меньший, чем просматриваемая вершина
дерева, то переход выполняется влево, иначе — вправо.
Рассмотрим пример.
В показаны последовательность загрузки и значения ключей
записей.
Номер записи Ключ записи Номер записи Ключ записи
1 12 7 14
2 8 8 16
3 4 9 100
4 9 10 10
5 6 11 25
6 13 12 32
Таблица 6.3
Рис.Y6.7. Пример бинарного дерева.
На Рис.Y 6 .7 приведено бинарное дерево для такой
последовательности записей Поиск записи по значению ключа выполняется
по тому же алгоритму, начиная с корня бинарного дерева. Например, для
нахождения записи с ключом 9 система обратится к корневой записи.
Поскольку искомый ключ меньше, переход будет выполнен влево к
индексной записи с ключом 8, а так как ключ больше текущего, переход в
дереве будет выполнен вправо.
Описанный механизм индексирования основан на известном
дихотомическом поиске, состоящем в пошаговом делении поискового
пространства пополам.
Наряду с достоинствами—решением ряда проблем разработки
механизма иерархии индексов—бинарные деревья имеют значительный
недостаток. В нашем примере для извлечения записи с ключом 6 требуется
сделать четыре шага по дереву, а для извлечения записи с ключом 31—семь
шагов, хотя обе записи конечные. Такое дерево, когда конечные вершины
находятся на разных уровнях, называется несбалансированным. Нетрудно
представить себе такую последовательность записей, когда рассмотренный
механизм приведет к построению дерева с одним иерархическим путем.
12
8 13
4 9 14
6 10 16
100
25
31
6.3.5.В–ДЕРЕВЬЯ
Механизм индексирования, основанный на построении так
называемых В–деревьев, позволяет формировать сбалансированные деревья,
когда все конечные вершины равно удалены от корневой был предложен в
1963 г. советскими математиками Г. М. Адельсон–Вельским и Е. М.
Ландисом. В сбалансированном В–дереве длина поиска по любому пути
превышает оптимальный не более чем на 45%.
Принципиальное отличие В–дерева от бинарного состоит в том, что
бинарное растет вниз и корневая вершина не меняется, а В–дерево растет
вверх, и корневая вершина меняется.
ВYдерево порядка n должно удовлетворять следующим условиям.
1. Каждая вершина может содержать n адресных ссылок и п—1
ключей. Ссылка влево от ключа обеспечивает переход к вершине дерева с
меньшими по значению ключами, а вправо—к вершине с большими
ключами.
2. неконечная вершина имеет не менее n/2 подчиненных вершин.
3. Если неконечная вершина содержит k (kY≤Yn) ключей, то ей
подчинена (k+1) вершина на следующем уровне иерархии.
4. Все конечные вершины В–дерева расположены на одном уровне.
Алгоритм формирования В–дерева предполагает первоначальное
заполнение корневой вершины до тех пор, пока не будут сформированы все
ее (n—1) ключей. Затем при появлении очередной записи выделяется новая
корневая вершина и несколько подчиненных ей вершин.
Рис.Y6.8.Пример формирования В–дерева порядка 3.
При запоминании нового ключа поиск места для него начинается с
корня В–дерева, при этом используется алгоритм, рассмотренный для
бинарных деревьев. Построение ВY-Yдерева поясним на примере. Пусть
загружаемая последовательность записей останется той же, что и в , а будем
формировать ВY-Yдерево порядка 3. Очевидно, что каждая запись такого В–
дерева рассчитана на хранение двух ключей и трех адресных ссылок.
Соответствующее В–дерево и последовательность его создания
иллюстрируются на Рис.Y 6 .8
Первоначально корневая вершина содержит только ключ 12. Затем
он сдвигается вправо, уступая место ключу 8 (внутри записи ключи
располагаются в порядке возрастания значений).
Шаги 1, 2
•8 •12•
Шаги 3, 4, 5
• 8• •
• 4 • 6• • 9 •12•
Шаги 6, 7
•8 •12•
• 4 • 6 • • 9 • • •13•14•
Шаги 8, 9, 10
• 12 • •
• 8 • • • 14 • •
• 4 • 6 • •9 • 10• •13 • • •16•100•
Шаги 11, 12
• 12 • •
• 8 • • •14• 25•
• 4 • 6 • • 9 • 10 • • 13 • • • 16 • • •31•100 •
выбирается средний ключ, чтобы ключи 4 и 12 попали в две подчиненные
записи (при этом будут выполнены ограничения 2 и 3).
На шагах загрузки 4 и 5 осуществляется лишь перемещение ключей,
а шаг 6 требует нового деления. Действительно, в записи с ключами 9 и 12
нет места для ключа 13, потому средний ключ из этих трех—12—
перемещается на верхний уровень, а для оставшихся формируются две
подчиненные записи.
В результате мы на любом шаге получаем сбалансированное дерево.
Для нахождения некоторого ключа выполняется просмотр дерева с
корневой записи по тому же алгоритму, что и для бинарных деревьев.
Очевидно, что с увеличением порядка В–дерева сокращается его уровень, а
следовательно, и время просмотра.
Рассмотренные механизмы индексирования, основанные на
поддержке бинарных деревьев и В–деревьев, могут быть успешно
использованы как для первичного, так и для вторичного индексирования.
6.4. ОРГАНИЗАЦИЯ ВНЕШНЕЙ ПАМЯТИ В РЕЛЯЦИОННЫХ
СУБД
Реляционные СУБД обладают рядом особенностей, влияющих на
организацию внешней памяти. К наиболее важным можно отнести
следующие:
— Наличие двух уровней системы: уровня непосредственного управления
данными во внешней памяти (а также обычно управления буферами
оперативной памяти, управления транзакциями и журнализацией
изменений БД) и языкового уровня (например, уровня, реализующего
язык SQL). При такой организации подсистема нижнего уровня должна
поддерживать во внешней памяти набор базовых структур, конкретная
интерпретация которых входит в число функций подсистемы верхнего
уровня.
— Поддержание отношений-каталогов. Информация, связанная с
именованием объектов базы данных и их конкретными свойствами
(например, структура ключа индекса), поддерживается подсистемой
языкового уровня. С точки зрения структур внешней памяти отношение-
каталог ничем не отличается от обычного отношения базы данных.
— Регулярность структур данных. Поскольку основным объектом
реляционной модели данных является плоская таблица, главный набор
объектов внешней памяти может иметь очень простую регулярную
структуру.
— При этом необходимо обеспечить возможность эффективного
выполнения операторов языкового уровня как над одним отношением
(простые селекция и проекция), так и над несколькими отношениями
(наиболее распространено и трудоемко соединение нескольких
отношений). Для этого во внешней памяти должны поддерживаться
дополнительные "управляющие" структуры - индексы.
— Наконец, для выполнения требования надежного хранения баз данных
необходимо поддерживать избыточность хранения данных, что обычно
реализуется в виде журнала изменений базы данных.
— Соответственно возникают следующие разновидности объектов во
внешней памяти базы данных:
— строки отношений - основная часть базы данных, большей частью
непосредственно видимая пользователям;
— управляющие структуры - индексы, создаваемые по инициативе
пользователя (администратора) или верхнего уровня системы из
соображений повышения эффективности выполнения запросов и обычно
автоматически поддерживаемые нижним уровнем системы;
— журнальная информация, поддерживаемая для удовлетворения
потребности в надежном хранении данных;