2.3.2. Индексирование данных

Как уже отмечалось, стандартным приемом повышения эф­фективности доступа к записям в базах данных является созда­ние индексных массивов по отдельным, обычно ключевым по­лям. Идея индексов основана на том факте, что если для повы­шения эффективности доступа к конкретному кортежу-записи использовать линейное упорядочение кортежей в таблице (ска­жем, по алфавиту для текстовых ключевых полей или по возра­станию для числовых ключевых полей), то накладные расходы по «перетряске» всей таблицы после добавления/удаления строк-кортежей превысят выигрыш во времени доступа. Струк­тура индексов (индексных массивов) строится так, чтобы на основе некоторого критерия можно было бы быстро находить по значению индексируемого поля указатель на нужную запись (строку) таблицы и получать к ней доступ. При этом совокуп­ность записей-кортежей базовой таблицы не обязательно упо­рядочивать, а при их изменении необходимо изменить только лишь индексный массив.

Как и для информационных массивов самих данных (таб­лиц), так и для индексных массивов применяются линейные и нелинейные структуры. В качестве линейных структур ин­дексовв большинстве случаев выступают инвертированные списки.Инвертированный список строится по схеме таблицы с двумя колонками — «Значение индексируемого поля» и «Но­мера строк»* (см. рис. 2.16). Инвертированные списки чаще все­го применяются для индексации полей, значения которых в раз­ных строках-записях могут повторяться, к примеру, поле «Год рождения» таблицы «Сотрудники» (в реляционных базах дан­ных такие поля не могут быть ключевыми).

* На практике не номера строк базовой таблицы, а номера страниц файла БД, где находится соответствующая строка.

Значение индексируемого поля ("Год рождения")	Номера, строк
1958	3
1959	5, 17, 123, 256
1960	31, 32, 77
1961	11, 45, 58, 167, 231
1962	7, 8, 9, 10, 234, 235, 236

Рис. 2.16. Пример инвертированного списка

Строки инвертированного списка упорядочиваются по зна­чению индексируемого поля. Для доступа к нужной строке исходной таблицы сначала в упорядоченном инвертированном списке отыскивается строка с требуемым значением поля,* за­тем считывается номер соответствующей строки (строк) в ис­ходной таблице и далее по нему уже осуществляется непосред­ственный доступ к искомой строке базовой таблицы.

* Способы поиска в линейно упорядоченных структурах см., например, в работе: Вирт Н.. Алгоритмы и структуры данных: Пер. с англ.—М.: Мир, 1989.

При добавленииновой строки в базовую таблицу ее значение по индексируемому полю ищется в ранее составленном индексе. Если соответствующая строка инвертированного спис­ка отыскивается (т.е. подобное значение индексируемого поля среди строк таблицы уже встречалось и было поставлено на учет), то в ячейку второго столбца соответствующей строки индекса дописывается номер страницы, куда была помещена соответствующая строка базовой таблицы. Если такого значе­ния в индексе нет, то создается новая строка индекса и осуще­ствляется переупорядочение нового состояния индексного мас­сива.

При удалениистроки из базовой таблицы также осуществ­ляется поиск соответствующей строки в индексном массиве и осуществляется вычеркивание в индексе соответствующего номера отсылаемой строки базовой таблицы. Если при этом других строк в базовой таблице с таким же значением индекси­руемого поля не осталось (соответствующая ячейка индекса стала пустой), то удаляется и вся данная строка индекса с пос­ледующим переупорядочением всего индексного массива. При этом за счет того, что индекс в виде инвертированного списка содержит лишь один столбец значений, затраты на «перетряс­ку» при добавлении или удалении записей существенно мень­ше по сравнению с тем, если бы переупорядочение происходи­ло непосредственно в самой базовой таблице.*

* Кроме того, строки базовой таблицы можно упорядочивать только лишь по какому-либо одному полю, а индексные массивы можно создавать сразу по нескольким полям.

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

Нелинейные структуры индексовприменяются для созда­ния индексных массивов ключевых полей или тех полей, значения по которым не повторяются. При организации индексов в таких случаях чаще всего используются уже упоминавшиеся древовидные иерархические структуры в видеБ-деревьев. Б-дерево представляет собой корневое сбалансированное силь­но ветвистое дерево.

Каждая внутренняя вершина, если она полностью запол­нена, содержит информацию о n–1 различных последователь­но возрастающих значениях индексируемого поля по следую­щей схеме, приведенной на рис. 2.17.

где: Х_i – i-езначение индексируемого поля, при этом Х_iJX_i+1 –указатель на вершину, содержащую значения индексируе­мого поля, меньшие или равныеX_i.

Рис. 2.17. Структура внутренней вершины Б-дерева

Число nназываетсяпорядкомБ-дерева.

Листовая вершина, в отличие от внутренней, содержит ин­формацию о нахождении страницы в файле базы данных с за­писями-кортежами, имеющими соответствующие значения ин­дексируемого поля. Схема листовой страницы представлена на рис.2.18.

где: Р_k–указатель на страницу файла данных, содержащую строку (строки) со значением индексируемого поля, равнымХ_k.

Рис. 2.18. Структура листовой вершины Б-дерева

