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

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

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

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

Кнут [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, удовлетворяющими условиям: <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].

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

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

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