Использование B-деревьев в базах данных

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

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

Рис. 4.11.Файловая структура базы данных

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

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

Вопросы и упражнения

1. Для алгоритма поиска со вставкой по дереву можно применить ту же идею барьера, которая рассматривалась для линейного поиска в массиве (п. 2.1). Как для этого нужно изменить структуру данных дерева и текст процедуры поиска?

2. Докажите, что длины всех ветвей ИС-дерева различаются не более, чем на 1.

3. Можно ли при удалении вершины дерева поиска, имеющей двух сыновей, вместо ближайшей вершины слева использовать ближайшую справа?

4. Докажите, что число листьев для наихудших АВЛ-деревьев при увеличении высоты дерева образует последовательность Фибоначчи.

5. Напишите фрагмент программы, выполняющий поворот в АВЛ-дереве для случая 2.

6. Сформулируйте алгоритм вставки в B+-дерево, исходя из примера B+-дерева на рис. 4.10.

7. Известна модификация страничных деревьев поиска, называемая B++-деревьями. Для этих деревьев каждая страница, кроме корня, заполнена не менее, чем на 3/4. Объясните, как должна работать вставка в B++-дерево и сколько ключей может содержать корень такого дерева.

8. Чем отличается операция изменения значения ключевого поля записи базы данных от изменения неключевого поля?