Б-деревья

До сих пор молчаливо предполагалось, что деревья поиска находятся в оперативной памяти. При увеличении их объема это становится невозможным. Конечно, можно хранить дерево и в файле с прямым доступом. В сбалансированном дереве смещение на один уровень вниз при поиске данных сокращает пространство поиска примерно вдвое, поэтому среднее число шагов поиска пропорционально величине log₂N, где N – количество вершин дерева. Если, например, N=10⁶, то эта величина близка к 20, и нерационально столько раз позиционировать файл. С другой стороны, при прямом доступе позиционирование является самой трудоемкой операцией, а чтение одного или нескольких блоков информации мало отличаются по времени. Эти соображения приводят к потребности блокирования элементов в страницы, что порождает множество вопросов.

Эту проблему удалось решить путем применения Б-деревьев - сильно ветвящихся деревьев поиска, вершинами которых являются страницы элементов.

Б-деревом порядка n называется сильно ветвящееся дерево со следующими свойствами.

1. Каждая страница , кроме корня, содержит не менее n элементов.

2. Каждая страница содержит не более 2n элементов.

3. Если страница не лист и имеет m элементов, то у нее ровно m+1 сын.

4. Если элементы нелистовой страницы с ключами A₁, A₂,…, A_m упорядочены по возрастанию ключей, то поддерево с корнем в первом сыне содержит элементы с ключами, меньшими A₁, поддерево с корнем во втором сыне - с ключами, большими A₁, но меньшими A₂ и т. д.

5. Все листовые страницы находятся на одном уровне.

Ниже приведен пример Б-дерева порядка 2. Этот порядок является тестовым, то есть иллюстрирует все принципы работы с Б-деревьями, позволяя, тем не менее, просматривать результаты вручную. В целях наглядности выбраны числовые значения ключей.

Поиск элемента с заданным ключом проводится по направлению от корня к листьям Б-дерева на основании свойства 4. Число уровней Б-дерева оценивается величиной log_nN, где N – количество элементов дерева. Для рассмотренного случая N=10⁶ эта величина равна 3, то есть по сравнению с бинарным деревом поиска для нахождения элемента требуется перебирать существенно меньшее число вершин.

Включение нового элемента в Б-дерево выполняется следующим образом. Сначала производится поиск листовой страницы, где должен располагаться новый элемент. Если в этой странице менее 2n элементов, то новый элемент добавляется в страницу без изменения структуры дерева. Если же в ней оказывается 2n+1 элемент, то средний по значению ключа элемент отправляется в отцовскую страницу, а элементы, меньшие и большие среднего элемента по значениям ключа, образуют две новые страницы по n элементов. Если в отцовской странице тоже происходит переполнение, то процесс продолжается вверх по дереву. Вытесненный элемент из корневой страницы образует новый корень, увеличивая число уровней дерева. Следовательно, Б-дерево растет снизу вверх.

Рассмотрим следующий пример. Требуется вставить элемент с ключами 7 и 75 в следующее Б-дерево.

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

Начальная организация Б-дерева производится путем последовательного включения элементов. Для Б-дерева второго порядка второй уровень появляется после включения пятого элемента.

Исключение из Б-дерева распадается на несколько случаев. Пусть сначала исключаемый элемент находится на листовой странице дерева. Если на этой странице больше n элементов, то структура дерева не нарушается. Если же на ней ровно n элементов, то элементы этой страницы объединяется с элементами соседней страницей той же отцовской страницы и к ним добавляется элемент из отцовской страницы, ключ которого имеет промежуточное значение между ключами объединяемых страниц.

Если число объединенных элементов окажется не менее 2n+1, то средний элемент располагается в отцовской странице, а элементы, меньшие и большие среднего элемента по значениям ключей, образуют 2 страницы.

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

В качестве примера рассмотрим последнее Б-дерево, полученное после вставки элементов с ключами 7 и 75. При удалении элемента с ключом 36 объединяются элементы с ключами 2, 4, 7, 30, 34. Элемент с ключом 7 отправляется в отцовскую страницу вместо бывшего там элемента с ключом 30, а две измененные листовые страницы будут содержать элементы с ключами 2,4 и 30,34.

Удалим в полученном дереве элемент с ключом 75. Сейчас новую страницу образуют элементы с ключами 65,67,68,69, а в отцовской странице останется единственный элемент с ключом 60, что недопустимо. Этот элемент объединяется с элементами соседней страницы и к ним добавляется элемент с ключом 50 из корня, который остается пустым. После удаления корня дерево примет вид, имевший до вставки элементов с ключами 7 и 75. Число уровней дерева уменьшается с трех до двух.

Если удаляемый элемент находится не в листовой странице, то сначала он замещается любым из двух соседних по значению ключа элементов. Он, очевидно, находится в листовой странице. Пусть элементы каждой страницы отсортированы по возрастанию ключей, и удаляемый элемент имеет номер k в своей странице. Тогда соседними элементами являются наибольший и наименьший по значению ключей элементы поддеревьев, корнями которых являются k-й и k+1-й сын страницы с удаляемым элементом. Далее все сводится к рассмотренной выше процедуре удаления элемента из листовой страницы.

Б-деревья широко применяются для индексации данных. Индексация здесь понимается в более широком смысле как аппарат, обеспечивающий быстрый поиск данных. Почти все современные системы управления базами данных используют идексацию на основе Б-деревьев. Рассмотрим на принципиальном уровне способ индексации с помощью Б-деревьев.

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

Б-дерево представляет собой файл прямого доступа, записями которого являются страницы. В структуре каждой страницы резервируется массивы из 2n элементов для ключей и соответствующих номеров записей исходного файла, а также массив из 2n+1 элемента для ссылок на страницы сыновей. Каждая страница в простейшем случае идентифицируется номером записи в файле, представляющем Б-дерево.

Новая запись дописывается в конец исходного файла, а ее ключ вставляется в Б-дерево с возможной перестройкой последнего. Удаление записи обычно проводят в два этапа. Удаляемая запись помечается в исходном файле без изменения Б-дерева. Доступ к помеченным записям сохраняется, поэтому любая пометка может быть снята. Физическое удаление записей производится отдельной командой. Исходный файл переписывается без помеченных записей, а Б-дерево строится с самого начала. Такой подход обеспечивает большую безопасность удаления и уменьшает трудоемкость перестройки Б-дерева за счет группировки удалений.