Лекция №25

Название лекции: В– деревья.

План:

1. Иерархия индексов как дерево.

2. Соглашения, принятые для организации В–деревьев.

3. Поиск в B- деревьях.

4. Модификация.

5. Включение.

6. Удаление.

1. Иерархия индексов как дерево.

Дать определение – сбалансированные деревья.

Рассмотрим случай незакрепленных записей главного файла. Индекс – это файл с незакрепленными записями. Таким образом, для этого файла можно построить индекс индекса. Далее индекс этого индекса и т.д. пока индекс не поместится в один блок. Такая схема может быть более эффективна, одноуровневый индекс, и называется иерархией индексов.

Общая схема для очень больших файлов основана на иерархии индексов, соответствующей иерархической природе устройств внешней памяти.

Иерархию индексов можно организовать и независимо от иерархии структуры внешних устройств.

Иерархию индексов можно рассматривать как дерево (см. рисунок).

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

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

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

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

Соглашения, принятые для организации В–деревьев.

Для удобства организации индексных файлов в виде В–деревьев положим:

a) число записей индекса, которые могут содержатся в одном блоке, является числом нечетным, и равным 2d-1≥3;

b) максимальное число записей главного файла в одном блоке также нечетное число, равное 2е-1≥3;

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

Рассмотрим функции доступа к главному файлу при использовании В–деревьев.

Дата добавления: 2014-01-05