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

⇐ ПредыдущаяСтр 7 из 11Следующая ⇒

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

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

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

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

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

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

Поразрядная сортировка

Рассмотрим сначала несерьезный пример. Дана колода из 32 карт. Требуется отсортировать колоду так, чтобы карты лежали по мастям (например, пики, трефы, бубны, черви), а внутри каждой масти – по убыванию: туз, король, дама, валет, 10, 9, 8, 7.

Предлагается такое решение. Сначала просмотрим один раз колоду, раскладывая карты на 8 стопок по старшинству: тузы, короли, дамы и т.п. Затем соберем стопки опять в одну колоду, но в определенном порядке: сначала тузы, затем короли, дамы и т.д. Теперь еще раз просмотрим колоду от начала до конца, раскладывая карты на 4 стопки по мастям.

Нетрудно понять, что внутри каждой масти карты будут правильно отсортированы. Осталось собрать все масти в требуемом порядке. Сортировка закончена, и она потребовала всего двух проходов по массиву (колоде)! Ну, или максимум – четырех, если сбор нескольких стопок в одну колоду тоже считать проходом.

Заметим еще, что при использовании полной колоды (52 карты) число проходов не изменится, а время выполнения каждого прохода возрастет линейно.

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

1. Ключ состоит из k компонент: x = (x₁, x₂, …, x_k). Для приведенного выше примера с картами ключ состоит из масти и значения. Более серьезный пример – даты, которые состоят из года, месяца и числа.

2. Сортировка выполняется в лексикографическом порядке, т.е. по возрастанию первой компоненты x₁, при равенстве x₁ – по возрастанию x₂ и т.д. Например, даты сортируются по году, внутри одного года – по месяцам, внутри месяца – по числам.

3. Каждая компонента ключа может принимать небольшое число значений, причем желательно последовательных: l_i £ x_i £ h_i. Число этих значений обозначим u_i = l_i - h_i + 1.

Что значит «небольшое число значений»? На практике это означает, что в программе может быть описан (или динамически создан) массив из u_i элементов (от l_i до h_i для каждого i). То есть речь может идти о десятках, сотнях, в крайнем (нежелательном) случае нескольких тысячах значений. В примере с датами число принимает значения от 1 до 31, месяц – от 1 до 12. Сложнее с годом; однако часто можно ограничиться, скажем, датами из XX и XXI вв., тогда число значений равно 200.

В качестве еще одного примера рассмотрим десятичные числа с ограниченным числом разрядов; например, числа от 0 000 000 до 9 999 999. Первую цифру (число миллионов) будем рассматривать как компоненту x₁, вторую цифру – как x₂, последнюю цифру (число единиц) – как x₇. Именно с этим примером связано само название «поразрядная сортировка».

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

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

procedure RadixSort(A);

begin

for i: = k downto 1 do begin

Создать массив пустых линейных списков B[li..hi];

for(каждый элемент d списка A, начиная с головы) do

Перенести d в хвост списка B[v], где v = значение

компоненты ключа xi для записи d;

for v: = li to hi do

Подключить список B[v] в хвост списка A;

end;

Как работает этот алгоритм?

Работа начинается с наименее важной компоненты ключа (в примере с датами это число месяца). Все сортируемые элементы разносятся по спискам в зависимости от значения компоненты (для числа месяца это будут списки от B1 до B31). Список A становится пустым. Далее сливаем все списки Bv в общий список A. Теперь в этом списке будут сначала все даты с числом месяца 1, затем с числом 2 и т.д. до 31. Затем все то же самое повторяется для предыдущей (более важной) компоненты ключа (в примере с датами это номер месяца). После очередного слияния общий список A будет содержать сначала январские даты, потом февральские и т.д. Нетрудно видеть, что при этом внутри каждого месяца сохранится сортировка по числам. Наконец, строятся списки по годам, причем внутри каждого года сохраняется сортированность по месяцам и числам. После слияния этих списков сортировка закончена.

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

Оценим трудоемкость алгоритма. Каждый проход по таблице требует времени порядка O(n). Создание списков и их последующее слияние требуют времени O(u_i). Число проходов равно числу компонент ключа k. Собирая это воедино, получим оценку: .

Заметим, что как k, так и u_i не зависят от n. Полагая эти величины константами, получаем удивительную оценку: T(n) = O(n). Линейная оценка для алгоритма сортировки – об этом, казалось бы, можно только мечтать.

Если поразрядная сортировка так хороша, то зачем мы тогда рассматривали все предыдущие алгоритмы, оценка которых в лучшем случае T(n) = O(n·log(n))?

Давайте рассмотрим, при каких условиях поразрядная сортировка работает столь чудесно. Эти условия были приведены выше: ключ должен состоять из нескольких компонент, каждая из которых принимает небольшое число значений. Хотя при получении оценки «O-большое» мы отбросили k и u_i как константы, слишком большие значения этих констант могут свести на нет преимущества линейной оценки.

Рассмотрим крайний случай: целочисленный четырехбайтовый ключ, не разлагающийся ни на какие компоненты. Формально можно сказать, что k = 1, но тогда u₁ равно мощности множества всех целых чисел выбранной разрядности, т.е. 2³². Создать такое количество списков явно нереально.

Более интересен пример с десятичными числами, разбитыми на разряды. В этом случае все u_i = 10, но k есть максимальное число цифр, которое примерно равно десятичному логарифму максимального допустимого числа. Таким образом, в оценке времени все-таки появляется логарифм, хотя и не совсем тот, что для QuickSort и HeapSort.

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

⇐ Предыдущая 2 3 4 5 678 9 10 11 Следующая ⇒