B-дерево (дерево многоканального поиска)
Ключевые слова и синонимы: деревья многоканального поиска
Постановка задачи
Задача связана с хранением линейно упорядоченного множества элементов таким образом, чтобы операции FIND, INSERT и DELETE для типа данных DICTIONARY могли эффективно исполняться. В 1972 году Байером и Маккрейтом был введен класс B-деревьев как одного из способов реализации «индекса динамически меняющегося файла с произвольным доступом» [6, стр. 173]. С тех пор B-деревья получили широкое распространение в контексте работы с базами данных и в сообществе разработчиков алгоритмов; одним из свидетельств их быстрого и широкого принятия может служить тот факт, что авторитетный обзор B-деревьев за авторством Комера [9] появился уже в 1979 году и описывал структуру данных B-дерева как «вездесущую».
Нотация
B-дерево представляет собой дерево многоканального поиска, определенное следующим образом (определение Байера и Маккрейта [6] было переформулировано Кнутом [16, глава 6.2.4] и Корменом и коллегами [10, глава 18.1]):
Определение 1. Пусть [math]\displaystyle{ m \ge 3 }[/math] – целое положительное число. Дерево T представляет собой B-дерево степени m, если оно пусто или удовлетворяет следующим условиям:
1. Все листья T находятся на одном и том же уровне T.
2. Каждая вершина T имеет не более m потомков.
3. Каждая вершина T, кроме корня и листьев, имеет по крайней мере m/2 потомков.
4. Корень T либо является листом, либо имеет не менее двух потомков.
5. Внутренняя вершина, имеющая k потомков [math]\displaystyle{ c_1[v], ... , c_k[v] \; }[/math], хранит k – 1 ключей; лист хранит от m/2 – 1 до m – 1 ключей. Ключи [math]\displaystyle{ key_i[v], 1 \le i \le k \; }[/math] [math]\displaystyle{ - 1 \; }[/math] вершины [math]\displaystyle{ v \in T \; }[/math] хранятся в порядке сортировки, т.е. [math]\displaystyle{ key_1[v] \le ... \le key_{k-1}[v] \; }[/math].
6. Если v – внутренняя вершина T с k потомками [math]\displaystyle{ c_1[v], ..., c_k[v] \; }[/math], то k – 1 ключей [math]\displaystyle{ key_1[v], ... ,key_{k-1}[v] \; }[/math] вершины v делят диапазон ключей, хранящихся в поддеревьях с корнем в вершине потомков v. Если [math]\displaystyle{ x_i \; }[/math] – любой ключ, хранящийся в поддереве, корнем которого является [math]\displaystyle{ c_i[v] \; }[/math], выполняется следующее соотношение:
[math]\displaystyle{ x_1 \le key_1[v] \le x_2 \le key_2[v] \le ... \le x_{k-1} \le key_{k-1}[v] \le x_k \; }[/math]
Чтобы произвести поиск по B-дереву для заданного ключа x, алгоритм начинает с корня дерева, которым является текущая вершина. Если x соответствует одному из ключей текущей вершины, поиск успешно завершается. В противном случае, если текущая вершина представляет собой лист, поиск завершается неуспешно. Если ключи текущей вершины не содержат x, а текущая вершина не является листом, алгоритм определяет уникальное поддерево с корнем в потомке текущей вершины, которое может содержать x, и рекурсивно исполняется для этого поддерева. Поскольку процесс поиска управляется ключами вершины, они также называются элементами маршрутизации.
Варианты и расширения
Кнут [16] определяет B*-дерево как B-дерево, для которого свойство 3 определения 1 меняется следующим образом: каждая вершина, помимо корневой, содержит не менее 2m/3 ключей.
B[math]\displaystyle{ ^+ }[/math]-дерево представляет собой листовое B-дерево, то есть B-дерево, в котором ключи хранятся только в листьях. Кроме того, листья привязываются по порядку слева направо, что позволяет осуществлять быстрый последовательный обход ключей, хранящихся в дереве. Элементы маршрутизации в листовом дереве обычно являются копиями определенных ключей, хранящихся в листьях (ключ [math]\displaystyle{ key_i[v] \; }[/math] может быть установлен равным максимальному ключу, хранящемуся в поддереве с корнем в [math]\displaystyle{ c_i[v] \; }[/math]), однако вполне подойдет любой набор элементов маршрутизации, для которого выполняются свойства 5 и 6 определения 1.
Хаддлстон и Мельхорн [13] расширили определение 1 для описания более общего класса деревьев многоканального поиска, включающего класс B-деревьев в качестве частного случая. Введенный ими класс так называемых (a, b)-деревьев параметризован двумя целыми числами a и b, удовлетворяющими условиям: [math]\displaystyle{ a \ge 2 \; }[/math] и [math]\displaystyle{ 2a \; }[/math]— [math]\displaystyle{ 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]\displaystyle{ b \ge 2 \; }[/math]. Это утверждение в конечном итоге привело к тому, что (a, b)-деревья с [math]\displaystyle{ b \ge 2a \; }[/math] получили специальное название – слабые B-деревья [13].
Операции обновления
Операция вставки INSERT для (a, b)-дерева вначале ищет ключ x, который должен быть вставлен. После того, как неуспешный поиск остановится в некотором листе [math]\displaystyle{ \ell \; }[/math], x вставляется в набор ключей [math]\displaystyle{ \ell \; }[/math]. Если в результате у [math]\displaystyle{ \ell \; }[/math] становится более b элементов, для разрешения ситуации переполнения может применяться один из двух подходов: (1) вершина [math]\displaystyle{ \ell \; }[/math] может быть расщеплена по среднему ключу на две вершины, каждая из которых содержит не менее a ключей, либо (2) вершина [math]\displaystyle{ \ell \; }[/math] может передать некоторые ключи левой или правой вершине-«сестре» (если у вершины-«сестры» достаточно места для принятия новых ключей). В первом случае новый элемент маршрутизации, разделяющий ключи в двух новых поддеревьях предка [math]\displaystyle{ \ell \; }[/math] – [math]\displaystyle{ \mu \; }[/math] – должен быть вставлен в набор ключей [math]\displaystyle{ \mu \; }[/math]; во втором случае необходимо обновить элемент маршрутизации в [math]\displaystyle{ \mu \; }[/math], отделяющий ключи в поддереве, корнем которого является [math]\displaystyle{ \ell \; }[/math], от ключей, относящихся к соответствующей вершине-«сестре» [math]\displaystyle{ \ell \; }[/math]. Если вершина [math]\displaystyle{ \ell \; }[/math] была расщеплена, вершину [math]\displaystyle{ \mu \; }[/math] необходимо проверить на предмет потенциального переполнения из-за вставки нового элемента маршрутизации; и это расщепление может продолжаться вверх, вплоть до корня.
Операция удаления DELETE также вначале определяет ключ x, подлежащий удалению. Если (в нелистовом дереве) x располагается во внутренней вершине, то x заменяется самым большим ключом левого поддерева x (или самым маленьким ключом правого поддерева x), который располагался в листе и теперь удаляется оттуда. В листовом дереве ключи удаляются только из листьев (это удаление не влияет на корректность элемента маршрутизации более высоких уровней). В любом случае операция DELETE может привести к тому, что вершина-лист [math]\displaystyle{ \ell \; }[/math] будет содержать меньше a элементов. Для разрешения ситуации нехватки также применяются два подхода: (1) вершина [math]\displaystyle{ \ell \; }[/math] сливается с вершиной-«сестрой» слева или справа от нее; (2) ключи из левой или правой вершины-«сестры» перемещаются в [math]\displaystyle{ \ell \; }[/math] (если это не приведет к нехватке ключей в этой вершине). Обе стратегии обработки нехватки требуют обновления информации о маршрутизации, хранящейся в вершине-предке [math]\displaystyle{ \ell \; }[/math], которая в случае слияния сама может испытать нехватку ключей. Как и при обработке переполнения, этот процесс может продолжаться вплоть до корня дерева.
Заметим, что корень дерева может быть расщеплен в результате операции вставки INSERT, а также может исчезнуть, если два его единственных потомка сливаются, образуя новый корень. Это значит, что B-деревья растут и сжимаются в своей верхней части, в силу чего все листья гарантированно остаются на одном и том же уровне дерева (свойство 1 определения 1).
Основные результаты
Поскольку B-деревья представляют собой основную индексную структуру для внешнего хранения, результаты приводятся не только в форме RAM-модели вычислений, но и в форме I/O-модели (модели ввода-вывода), введенной Аггарвалом и Виттером [1]. В I/O-модели неконстантными параметрами являются не только количество элементов в экземпляре задачи (N), но и количество элементов, которые могут одновременно храниться в основной памяти (M), и количество элементов, помещающихся в один блок диска (B), а мерой сложности является количество операций ввода-вывода (I/O), необходимых для решения данного экземпляра задачи. Если B-деревья используются в структуре внешней памяти, степень B-дерева (m) обычно выбирается таким образом, чтобы одна вершина помещалась в один блок диска, то есть [math]\displaystyle{ m \in \Theta(B) \; }[/math], и это неявно предполагается везде, где рассматривается I/O-сложность B-деревьев.
Теорема 1. Высота B-дерева степени [math]\displaystyle{ m \ge 3 \; }[/math] с N ключами ограничена значением [math]\displaystyle{ log_{\mathcal{d}m/2\mathcal{e}} ((N + 1)/2) }[/math].
Теорема 2 ([18]). Использование памяти большими B-деревьями высокого порядка при условии случайных вставок и удалений составляет приблизительно [math]\displaystyle{ ln_2 \approx 69% \; }[/math].
Теорема 3. B-дерево может использоваться для реализации абстрактного типа данных Dictionary, такого, что операции Find, Insert и Delete на множестве из N элементов из линейно упорядоченной области определений могут быть выполнены за время [math]\displaystyle{ O(log N) \; }[/math] (и [math]\displaystyle{ O(log_B N) \; }[/math] операций ввода-вывода) в худшем случае.
Примечание 1. При поточной обработке вершин B-дерева, то есть связывании вершин в соответствии с их номером в порядке обхода графа, операции PREV и NEXT могут быть выполнены за константное время (с константным числом операций ввода-вывода).
Одномерный запрос диапазона ищет все ключи, попадающие в заданный диапазон запросов.
Лемма 1. B-дерево поддерживает одномерные запросы диапазонов с временной сложностью [math]\displaystyle{ O(log N + K) \; }[/math] (и [math]\displaystyle{ O(log_B N + K/B) \; }[/math] операций ввода-вывода) в худшем случае, где K – количество возвращаемых ключей.
В рамках соглашения о том, что каждое обновление B-дерева создает новую «версию» B-дерева, мультиверсия B-дерева представляет собой B-дерево, позволяющее вносить обновления в текущую версию и одновременно поддерживающее запросы к более ранним версиям.
Теорема 4 ([8]). Мультиверсия B-дерева может быть построена из B-дерева, являющегося оптимальным относительно сложности операций Find, Insert и Delete в худшем случае, а также относительно сложности ответа на запросы диапазонов в худшем случае.
Применение
Базы данных
Одной из основных причин успеха формата B-деревьев является их тесная связь с базами данных: любая реализация реляционной модели данных Кодда (по случайности, предложенной в том же году, когда были изобретены B-деревья) требует использования эффективного механизма индексирования для поиска и обхода отношений, хранящихся во внешней памяти. Если этот индекс реализуется в форме [math]\displaystyle{ B^+ \; }[/math]-дерева, то все ключи хранятся в связанном списке листьев, который индексируется верхними уровнями [math]\displaystyle{ B^+ \; }[/math]-дерева, что делает возможными эффективный логарифмический поиск и последовательное сканирование множества ключей.
В силу важности этого механизма индексирования в сообществе разработчиков баз данных был опубликован целый ряд работ, посвященных тому, как встраивать B-деревья и их варианты в системы баз данных и как формулировать алгоритмы, использующие эти структуры. Комер [9] и Грэф [12] дают краткие обзоры ранних и новых результатов, однако из-за огромного количества этих результатов даже такие сжатые обзоры оказываются недостаточно исчерпывающими. Также было показано, что B-деревья хорошо работают в присутствии параллельно выполняемых операций [7], а Мельхорн [17, стр. 212] отмечал, что они демонстрируют особенно высокую производительность при применении подхода с расщеплением сверху вниз. Детали алгоритма расщепления можно найти, к примеру, в учебнике Кормена и коллег [10, глава 18.2].
Очереди с приоритетами
B-деревья могут применяться для реализации абстрактного типа данных PRIORITYQUEUE, поскольку наименьший ключ всегда располагается в первом слоте самого левого листа.
Лемма 2. Реализация очереди с приоритетами, использующая B-дерево, поддерживает операцию взятия минимума Min, выполняемую за время [math]\displaystyle{ O(1) \; }[/math] (с [math]\displaystyle{ O(1) \; }[/math] операций ввода-вывода). Все остальные операции (включая операцию понижения ключа DecreaseKey) имеют временную сложность [math]\displaystyle{ O(log N) \; }[/math] (и количество операций ввода-вывода [math]\displaystyle{ O(log_B N)) \; }[/math] в худшем случае.
Мельхорн [17, глава III, 5.3.1] исследовал B-деревья (и более общий случай – (a, b)-деревья с [math]\displaystyle{ a \ge 2 \; }[/math] и [math]\displaystyle{ b \ge 2a \; }[/math] [math]\displaystyle{ - 1 \; }[/math]) в контексте очередей с приоритетами, допускающих слияние. Очереди, допускающие слияние, представляют собой очереди с приоритетами, для которых можно выполнять сцепление и расщепление.
Сцепление очередей с приоритетами для множества [math]\displaystyle{ S_1 \ne \empty \; }[/math] и множества [math]\displaystyle{ S_2 \ne \empty \; }[/math] определяется только для случая, если [math]\displaystyle{ max \; }[/math] {[math]\displaystyle{ x | x \in S_1 }[/math]} [math]\displaystyle{ \lt min \; }[/math] {[math]\displaystyle{ x | x \in S_2 \; }[/math]}, в результате чего получается одна очередь с приоритетами S1 [ S2. Расщепление очереди с приоритетами для множества S3 ф ; в соответствии с некоторым y 2 dom(S3) приводит к появлению очередей с приоритетами для множества S4 := fx 2 S3 j x < yg и для множества S5 := fx 2 S3 j x > yg (одно из этих множеств может быть пустым). Результат Мельхорна, переформулированный в контексте B-деревьев, выглядит следующим образом: Теорема 5 (теорема 6, глава III, 5.3.1 в [7]). Если множества S1 ф ; и S2 ф ; представлены B-деревьями, тогда операция Concatenate(S1; S2) выполняется за время O(logmaxfjS1j; jS2jg) и содержит O(logB maxfjS1j; jS2jg)) операций ввода-вывода, а операция Split(S1 ; y) выполняется за время O(logjS1j) и содержит O(log B jS1j) операций ввода-вывода. Все границы приведены для наихудшего случая.
Буферизованные структуры данных
Многие приложения (в том числе для сортировки), включающие работу с большими множествами данных, позволяют применять пакетную обработку данных. Вариант B-деревьев, использующий эту ослабленную постановку задачи и предложенный Арджем [ ], называется буферным деревом. Буферное дерево представляет собой B-деревья степени m 2 &(M/B) (вместо m 2 &(B)), в которых каждой вершине присвоен буфер размера 0{M). Эти буферы используются для сбора обновлений и запросов, передаваемых далее по дереву только в случае, если буфер достаточно полон, чтобы оправдать амортизационные расходы.
Теорема 6 (теорема 1 в [ ]). Полная стоимость произвольной последовательности из N перемешанных операций Insert и Delete в изначально пустом буферном дереве составляет O(N/BlogM/BN/B) операций ввода-вывода, что означает, что амортизационная стоимость ввода-вывода операции составляет O(1/BlogM/B N/B). Следовательно, N элементов могут быть отсортированы за оптимальное число операций ввода-вывода O(N/BlogM/B N/B) при помощи пакетной вставки их в листовое буферное дерево и последующего обхода листьев. Кроме того, буферные деревья также могут использоваться для реализации пакетных очередей с приоритетами на внешнем устройстве памяти. Ардж [ ] расширил анализ буферных деревьев и показал, что они также поддерживают реализацию операций DELETEMIN с амортизационной стоимостью в O(1/BlogM/B N/B) операций ввода-вывода. Поскольку степень буферного дерева слишком велика, чтобы выполнение непакетных операций было эффективным, Ардж и коллеги [4] исследовали, каким образом буферы могут быть присоединены к дереву многоканального поиска (и впоследствии отсоединены от него) с сохранением степени базовой структуры, равной 0{B). Их исследование использует в качестве примера индексную структуру R-дерева, однако представленные в нем техники могут быть перенесены на B-дерево. Доступ к полученной структуре данных осуществляется стандартными методами; к тому же она допускает пакетные операции обновления – например, массовую загрузку и массовые запросы. Амортизационная стоимость операций ввода-вывода аналогична сложности операций для буферного дерева.
B-деревья как базовые структуры
Несколько структур данных внешней памяти были выведены из B-деревьев или используют B-дерево в качестве базовой структуры; более подробное изложение см. в [2]. Одна из таких структур – так называемое сбалансированное по весам B-дерево – особенно хорошо подходит в качестве базы для построения динамических внешних структур данных, имеющих вторичные структуры, присоединенные ко всем или некоторым их вершинам. Предложенное Арджем и Виттером [ ], сбалансированное по весам B-дерево является вариантом B-дерева, у которого все поддерревья вершины имеют приблизительно одинаковое, с поправкой на небольшой константный коэффициент, число листьев. Можно показать, что сбалансированные по весам B-деревья обладают следующим свойством:
Теорема 7 ([5]). В сбалансированном по весам B-дереве повторная балансировка после операции обновления производится путем расщепления или слияния вершин. Если операция повторной балансировки затрагивает вершину v, являющуюся корнем поддерева с w{v) листьями, должны быть выполнены по меньшей мере 0{w{v)) операций обновления, касающихся листьев ниже v, прежде чем сама вершина v потребует новой балансировки.
При помощи этой теоремы можно получить амортизированные границы для обработки вторичных структур данных, присоединенных к вершинам базового дерева, если только обновление каждой структуры имеет сложность по количеству операций ввода-вывода, линейную относительно числа элементов, хранящихся ниже вершины, к которой они присоединены [2,5].
Анализ амортизации
Большинство утверждений об амортизации, используемых для (a, b)-деревьев, буферных деревьев и родственных им структур, основаны на теореме, предложенной Хаддлстоном и Мельхорном [13 , теорема 3]. Эта теорема утверждает, что полное число операций повторной балансировки в любой последовательности из N перемешанных операций вставки и удаления, выполняемых на изначально пустом слабом B-дереве (то есть на (a; b)-дереве, у которого b > 2a), являются не более чем линейными относительно N. Этот результат распространяется на буферные деревья, так как они представляют собой (M/4B; M/B)-деревья. Поскольку B-деревья представляют собой (a, b)-деревья с b = 2a – 1 (если b является нечетным), этот результат в максимально общей ситуации не является полностью верным для B-деревьев; Хаддлстон и Мельхорн приводят простой контрпример для (2; 3)-деревьев.
Важнейший факт, используемый для доказательства вышеприведенного утверждения об амортизации, заключается в том, что анализируемая последовательность операций производится над изначально пустой структурой данных. Джекобсен и коллеги [ ] доказали существование неэкстремальных (a, b)-деревьев, то есть (a, b)-деревьев, у которых только некоторые вершины имеют степень a или b. На базе этого результата они подтвердили вышеприведенное положение о том, что стоимость повторной балансировки последовательности операций представляет собой амортизированную константу также и для операций на изначально непустых структурах данных, из чего следует и соответствующий результат для буферных деревьев. В контексте параллельных операций на системах баз данных следует отметить, что анализ Хаддлстона и Мельхорна предполагает соотношение b > 2a + 2 в случае использования алгоритма расщепления сверху вниз. Однако можно показать, что даже в общем случае несколько расщеплений вершин (в контексте амортизации) производятся неподалеку от корня.
Ссылка на код
Существует множество коммерческих и бесплатных реализаций 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] особенно ценно.
См. также
Литература
1. Aggarwal, A., Vitter, J.S.: The input/output complexity of sorting and related problems. Commun. ACM 31, 1116-1127 (1988)
2. Arge, L.A.: External memory data structures. In: Abello, J., Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Massive Data Sets, pp. 313-357. Kluwer, Dordrecht (2002)
3. Arge, L.A.: The Buffer Tree: A technique for designing batched external data structures. Algorithmica 37,1-24 (2003)
4. Arge, L.A., Hinrichs, K.H., Vahrenhold, J., Vitter, J.S.: Efficient bulk operations on dynamic R-trees. Algorithmica 33,104-128 (2002)
5. Arge, L.A., Vitter, J.S.: Optimal external interval management. SIAM J. Comput. 32,1488-1508 (2003)
6. Bayer, R., McCreight, E.M.: Organization and maintenance of large ordered indexes. Acta Inform. 1,173-189 (1972)
7. Bayer, R., Schkolnick, M.: Concurrency of operations on B-trees. Acta Inform. 9,1-21 (1977)
8. Becker, B., Gschwind, S., Ohler, T., Seeger, B., Widmayer, P.: An asymptotically optimal multiversion B-tree.VLDBJ. 5,264-275 (1996)
9. Comer, D.E.: The ubiquitous B-tree. ACM Comput. Surv. 11, 121-137(1979)
10. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. The MIT Electrical Engineering and Computer Science Series, 2nd edn. MIT Press, Cambridge (2001)
11. Elmasri, R., Navanthe, S.B.: Fundamentals of Database Systems, 5th edn. Addison-Wesley, Boston (2007)
12. Graefe, G.: B-tree indexes for high update rates. SIGMOD RECORD 35, 39-44 (2006)
13. Huddleston, S., Mehlhorn, K.: A new data structure for representing sorted lists. Acta Inform. 17,157-184(1982)
14. Jacobsen, L., Larsen, K.S., Nielsen, M.N.: On the existence of non-extreme (a,b)-trees. Inform. Process. Lett. 84, 69-73 (2002)
15. Jannink, J.: Implementing deletions in B+-trees. SIGMOD RECORD 24, 33-38 (1995)
16. Knuth, D.E.: Sorting and Searching. The Art of Computer Programming, vol. 3, 2nd edn. Addison-Wesley, Reading (1998)
17. Mehlhorn, K.: Data Structures and Algorithms 1: Sorting and Searching. EATCS Monographs on Theoretical Computer Science, vol. 1. Springer, Berlin (1984)
18. Yao, A.C.-C.: On random 2-3 trees. Acta Inform. 9, 159-170 (1978)