Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Дроздов С. Методичка. Сортировка и поиск.doc
Скачиваний:
99
Добавлен:
02.05.2014
Размер:
561.66 Кб
Скачать
    1. Использование b-деревьев в базах данных

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. Специальные методы сортировки и поиска

В предыдущих разделах задачи сортировки и поиска рассматривалась в предположении, что в качестве ключа могут использоваться данные любого типа с единственным ограничением: на множестве значений ключа определено некоторое отношение линейного порядка, т.е., проще говоря, для любой пары значений справедливо одно из отношений: <,=или>. Больше никаких предположений о множестве ключей не делалось.

Такой подход хорош своей универсальностью. Рассмотренные алгоритмы работают одинаково эффективно для числовых, строковых и других ключей. В некоторых библиотеках имеются даже стандартные функции сортировки (чаще всего QuickSort) и поиска (бинарного), которые в качестве одного из параметров принимают произвольную функцию сравнения ключей, возвращающую значения –1, 0, +1, что означает результат сравнения соответственно<,=,>.

Платой за универсальность являются ограничения скорости алгоритмов. Мы показали, что для сортировки наилучшая оценка времени есть Tmax(n) = O(n·log(n)), для поиска –Tmax(n) = O(log(n)), и лучших оценок нельзя получить в принципе.

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