Индексно-последовательный файл

Отсортированный файл данных с первичным индексом называется индексированным последовательным файлом, или индексно-последовательным файлом.

ВТОРИЧНЫЙ ИНДЕКС

Вторичный индекс также является отсортированным файлом, аналогичным первичному индексу.

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

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

б) создание вторичного индекса со значениями для всех уникальных значений ключа. Указатели блоков являются многозначными

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

МНОГОУРОВНЕВЫЕ ИНДЕКСЫ

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

Данный способ достаточно часто реализуется в СУБД, при этом на практике обычно ограничиваются не более чем тремя уровнями, поскольку большее количество уровней требуется только для исключительно больших файлов.

Лекция 15

ДЕРЕВЬЯ

Видимо, наиболее популярным подходом к организации индексов в базах данных является использование техники B+-деревьев. С точки зрения внешнего логического представления B+-дерево - это сбалансированное сильно ветвистое дерево во внешней памяти. Сбалансированность означает, что длина пути от корня дерева к любому его листу одна и та же. Ветвистость дерева - это свойство каждого узла дерева ссылаться но большое число узлов-потомков. При этом максимальное количество узлов-потомков называется порядком дерева.

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

В типовом случае структура внутренней страницы выглядит следующим образом:
(Ссылка1, Ключ1, Ссылка2, Ключ2, … Ключn),
где
а) Ключ1 < Ключ2 < ... < Ключn;
б) Ссылкаi указывает на внутреннюю страницу для вершины дерева следующего уровня, которая содержит ключи со значениями, меньшими или равными Ключi. Таким образом, Ссылкаi+1 указывает на внутреннюю страницу, которая содержит ключи со значениями, большими, чем Ключi.

Листовая страница обычно имеет следующую структуру:
(Список1, Ключ1, Список2, Ключ2, … Списокn, Ключn),
где
а) Ключ1 < Ключ2 < ... < Ключn;
б) Списокi - список ссылок на строки таблицы, включающих значение Ключi;
в) листовые страницы представляют собой одно- или двунаправленный список.

Поиск в B+-дереве - это прохождение от корня к листу в соответствии с заданным значением ключа. Самостоятельно предложите эффективный алгоритм поиска в B+-дереве.

Так как B+ - сбалансированное дерево, то для выполнения поиска по любому значению ключа потребуется одно и то же число обменов с внешней памятью (страницы считываются в память целиком), оцениваемое величиной logn(m), где n – порядок дерева, а m – количество хранимых записей с разным значением ключа индексирования.

Строение B+-дерева позволяет использовать эффективный алгоритм автоматического поддержания свойства сбалансированности при добавлении и удалении записей.

Действия при добавлении новой записи.
1. Поиск ключа добавляемой записи в дереве.
2. Добавление нового ключа в дерево:

а) ключ существует – ссылка на добавляемую запись помещается в соответствующий Списокi листовой страницы. На этом алгоритм добавления закончил работу.

б) ключ отсутствует в дереве: если значение ключа превосходит все уже существующие, для него выделяется новая страница из списка свободных. Иначе ключ помещается на существующую страницу в найденное положение, При этом, если страница переполнена, то также выделяется новая страница, на которую помещается половина данных исходной страницы.

3. Если была добавлена новая страница, вносятся изменения на родительскую страницу для исходной в соответствии с шагом 2 (добавляется ссылка и ключ новой страницы в родительскую для исходной, при этом аналогично обрабатывается случай переполнения).

4. При переполнении корневой страницы B-дерева, она тоже расщепляется на две, и формируется новая корневая страница дерева, родительская для двух новых.

Действия при удалении записи.

1. Поиск ключа удаляемой записи в дереве.

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

3. . Если после удаления сумма размера текущей страницы с размером страницы слева или справа больше n, то алгоритм закончил работу. Иначе производится перемещение данных текущей страницы соответственно в правую или левую. Освободившаяся страница заносится в список свободных страниц. Корректируется связный список листовых страниц.

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

5. Если в корневой странице остался один элемент, корневая страница освобождается (стала ненужной), а новой корневой становится единственная вершина бывшего первого уровня.

Таким образом, при выполнении операций вставки и удаления свойство сбалансированности B-дерева сохраняется, а внешняя память расходуется достаточно экономно.

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

1. Упреждающие расщепления, т.е. расщепления страницы не при ее переполнении, а несколько раньше, когда степень заполненности страницы достигает некоторого уровня;

2. Переливания, т.е. поддержание равновесного заполнения соседних страниц;

3. Слияния 3-в-2, т.е. порождение двух листовых страниц на основе содержимого трех соседних.

ЯЗЫКИ ЗАПРОСОВ К БАЗЕ ДАННЫХ

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

Операции, выполняемые над отношениями, можно разделить на две группы. Первую группу составляют операции над множествами (теоретико – множественные операции), к которым относятся операции: объединения, пересечения, разности, деления и декартова произведения. Вторую группу составляют специальные операции над отношениями, к которым, в частности, относятся операции: проекции, соединения, выбора. В различных СУБД реализована некоторая часть операций над отношениями, определяющая в какой-то мере возможности данной СУБД и сложность реализации запросов к БД.

В реляционных СУБД для выполнения операций над отношениями используются две группы языков, имеющие в качестве своей математической основы теоретические языки запросов, предложенные Э.Коддом:
- реляционная алгебра;
- реляционное исчисление.

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

В реляционной алгебре операнды и результаты всех действий являются отношениями. Языки реляционной алгебры являются процедурными, так как отношение, являющееся результатом запроса к реляционной БД, вычисляется при выполнении последовательности реляционных операторов, применяемым к отношениям. Операторы состоят из операндов, в роли которых выступают отношения, и реляционных операций. Результатом реляционной операции является отношение.

Языки исчислений, в отличие от реляционной алгебры, являются непроцедурными (описательными, или декларативными) и позволяют выражать запросы с помощью предиката первого порядка (высказывания в виде функции), которому должны удовлетворять кортежи или домены отношений. Запрос к БД, выполненный с использованием подобного языка, содержит лишь информацию о желаемом результате. Для этих языков характерно наличие наборов правил для записи запросов. В частности, к языкам этой группы относится SQL.

Лекция 16

РЕЛЯЦИОННЫЙ АЛГЕБРА

Реляционная алгебра описывает выполняемые над отношениями действия. Языки запросов, построенные на основе реляционной алгебры, в современных СУБД широкого распространения не получили. Однако знание реляционной алгебры необходимо для понимания сути действий, происходящих при выполнении любых запросов к реляционным базам данных.