СбалансированностьБ-дерева означает одинаковое количество потомков до листовой вершины по любым раз­ветвлениям от корневой вершины. В качестве примера на рис. 2.19 приведено Б-дерево 3-го порядка уровня 2, пост­роенное для поля «Год рождения» таблицы «Сотрудники».

Рис. 2.19. Пример Б-дерева 3-го порядки уровня 2

Как правило, порядок Б-дерева выбирается таким, что­бы информация одной полностью заполненной вершины соответствовала странице файла данных. В силу того что объем одной страницы файлов данных существенно боль­ше размера полей, то в большинстве случаев в одну пол­ностью заполненную страницу вместе с указателями по­мещается большое количество значений индексируемого поля, исчисляемое сотнями и даже тысячами значений (n >> 100...1000). Это обстоятельство обусловливает сравни­тельно небольшой уровень Б-деревьев на практике (поряд­ка 2...4) даже в тех случаях, когда количество строк в ба­зовой таблице исчисляется десятками тысяч. В результате доступ к нужной записи по определенному значению ин­дексируемого поля через Б-дерево осуществляется за небольшое количество страничных обменов между внутрен­ней и внешней памятью по следующему алгоритму:

— в оперативную память из внешней считывается страни­ца с корневой вершиной и последовательно просматривается до первого значения, превышающего значение индексируемого поля нужной записи. При этом определяется ссылка (номер) страницы-потомка (внутренней или листовой);

— в оперативную память считывается страница-потомок. Если она внутренняя, то ее обработка производится аналогич­но корневой. Если страница-потомок является листовой, то она последовательно просматривается до нахождения нужного зна­чения индексируемого поля. При этом определяется номер стра­ницы файла данных, которая содержит нужную запись;

— если при просмотре листовой страницы нужное значе­ние индексируемого поля не находится, то поиск считается от­рицательным, т. е. принимается решение о том, что строки-кор­тежа с требуемым значением индексируемого поля в таблице-отношении (файле данных) нет.

Анализ данного алгоритма показывает, что при поиске нуж­ного значения индексируемого поля по индексу в виде Б-дерева требуется такое количество страничных обменов между внеш­ней и внутренней памятью, которое равно уровню Б-дерева плюс единица. При достаточно большом значении n, а это, как уже отмечалось, наиболее распространенная ситуация, уровеньmБ-дерева невелик (m >> 2..3),и, следовательно, количество страничных индексных обменов с памятью также невелико. При этом сбалансированность Б-дерева обусловливает одинаковые затраты по доступу к любой записи с любым значением индек­сируемого поля.СбалансированностьБ-деревьев обеспечива­ется легко алгоритмизируемым правилом их построения (рос­та) при включении нового значения индексируемого поля.

Включениенового значения индексируемого поля осуще­ствляется следующим образом.

• Производится поиск требуемого значения в существую­щем Б-дереве. При его отсутствии поиск, естественно, закан­чивается отрицательным результатом, но в оперативной памя­ти остается листовая страница, куда, следовательно, и необхо­димо поместить новое значение индексируемого поля.

• Если листовая страница не заполнена полностью, в нее записывается новое значение индексируемого поля и указатель на страницу файла данных, содержащую соответствующую за­пись (строку таблицы).

• Если листовая страница уже заполнена, то она делится «пополам», и тем самым порождается новая листовая страни­ца. Среднее значение исходной листовой страницы записыва­ется в вершину-предок на соответствующее место.*При этом после вставленного значения образуется указатель-ссылка на новую листовую страницу, образованную остатком от ополо­виненной исходной листовой страницы.

*Так, чтобы в странице обеспечивался последовательный порядок расположе­ния -значений индексируемого поля по схеме, приведенной на рис. 2.17.

• Если при занесении среднего значения переполненной листовой страницы в страницу-предок происходит переполне­ние самой страницы-предка, то она аналогично делится попо­лам, «посылая» свое среднее значение своему предку. Если при этом происходит переполнение корневой страницы, то она так­же делится на две новые внутренние страницы, а ее среднее значение образует новую корневую страницу, повышая уровень дерева на единицу и т. д. (говорят, что Б-дерево «растет» вверх).

Удалениеопределенного значения индексируемого поля производится следующим образом:

• Производится поиск требуемого значения индексируе­мого поля и в результате в оперативную память считывается нужная листовая страница.

• Из нее удаляется соответствующее значение индексиру­емого поля и указатель-адрес соответствующей страницы фай­ла данных.

• Если после удаления размер занятого пространства па­мяти текущей листовой страницы в сумме с размером занятого пространства левого (правого) брата больше, чем размер памя­ти одной страницы, то процесс заканчивается.

• В противном случае текущая листовая страница объеди­няется с левым (правым) братом. Тем самым одна из листовых страниц (левая или правая) опустошается и уничтожается. В вершине-предке удаляется значение индексируемого поля, ука­затель перед которым или после которого ссылался на опустошенную листовую страницу. При этом может, в свою очередь, возникнуть необходимость слияния и опустошения уже внут­ренних страниц, которое осуществляется аналогичным обра­зом.

Описанный алгоритм удаления значений индексируемого поля соответствует одной из наиболее широко применяемых разновидностей Б-деревьев—Б*-деревьев,которые позволя­ют использовать в среднем до 2/3 пространства всех страниц (вершин) дерева.

Структура Б-деревьев является эффективным способом ин­дексации больших массивов данных и широко применяется в современных СУБД.