B-дерево (дерево многоканального поиска): различия между версиями

Ключевые слова и синонимы: [[Дерево многоканального поиска|деревья многоканального поиска]]

В 1972 году Байером и Маккрейтом был введен класс [[B-Дерево|B-деревьев]] как одного из способов реализации «индекса динамически меняющегося файла с произвольным доступом» [6, стр. 173]. С тех пор B-деревья получили широкое распространение в контексте работы с базами данных и в сообществе разработчиков алгоритмов; одним из свидетельств их быстрого и широкого принятия может служить тот факт, что авторитетный обзор B-деревьев за авторством Комера [9] появился уже в 1979 году и описывал структуру данных B-дерева как «вездесущую».

'''Определение 1.''' Пусть <math>m \ge 3</math> – целое положительное число. Дерево T представляет собой ''[[B-дерево степени m]]'', если оно пусто или удовлетворяет следующим условиям:

Чтобы произвести поиск по B-дереву для заданного ключа x, алгоритм начинает с корня дерева, которым является текущая вершина. Если x соответствует одному из ключей текущей вершины, поиск успешно завершается. В противном случае, если текущая вершина представляет собой лист, поиск завершается неуспешно. Если ключи текущей вершины не содержат x, а текущая вершина не является листом, алгоритм определяет уникальное поддерево с корнем в потомке текущей вершины, которое может содержать x, и рекурсивно исполняется для этого поддерева. Поскольку процесс поиска управляется ключами вершины, они также называются ''элементами маршрутизации (routing elements)''.

Кнут [16] определяет ''[[B*-дерево]]'' как B-дерево, для которого свойство 3 определения 1 меняется следующим образом: каждая вершина, помимо корневой, содержит не менее 2m/3 ключей.

''B<math>^+</math>-дерево'' представляет собой ''[[листовое B-дерево]]'', то есть B-дерево, в котором ключи хранятся только в листьях. Кроме того, листья привязываются по порядку слева направо, что позволяет осуществлять быстрый последовательный обход ключей, хранящихся в дереве. Элементы маршрутизации в листовом дереве обычно являются копиями определенных ключей, хранящихся в листьях (ключ <math>key_i[v] \; </math> может быть установлен равным максимальному ключу, хранящемуся в поддереве с корнем в <math>c_i[v] \; </math>), однако вполне подойдет любой набор элементов маршрутизации, для которого выполняются свойства 5 и 6 определения 1.

Хаддлстон и Мельхорн [13] расширили определение 1 для описания более общего класса деревьев многоканального поиска, включающего класс B-деревьев в качестве частного случая. Введенный ими класс так называемых ''[[(a, b)-Дерево|(a, b)-деревьев]]'' параметризован двумя целыми числами a и b, удовлетворяющими условиям: <math>a \ge 2 \; </math> и <math>2a \; </math>— <math>1 \le b \; </math>. Свойство 2 определения 1 изменяется таким образом, что каждая вершина может иметь до b потомков, а свойство 3 теперь гласит, что все вершины (a; b)-дерева, за исключением корня и листьев, имеют по меньшей мере a потомков. Остальные свойства определения 1 в случае (a, b)-деревьев остаются неизменными. Обычно (a, b)-деревья реализуются как листовые деревья.

Согласно этому определению, B-дерево представляет собой (b/2; b)-дерево, если b является четным, или (a; 2a – 1)-дерево (для нечетных b). Небольшое различие между четной и нечетной максимальной степенью приобретает значимость в контексте важного утверждения Хаддлстона и Мельхорна об амортизации (см. ниже), в котором должно выполняться неравенство <math>b \ge 2 \; </math>. Это утверждение в конечном итоге привело к тому, что (a, b)-деревья с <math>b \ge 2a \; </math> получили специальное название – ''[[слабые B-деревья]]'' [13].

Поскольку B-деревья представляют собой основную индексную структуру для внешнего хранения, результаты приводятся не только в форме RAM-модели вычислений, но и в форме I/O-модели (модели ввода-вывода), введенной Аггарвалом и Виттером [1]. В I/O-модели неконстантными параметрами являются не только количество элементов в экземпляре задачи (N), но и количество элементов, которые могут одновременно храниться в основной памяти (M), и количество элементов, помещающихся в один блок диска (B), а мерой сложности является количество операций ввода-вывода (I/O), необходимых для решения данного экземпляра задачи. Если B-деревья используются в структуре внешней памяти, степень B-дерева (m) обычно выбирается таким образом, чтобы одна вершина помещалась в один блок диска, то есть <math>m \in \Theta(B) \; </math>, и это неявно предполагается везде, где рассматривается I/O-сложность B-деревьев.

 

 

'''Теорема 2 ([18]).''' Использование памяти большими B-деревьями высокого порядка при условии случайных вставок и удалений составляет приблизительно <math>ln 2 \approx 69 \% </math>.

 

 

'''Теорема 3.''' B-дерево может использоваться для реализации абстрактного типа данных Dictionary, такого, что операции Find, Insert и Delete на множестве из N элементов из линейно упорядоченной области определений могут быть выполнены за время <math>O(log N) \; </math> (и <math>O(log_B N) \; </math> операций ввода-вывода) в худшем случае.

Одномерный ''запрос диапазона'' ищет все ключи, попадающие в заданный диапазон запросов.

 

 

'''Лемма 1.''' B-дерево поддерживает одномерные запросы диапазонов с временной сложностью <math>O(log N + K) \; </math> (и <math>O(log_B N + K/B) \; </math> операций ввода-вывода) в худшем случае, где K – количество возвращаемых ключей.

