Лекция №25
Название лекции: В– деревья.
План:
1. Иерархия индексов как дерево.
2. Соглашения, принятые для организации В–деревьев.
3. Поиск в B- деревьях.
4. Модификация.
5. Включение.
6. Удаление.
1. Иерархия индексов как дерево.
Дать определение – сбалансированные деревья.
Рассмотрим случай незакрепленных записей главного файла. Индекс – это файл с незакрепленными записями. Таким образом, для этого файла можно построить индекс индекса. Далее индекс этого индекса и т.д. пока индекс не поместится в один блок. Такая схема может быть более эффективна, одноуровневый индекс, и называется иерархией индексов.
Общая схема для очень больших файлов основана на иерархии индексов, соответствующей иерархической природе устройств внешней памяти.
Иерархию индексов можно организовать и независимо от иерархии структуры внешних устройств.
Иерархию индексов можно рассматривать как дерево (см. рисунок).
Операции поиска, модификации, включения, и удаления над многоуровневыми индексами являются простым обобщением ранее рассмотренных методов. Проблема – если индекс первого уровня превышает размер 1-го блока. Очевидно, что можно добавить ещё один уровень (что не меняет алгоритмов доступа). Таким образом, мы получим сбалансированное дерево, с неопределённым (переменным) числом уровней. Дерево сбалансированное: длина пути от корня до любого листа одинакова.
Для дальнейших рассуждений предполагаем, что записи главного файла не закреплены. Хотя если записи закреплены, то можно, как и в предыдущем случае, считать, что листья в дереве являются первыми блоками участков.
Как и раньше будем считать, что в листе дерева стоит указатель на блок главного файла (случай, когда в листе стоит ссылка на запись главного файла, а не на блок, называется плотным индексом, название от того, что в блоках главного файла нет свободных мест (записи плотно распределены)).
Для операций включения и удаления над В–деревьями можно было бы использовать туже стратегию, что и в предыдущем разделе, применяя операции включения и удаления к узлам (блокам) дерева на всех уровнях. Тогда узлы содержали бы от одной записи до максимально возможного их числа. Для В–деревьев обычно применяется другая стратегия включения и удаления, которая обеспечивает наполняемость всех узлов (за исключением корня) не менее чем на половину.
Соглашения, принятые для организации В–деревьев.
Для удобства организации индексных файлов в виде В–деревьев положим:
a) число записей индекса, которые могут содержатся в одном блоке, является числом нечетным , и равным 2d-1≥3;
b) максимальное число записей главного файла в одном блоке также нечетное число, равное 2е-1≥3;
c) для экономии пространства в блоках индекса В–дерева значения ключа в первой записи опускается. При поиске будем считать, что все значения ключей, меньше значения ключа во второй записи, покрывается его первым значением.
Рассмотрим функции доступа к главному файлу при использовании В–деревьев.