Основы теории. Стандартным приемом повышения эффективности доступа к записям в базах данных является создание индексных массивов по отдельным
Стандартным приемом повышения эффективности доступа к записям в базах данных является создание индексных массивов по отдельным, обычно ключевым полям. Идея индексов основана на том факте, что если для повышения эффективности доступа к конкретному кортежу-записи использовать линейное упорядочение кортежей в таблице (скажем, по алфавиту для текстовых ключевых полей или по возрастанию для числовых ключевых полей), то накладные расходы по «перетряске» всей таблицы после добавления/удаления строк-кортежей превысят выигрыш во времени доступа. Структура индексов (индексных массивов) строится так, чтобы на основе некоторого критерия можно было бы быстро находить по значению индексируемого поля указатель на нужную запись (строку) таблицы и получать к ней доступ. При этом совокупность записей-кортежей базовой таблицы не обязательно упорядочивать, а при их изменении необходимо изменить только лишь индексный массив. Иногда удобно сконструировать индекс так, чтобы он указывал приблизительное, а не точное местоположение нужной информации. Например, это можно реализовать путем хранения каким-либо образом отсортированного последовательного файла в виде нескольких сегментов, содержащих по несколько записей. Затем каждый сегмент представляется в индексе одной записью, обычно значением последнего ключа в сегменте. В результате мы получаем частичный индекс, содержащий только часть ключей, находящихся в файле. Структура частичного индекса показана на рис. 1, где для каждой записи указаны только ключевые поля, причем мы считаем, что в каждом из них хранится по одной букве.
Рисунок 1- Файл с частичным индексом Идею частичного индекса можно применять в структурах данных, как на запоминающих устройствах, так и в оперативной памяти. Например, длинный связный список можно хранить как небольшой список сегментов. В этом случае частичный индекс применяется для нахождения сегмента, содержащего нужную нам запись списка. Такой подход может существенно сократить время, необходимое для поиска записей в списке, так как вместо последовательного поиска во всем связном списке мы проводим поиск в меньшем по размеру сегменте. Как и для информационных массивов самих данных (таблиц), так и для индексных массивов применяются линейные и нелинейные структуры. В качестве линейных структур индексов в большинстве случаев выступают инвертированные списки. Инвертированный список строится по схеме таблицы с двумя колонками — «Значение индексируемого поля» и «Номера строк»* (см. рис. 1). Инвертированные списки чаще всего применяются для индексации полей, значения которых в разных строках-записях могут повторяться, к примеру, поле «Год рождения» таблицы «Сотрудники» (в реляционных базах данных такие поля не могут быть ключевыми).
Строки инвертированного списка упорядочиваются по значению индексируемого поля. Для доступа к нужной строке исходной таблицы сначала в упорядоченном инвертированном списке отыскивается строка с требуемым значением поля, * затем считывается номер соответствующей строки (строк) в исходной таблице и далее по нему уже осуществляется непосредственный доступ к искомой строке базовой таблицы. При добавлении новой строки в базовую таблицу ее значение по индексируемому полю ищется в ранее составленном индексе. Если соответствующая строка инвертированного списка отыскивается (т.е. подобное значение индексируемого поля среди строк таблицы уже встречалось и было поставлено на учет), то в ячейку второго столбца соответствующей строки индекса дописывается номер страницы, куда была помещена соответствующая строка базовой таблицы. Если такого значения в индексе нет, то создается новая строка индекса и осуществляется переупорядочение нового состояния индексного массива. При удалении строки из базовой таблицы также осуществляется поиск соответствующей строки в индексном массиве и осуществляется вычеркивание в индексе соответствующего номера отсылаемой строки базовой таблицы. Если при этом других строк в базовой таблице с таким же значением индексируемого поля не осталось (соответствующая ячейка индекса стала пустой), то удаляется и вся данная строка индекса с последующим переупорядочением всего индексного массива. При этом за счет того, что индекс в виде инвертированного списка содержит лишь один столбец значений, затраты на «перетряску» при добавлении или удалении записей существенно меньше по сравнению с тем, если бы переупорядочение происходило непосредственно в самой базовой таблице. Кроме того, строки базовой таблицы можно упорядочивать только лишь по какому-либо одному полю, а индексные массивы можно создавать сразу по нескольким полям. Индексы в виде инвертированных списков являются особенно эффективными в том случае, когда значения индексируемого поля часто повторяются, образуя равномерные по мощности группы. В этом случае количество ситуаций, при которых требуется добавление или удаление строк индекса, невелико, и затраты на переупорядочение индекса при изменениях данных в базовой таблице незначительны. В результате выигрыш по затратам на доступ существенно превышает накладные расходы по переупорядочению индекса в процессе ведения базы данных. Нелинейные структуры индексов применяются для создания индексных массивов ключевых полей или тех полей, значения по которым не повторяются. При организации индексов в таких случаях чаще всего используются уже упоминавшиеся древовидные иерархические структуры в виде Б-деревьев. Б-дерево представляет собой корневое сбалансированное сильно ветвистое дерево. Каждая внутренняя вершина, если она полностью заполнена, содержит информацию о n–1 различных последовательно возрастающих значениях индексируемого поля по следующей схеме
Рисунок 2- Структура внутренней вершины Б-дерева где: Х i –i-е значение индексируемого поля, при этом Х i J Xi+ 1 – указатель на вершину, содержащую значения индексируемого поля, меньшие или равные X i. Число n называется порядком Б-дерева. Листовая вершина, в отличие от внутренней, содержит информацию о нахождении страницы в файле базы данных с записями-кортежами, имеющими соответствующие значения индексируемого поля.
Рисунок3 -Структура листовой вершины Б-дерева где: Р k – указатель на страницу файла данных, содержащую строку (строки) со значением индексируемого поля, равным Х k. СбалансированностьБ-дерева означает одинаковое количество потомков до листовой вершины по любым разветвлениям от корневой вершины. В качестве примера на рис. 2.19 приведено Б-дерево 3-го порядка уровня 2, построенное для поля «Год рождения» таблицы «Сотрудники».
Рисунок 4- Пример Б-дерева 3-го порядки уровня 2 Как правило, порядок Б-дерева выбирается таким, чтобы информация одной полностью заполненной вершины соответствовала странице файла данных. В силу того что объем одной страницы файлов данных существенно больше размера полей, то в большинстве случаев в одну полностью заполненную страницу вместе с указателями помещается большое количество значений индексируемого поля, исчисляемое сотнями и даже тысячами значений (n > > 100...1000). Это обстоятельство обусловливает сравнительно небольшой уровень Б-деревьев на практике (порядка 2...4) даже в тех случаях, когда количество строк в базовой таблице исчисляется десятками тысяч. В результате доступ к нужной записи по определенному значению индексируемого поля через Б-дерево осуществляется за небольшое количество страничных обменов между внутренней ивнешней памятью по следующему алгоритму: в оперативную память из внешней считывается страница с корневой вершиной и последовательно просматривается до первого значения, превышающего значение индексируемого поля нужной записи. При этом определяется ссылка (номер) страницы-потомка (внутренней или листовой); в оперативную память считывается страница-потомок. Если она внутренняя, то ее обработка производится аналогично корневой. Если страница-потомок является листовой, то она последовательно просматривается до нахождения нужного значения индексируемого поля. При этом определяется номер страницы файла данных, которая содержит нужную запись; если при просмотре листовой страницы нужное значение индексируемого поля не находится, то поиск считается отрицательным, т. е. принимается решение о том, что строки-кортежа с требуемым значением индексируемого поля в таблице-отношении (файле данных) нет. Анализ данного алгоритма показывает, что при поиске нужного значения индексируемого поля по индексу в виде Б-дерева требуется такое количество страничных обменов между внешней и внутренней памятью, которое равно уровню Б-дерева плюс единица. При достаточно большом значении n, а это, как уже отмечалось, наиболее распространенная ситуация, уровень m Б-дерева невелик (m > > 2..3), и, следовательно, количество страничных индексных обменов с памятью также невелико. При этом сбалансированность Б-дерева обусловливает одинаковые затраты по доступу к любой записи с любым значением индексируемого поля. Сбалансированность Б-деревьев обеспечивается легко алгоритмизируемым правилом их построения (роста) при включении нового значения индексируемого поля. Включение нового значения индексируемого поля осуществляется следующим образом. Производится поиск требуемого значения в существующем Б-дереве. При его отсутствии поиск, естественно, заканчивается отрицательным результатом, но в оперативной памяти остается листовая страница, куда, следовательно, и необходимо поместить новое значение индексируемого поля. Если листовая страница не заполнена полностью, в нее записывается новое значение индексируемого поля и указатель на страницу файла данных, содержащую соответствующую запись (строку таблицы). Если листовая страница уже заполнена, то она делится «пополам», и тем самым порождается новая листовая страница. Среднее значение исходной листовой страницы записывается в вершину-предок на соответствующее место. При этом после вставленного значения образуется указатель-ссылка на новую листовую страницу, образованную остатком от ополовиненной исходной листовой страницы. Так, чтобы в странице обеспечивался последовательный порядок расположения -значений индексируемого поля по схеме. Если при занесении среднего значения переполненной листовой страницы в страницу-предок происходит переполнение самой страницы-предка, то она аналогично делится пополам, «посылая» свое среднее значение своему предку. Если при этом происходит переполнение корневой страницы, то она также делится на две новые внутренние страницы, а ее среднее значение образует новую корневую страницу, повышая уровень дерева на единицу и т. д. (говорят, что Б-дерево «растет» вверх). Удаление определенного значения индексируемого поля производится следующим образом: Производится поиск требуемого значения индексируемого поля и в результате в оперативную память считывается нужная листовая страница. Из нее удаляется соответствующее значение индексируемого поля и указатель-адрес соответствующей страницы файла данных. Если после удаления размер занятого пространства памяти текущей листовой страницы в сумме с размером занятого пространства левого (правого) брата больше, чем размер памяти одной страницы, то процесс заканчивается. В противном случае текущая листовая страница объединяется с левым (правым) братом. Тем самым одна из листовых страниц (левая или правая) опустошается и уничтожается. В вершине-предке удаляется значение индексируемого поля, указатель перед которым или после которого ссылался на опустошенную листовую страницу. При этом может, в свою очередь, возникнуть необходимость слияния и опустошения уже внутренних страниц, которое осуществляется аналогичным образом. Описанный алгоритм удаления значений индексируемого поля соответствует одной из наиболее широко применяемых разновидностей Б-деревьев—Б*-деревьев, которые позволяют использовать в среднем до 2/3 пространства всех страниц (вершин) дерева. Структура Б-деревьев является эффективным способом индексации больших массивов данных и широко применяется в современных СУБД. Рассмотрим, например, следующий массив: char p[10];Следующие два выражения идентичны: p& p[0]Выражение p == & p[0]принимает значение ИСТИНА, потому что адрес 1-го элемента массива — это то же самое, что и адрес массива. Как уже указывалось, имя массива без индекса представляет собой указатель. И наоборот, указатель можно индексировать как массив. Рассмотрим следующий фрагмент программы: int *p, i[10]; p = i; p[5] = 100; /* в присваении используется индекс */*(p+5) = 100; /* в присвоении используется адресная арифметика */Оба оператора присваивания заносят число 100 в 6-й элемент массива i. Первый из них индексирует указатель p, во втором применяются правила адресной арифметики. В обоих случаях получается один и тот же результат. Можно также индексировать указатели на многомерные массивы. Например, если а — это указатель на двухмерный массив целых размерностью 10× 10, то следующие два выражения эквивалентны: a& a[0][0]Более того, к элементу (0, 4) можно обратиться двумя способами: либо указав индексы массива: а[0][4], либо с помощью указателя: *((int*)а+4). Аналогично для элемента (1, 2): а[1][2] или *((int*)а+12). В общем виде для двухмерного массива справедлива следующая формула: a[j][k] эквивалентно *((базовый_тип *)а+(j* длина_строки)+k)Правила адресной арифметики требуют явного преобразования указателя на массив в указатель на базовый тип. Указатели используются для обращения к элементам массива потому, что часто операции адресной арифметики выполняются быстрее, чем индексация массива. Двухмерный массив может быть представлен как указатель на массив одномерных массивов. Добавив еще один указатель, можно с его помощью обращаться к элементам отдельной строки массива. Этот прием демонстрируется в функции pr_row(), которая печатает содержимое конкретной строки двухмерного глобального массива num: int num[10][10]; /*... */ void pr_row(int j){ int *p, t; p = (int *) & num[j][0]; /* вычисление адреса 1-го элемента строки номер j */ for(t=0; t< 10; ++t) printf(" %d ", *(p+t)); }Эту функцию можно обобщить, включив в список аргументов номер строки, длину строки и указатель на 1-й элемент: void pr_row(int j, int row_dimension, int *p){ int t; p = p + (j * row_dimension); for(t=0; t< row_dimension; ++t) printf(" %d ", *(p+t)); } /*... */ void f(void){ int num[10][10]; pr_row(0, 10, (int *) num); /* печать 1-й строки */}Такой прием " понижения размерности" годится не только для двухмерных массивов, но и для любых многомерных. Например, вместо того, чтобы работать с трехмерным массивом, можно использовать указатель на двухмерный массив, причем вместо него в свою очередь можно использовать указатель на одномерный массив. В общем случае вместо того, чтобы обращаться к n -мерному массиву, можно работать с указателем на (n-1)-мерный массив. Причем этот процесс понижения размерности кончается на одномерном массиве.
|