В рамках соглашения о том, что каждое обновление B-дерева создает новую «версию» B-дерева, ''мультиверсионное'' B-дерево (''multiversion B-tree'') представляет собой B-дерево, позволяющее вносить обновления в текущую версию и одновременно поддерживающее запросы к более ранним версиям.

 

'''Теорема 4 ([8]).''' Мультиверсионное B-дерево может быть построено из B-дерева таким образом, что оно будет оптимальным относительно сложности операций Find, Insert и Delete в худшем случае, а также относительно сложности ответа на запросы диапазонов в худшем случае.

'''Базы данных'''

 

 

 

 

'''Очереди с приоритетами'''

'''Лемма 2.''' Реализация очереди с приоритетами, использующая B-дерево, поддерживает операцию взятия минимума Min, выполняемую за время <math>O(1) \; </math> (с <math>O(1) \; </math> операций ввода-вывода). Все остальные операции (включая операцию понижения ключа DecreaseKey) имеют временную сложность <math>O(log N) \; </math> (и количество операций ввода-вывода <math>O(log_B N)) \; </math> в худшем случае.

 

 

Мельхорн [17, глава III, 5.3.1] исследовал B-деревья (и более общий случай – (a, b)-деревья с <math>a \ge 2 \; </math> и <math>b \ge 2a \; </math> <math>- 1 \; </math>) в контексте очередей с приоритетами, допускающих слияние. ''Очереди, допускающие слияние'', представляют собой очереди с приоритетами, для которых можно выполнять сцепление и расщепление.  

 

Сцепление очередей с приоритетами для множества <math>S_1 \ne \empty \; </math> и множества <math>S_2 \ne \empty \; </math> определяется только для случая, если <math>max \; </math> {<math>x | x \in S_1</math>} <math>< min \; </math> {<math>x | x \in S_2 \; </math>}, в результате чего получается одна очередь с приоритетами для <math>S_1 \cup S_2</math>. Расщепление очереди с приоритетами для множества <math>S_3 \ne \empty \; </math> в соответствии с некоторым <math>y \in dom(S_3) \; </math> приводит к появлению очередей с приоритетами для множества <math>S_4 := \; </math> {<math>x \in S_3 | x \le y \; </math>} и для множества <math>S_5 := \; </math>{<math>x \in S_3 | x > y \; </math>} (одно из этих множеств может быть пустым). Результат Мельхорна, переформулированный в контексте B-деревьев, выглядит следующим образом:

 

 

'''Теорема 5 (теорема 6, глава III, 5.3.1 в [7]).''' Если множества <math>S_1 \ne \empty \; </math> и <math>S_2 \ne \empty \; </math> представлены B-деревьями, тогда операция <math>Concatenate(S_1, S_2) \; </math> выполняется за время <math>O(log \ max \; </math>{<math>|S_1|, |S_2| \; </math>}<math>) \; </math> и содержит <math>O(log_B max \; </math>{<math>|S_1|, |S_2| \; </math>}<math>) \; </math> операций ввода-вывода, а операция <math>Split(S_1, y) \; </math> выполняется за время <math>O(log|S_1| \; )</math> и содержит <math>O(log_B |S_1| \; )</math> операций ввода-вывода. Все границы приведены для наихудшего случая.

 

 

 

 

 

 

 

 

 

 

 

 

Несколько структур данных внешней памяти были выведены из B-деревьев или используют B-дерево в качестве базовой структуры; более подробное изложение см. в [2]. Одна из таких структур – так называемое ''сбалансированное по весам B-дерево'' – особенно хорошо подходит в качестве базы для построения динамических внешних структур данных, имеющих вторичные структуры, присоединенные ко всем или некоторым их вершинам. Предложенное Арджем и Виттером [5], сбалансированное по весам B-дерево является вариантом B-дерева, у которого все поддерревья вершины имеют приблизительно одинаковое, с поправкой на небольшой константный коэффициент, число листьев. Можно показать, что сбалансированные по весам B-деревья обладают следующим свойством:

 

 

'''Анализ амортизации'''

Большинство утверждений об амортизации, используемых для (a, b)-деревьев, буферных деревьев и родственных им структур, основаны на теореме, предложенной Хаддлстоном и Мельхорном [13 , теорема 3]. Эта теорема утверждает, что полное число операций повторной балансировки в любой последовательности из N перемешанных операций вставки и удаления, выполняемых на изначально пустом ''слабом'' B-дереве (то есть на (a, b)-дереве, у которого <math>b \ge 2a \; </math>), являются не более чем линейными относительно N. Этот результат распространяется на буферные деревья, так как они представляют собой (M/4B, M/B)-деревья. Поскольку B-деревья представляют собой (a, b)-деревья с b = 2a – 1 (если b является нечетным), этот результат в максимально общей ситуации не является полностью верным для B-деревьев; Хаддлстон и Мельхорн приводят простой контрпример для (2; 3)-деревьев.

 

 

 

 

 

 

 

Существует множество коммерческих и бесплатных реализаций B-деревьев и (a, b)-деревьев, доступных для скачивания. В их число входят реализации на базе C++, являющиеся компонентами библиотеки [http://www.algorithmic-solutions.com/ LEDA], библиотеки [http://stxxl.sourceforge.net/ STXXL] и библиотеки [http://www.cs.duke.edu/TPIE TPIE]), а также реализации на базе Java, являющиеся компонентами библиотеки [http://www.xxl-library.de/ javaxxl]. Кроме того, реализации на псевдокоде можно найти почти в любом учебнике по системам баз данных или алгоритмам и структурам данных – например, в [10, 11]. Поскольку учебники почти всегда оставляют детали реализации операции DELETE в качестве упражнения для читателя, обсуждение в работе Яннинка [15] особенно ценно.