ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ ДАННЫХ. МЕХАНИЗМЫ РАЗМЕЩЕНИЯ ДАННЫХ И ДОСТУПА К ДАННЫМ

Файлы с неплотным индексом, или индексно-последовательные файлы

Неплотный индекс строится именно для упорядоченных файлов. Для этих файлов используется принцип внутреннего упорядочения для уменьшения количества хранимых индексов. Структура записи индекса для таких файлов имеет следующий вид:

Значение ключа первой записи блока Номер блока с этой записью

В индексной области ищется нужный блок по заданному

значению первичного ключа. Так как все записи

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

области.

31

Пример заполнения индексной и основной области при
организации неплотного индекса, если первичным ключом
являются целые числа.	32

ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ ДАННЫХ. МЕХАНИЗМЫ РАЗМЕЩЕНИЯ ДАННЫХ И ДОСТУПА К ДАННЫМ

Рассмотрим процедуры добавления и удаления новой записи при подобном индексе.

Здесь новая запись должна заноситься сразу в требуемый блок на требуемое место, которое определяется заданным принципом упорядоченности на множестве значений первичного ключа. Поэтому сначала ищется требуемый блок основной памяти, в который надо поместить новую запись, а потом этот блок считывается, затем в оперативной памяти корректируется содержимое блока и он снова записывается на диск на старое место. Здесь, так же как и в первом случае, должен быть задан процент первоначального заполнения блоков, но только применительно к основной области. В MS SQL server этот процент называется Full-factor и используется при формировании кластеризованных индексов.

Кластеризованными называются как раз индексы, в которых исходные записи физически упорядочены по значениям первичного ключа. При внесении новой записи индексная область не корректируется. Уничтожение записи происходит путем ее физического удаления из основной области, при этом индексная область обычно не корректируется, даже если удаляется первая запись блока. Поэтому количество обращений к диску при удалении записи такое же, как и при добавлении новой записи.

33

ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ ДАННЫХ. МЕХАНИЗМЫ РАЗМЕЩЕНИЯ ДАННЫХ И ДОСТУПА К ДАННЫМ

Организация индексов в виде B-tree (В-деревьев)

Построение В-деревьев связано с простой идеей построения индекса над уже построенным индексом. Действительно, если мы построим неплотный индекс, то сама индексная область может быть рассмотрена нами как основной файл, над которым надо снова построить неплотный индекс, а потом снова над новым индексом строим следующий и так до того момента, пока не останется всего один индексный блок.

Мы в общем случае получим некоторое дерево, каждый родительский блок которого связан с одинаковым количеством подчиненных блоков, число которых равно числу индексных записей, размещаемых в одном блоке. Количество обращений к диску при этом для поиска любой

записи одинаково и равно количеству уровней в построенном дереве.

Такие деревья называются сбалансированными (balanсed) именно потому, что путь от корня до любого листа в этом древе одинаков. Именно термин "сбалансированное" от английского "balanced" — "сбалансированный, взвешенный" и дал название данному методу организации индекса.

34

Построенное В-дерево

35

ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ ДАННЫХ. МЕХАНИЗМЫ РАЗМЕЩЕНИЯ ДАННЫХ И ДОСТУПА К ДАННЫМ

В том случае, если каждому значению индекса соответствует

уникальное значение ключа, такой индекс

называется первичным.

Если же индекс строится по ключу, допускающему дубликаты значений, такой индекс называется вторичным. Для

каждой БД можно одновременно поддерживать несколько

первичных и вторичных индексов, что также относится к достоинствам индексирования.

Различают одиночные индексы и составные.

Составной индекс включает два или более столбца одной таблицы. Последовательность вхождения столбцов в индекс определяется при создании индекса.

36

ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ ДАННЫХ. МЕХАНИЗМЫ РАЗМЕЩЕНИЯ ДАННЫХ И ДОСТУПА К ДАННЫМ

Многоуровневые индексы на основе В-дерева

Типичное В–дерево содержит три уровня: корневую вершину, промежуточную вершину и листья, хотя способно включать и промежуточное количество уровней.

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

B-дерево строится динамически по мере заполнения базы данными. Оно растёт вверх, и корневая вершина может меняться. Параметрами B-дерева являются порядок n и количество уровней. Порядок – это количество ссылок из вершины i-го уровня на вершины (i+1)-го уровня.

Каждое B-дерево должно удовлетворять следующим условиям:

1. Каждая вершина может содержать n адресных ссылок и (n-1) ключей. Ссылка влево от ключа обеспечивает переход к вершине дерева с меньшими по значению ключами, а вправо – к вершине с большими ключами.

2.Любая неконечная вершина имеет не менее n/2 подчинённых вершин.

3.Если неконечная вершина содержит k (k € n) ключей, то ей подчинена (k+1) вершина на следующем уровне иерархии.

4.Все конечные вершины расположены на одном уровне.

37

57 81 95

К

следующему

ключу

К записи	К записи с	К записи
с ключом	ключом 81	с ключом
57		95

Типичная вершина-лист В – дерева

Пример построения B-дерева порядка 3

38

57

81

95

К записи с ключом К 95

К ключам К<57 К ключам	К ключам
57 К<81	81 К<95

Промежуточная вершина В–дерева

Пример построения B-дерева порядка 3

39

Пример индексного блока СУБД Oracle

40