4430
правок
B-дерево (дерево многоканального поиска): различия между версиями
Материал из WEGA
B-дерево (дерево многоканального поиска) (посмотреть исходный код)
Версия от 18:37, 1 марта 2016
, 1 марта 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показано 14 промежуточных версий этого же участника) | |||
| Строка 4: | Строка 4: | ||
Задача связана с хранением линейно упорядоченного множества элементов таким образом, чтобы операции FIND, INSERT и DELETE для типа данных DICTIONARY могли эффективно исполняться. | Задача связана с хранением линейно упорядоченного множества элементов таким образом, чтобы операции FIND, INSERT и DELETE для типа данных DICTIONARY могли эффективно исполняться. | ||
В 1972 году Байером и Маккрейтом был введен класс B-деревьев как одного из способов реализации «индекса динамически меняющегося файла с произвольным доступом» [6, стр. 173]. С тех пор B-деревья получили широкое распространение в контексте работы с базами данных и в сообществе разработчиков алгоритмов; одним из свидетельств их быстрого и широкого принятия может служить тот факт, что авторитетный обзор B-деревьев за авторством Комера [9] появился уже в 1979 году и описывал структуру данных B-дерева как «вездесущую». | В 1972 году Байером и Маккрейтом был введен класс [[B-Дерево|B-деревьев]] как одного из способов реализации «индекса динамически меняющегося файла с произвольным доступом» [6, стр. 173]. С тех пор B-деревья получили широкое распространение в контексте работы с базами данных и в сообществе разработчиков алгоритмов; одним из свидетельств их быстрого и широкого принятия может служить тот факт, что авторитетный обзор B-деревьев за авторством Комера [9] появился уже в 1979 году и описывал структуру данных B-дерева как «вездесущую». | ||
== Нотация == | == Нотация == | ||
| Строка 40: | Строка 40: | ||
== Операции обновления == | == Операции обновления == | ||
Операция вставки INSERT для (a, b)-дерева вначале ищет ключ x, который должен быть вставлен. После того, как неуспешный поиск остановится в некотором листе | Операция вставки INSERT для (a, b)-дерева вначале ищет ключ x, который должен быть вставлен. После того, как неуспешный поиск остановится в некотором листе <math>\ell \;</math>, x вставляется в набор ключей <math>\ell \;</math>. Если в результате у <math>\ell \;</math> становится более b элементов, для разрешения ситуации переполнения может применяться один из двух подходов: (1) вершина <math>\ell \;</math> может быть расщеплена по среднему ключу на две вершины, каждая из которых содержит не менее a ключей, либо (2) вершина <math>\ell \;</math> может передать некоторые ключи левой или правой вершине-«сестре» (если у вершины-«сестры» достаточно места для принятия новых ключей). В первом случае новый элемент маршрутизации, разделяющий ключи в двух новых поддеревьях предка <math>\ell \;</math> – <math>\mu \;</math> – должен быть вставлен в набор ключей <math>\mu \;</math>; во втором случае необходимо обновить элемент маршрутизации в <math>\mu \;</math>, отделяющий ключи в поддереве, корнем которого является <math>\ell \;</math>, от ключей, относящихся к соответствующей вершине-«сестре» <math>\ell \;</math>. Если вершина <math>\ell \;</math> была расщеплена, вершину <math>\mu \;</math> необходимо проверить на предмет потенциального переполнения из-за вставки нового элемента маршрутизации; и это расщепление может продолжаться вверх, вплоть до корня. | ||
Операция удаления DELETE также вначале определяет ключ x, подлежащий удалению. Если (в нелистовом дереве) x располагается во внутренней вершине, то x заменяется самым большим ключом левого поддерева x (или самым маленьким ключом правого поддерева x), который располагался в листе и теперь удаляется оттуда. В листовом дереве ключи удаляются только из листьев (это удаление не влияет на корректность элемента маршрутизации более высоких уровней). В любом случае операция DELETE может привести к тому, что вершина-лист <math>\ell \;</math> будет содержать меньше a элементов. Для разрешения ситуации нехватки также применяются два подхода: (1) вершина <math>\ell \;</math> сливается с вершиной-«сестрой» слева или справа от нее; (2) ключи из левой или правой вершины-«сестры» перемещаются в <math>\ell \;</math> (если это не приведет к нехватке ключей в этой вершине). Обе стратегии обработки нехватки требуют обновления информации о маршрутизации, хранящейся в вершине-предке <math>\ell \;</math>, которая в случае слияния сама может испытать нехватку ключей. Как и при обработке переполнения, этот процесс может продолжаться вплоть до корня дерева. | |||
Заметим, что корень дерева может быть расщеплен в результате операции вставки INSERT, а также может исчезнуть, если два его единственных потомка сливаются, образуя новый корень. Это значит, что B-деревья растут и сжимаются в своей верхней части, в силу чего все листья гарантированно остаются на одном и том же уровне дерева (свойство 1 определения 1). | Заметим, что корень дерева может быть расщеплен в результате операции вставки INSERT, а также может исчезнуть, если два его единственных потомка сливаются, образуя новый корень. Это значит, что B-деревья растут и сжимаются в своей верхней части, в силу чего все листья гарантированно остаются на одном и том же уровне дерева (свойство 1 определения 1). | ||
== Основные результаты == | == Основные результаты == | ||
Поскольку B-деревья представляют собой основную индексную структуру для внешнего хранения, результаты приводятся не только в форме RAM-модели вычислений, но и в форме I/O-модели (модели ввода-вывода), введенной Аггарвалом и Виттером [1]. В I/O-модели неконстантными параметрами являются не только количество элементов в экземпляре задачи (N), но и количество элементов, которые могут одновременно храниться в основной памяти (M), и количество элементов, помещающихся в один блок диска (B), а мерой сложности является количество операций ввода-вывода (I/O), необходимых для решения данного экземпляра задачи. Если B-деревья используются в структуре внешней памяти, степень B-дерева (m) обычно выбирается таким образом, чтобы одна вершина помещалась в один блок диска, то есть m | Поскольку B-деревья представляют собой основную индексную структуру для внешнего хранения, результаты приводятся не только в форме RAM-модели вычислений, но и в форме I/O-модели (модели ввода-вывода), введенной Аггарвалом и Виттером [1]. В I/O-модели неконстантными параметрами являются не только количество элементов в экземпляре задачи (N), но и количество элементов, которые могут одновременно храниться в основной памяти (M), и количество элементов, помещающихся в один блок диска (B), а мерой сложности является количество операций ввода-вывода (I/O), необходимых для решения данного экземпляра задачи. Если B-деревья используются в структуре внешней памяти, степень B-дерева (m) обычно выбирается таким образом, чтобы одна вершина помещалась в один блок диска, то есть <math>m \in \Theta(B) \; </math>, и это неявно предполагается везде, где рассматривается I/O-сложность B-деревьев. | ||
'''Теорема 1.''' Высота B-дерева степени <math>m \ge 3 \; </math> с N ключами ограничена значением <math>log_{\mathcal{d}m/2\mathcal{e}} ((N + 1)/2)</math>. | |||
'''Теорема 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-дерева, то есть связывании вершин в соответствии с их номером в порядке обхода графа, операции PREV и NEXT могут быть выполнены за константное время (с константным числом операций ввода-вывода). | Примечание 1. При поточной обработке вершин B-дерева, то есть связывании вершин в соответствии с их номером в порядке обхода графа, операции PREV и NEXT могут быть выполнены за константное время (с константным числом операций ввода-вывода). | ||
Одномерный запрос диапазона ищет все ключи, попадающие в заданный диапазон запросов. | Одномерный ''запрос диапазона'' ищет все ключи, попадающие в заданный диапазон запросов. | ||
Лемма 1. B-дерево поддерживает одномерные запросы диапазонов с временной сложностью O( | '''Лемма 1.''' B-дерево поддерживает одномерные запросы диапазонов с временной сложностью <math>O(log N + K) \; </math> (и <math>O(log_B N + K/B) \; </math> операций ввода-вывода) в худшем случае, где K – количество возвращаемых ключей. | ||
Теорема 4 ([8]). Мультиверсия B-дерева может быть построена из B-дерева, являющегося оптимальным относительно сложности операций Find, Insert и Delete в худшем случае, а также относительно сложности ответа на запросы диапазонов в худшем случае. | В рамках соглашения о том, что каждое обновление B-дерева создает новую «версию» B-дерева, ''мультиверсия'' B-дерева представляет собой B-дерево, позволяющее вносить обновления в текущую версию и одновременно поддерживающее запросы к более ранним версиям. | ||
'''Теорема 4 ([8]).''' Мультиверсия B-дерева может быть построена из B-дерева, являющегося оптимальным относительно сложности операций Find, Insert и Delete в худшем случае, а также относительно сложности ответа на запросы диапазонов в худшем случае. | |||
== Применение == | == Применение == | ||
Базы данных | '''Базы данных''' | ||
Очереди с приоритетами | Одной из основных причин успеха формата B-деревьев является их тесная связь с базами данных: любая реализация реляционной модели данных Кодда (по случайности, предложенной в том же году, когда были изобретены B-деревья) требует использования эффективного механизма индексирования для поиска и обхода отношений, хранящихся во внешней памяти. Если этот индекс реализуется в форме <math>B^+ \; </math>-дерева, то все ключи хранятся в связанном списке листьев, который индексируется верхними уровнями <math>B^+ \; </math>-дерева, что делает возможными эффективный логарифмический поиск и последовательное сканирование множества ключей. | ||
В силу важности этого механизма индексирования в сообществе разработчиков баз данных был опубликован целый ряд работ, посвященных тому, как встраивать B-деревья и их варианты в системы баз данных и как формулировать алгоритмы, использующие эти структуры. Комер [9] и Грэф [12] дают краткие обзоры ранних и новых результатов, однако из-за огромного количества этих результатов даже такие сжатые обзоры оказываются недостаточно исчерпывающими. Также было показано, что B-деревья хорошо работают в присутствии параллельно выполняемых операций [7], а Мельхорн [17, стр. 212] отмечал, что они демонстрируют особенно высокую производительность при применении подхода с расщеплением сверху вниз. Детали алгоритма расщепления можно найти, к примеру, в учебнике Кормена и коллег [10, глава 18.2]. | |||
'''Очереди с приоритетами''' | |||
B-деревья могут применяться для реализации абстрактного типа данных PRIORITYQUEUE, поскольку наименьший ключ всегда располагается в первом слоте самого левого листа. | B-деревья могут применяться для реализации абстрактного типа данных PRIORITYQUEUE, поскольку наименьший ключ всегда располагается в первом слоте самого левого листа. | ||
Многие приложения (в том числе для сортировки), включающие работу с большими множествами данных, позволяют применять пакетную обработку данных. Вариант B-деревьев, использующий эту ослабленную постановку задачи и предложенный Арджем [ ], называется буферным деревом. Буферное дерево представляет собой B-деревья степени m | '''Лемма 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-деревьев, использующий эту ослабленную постановку задачи и предложенный Арджем [3], называется ''буферным деревом''. Буферное дерево представляет собой B-деревья степени <math>m \in \Theta (M/B) \; </math> (вместо <math>m \in \Theta (B) \; </math>), в которых каждой вершине присвоен буфер размера <math>\Theta (M) \; </math>. Эти буферы используются для сбора обновлений и запросов, передаваемых далее по дереву только в случае, если буфер достаточно полон, чтобы оправдать амортизационные расходы. | |||
'''Теорема 6 (теорема 1 в [3]).''' Полная стоимость произвольной последовательности из N перемешанных операций Insert и Delete в изначально пустом буферном дереве составляет <math>O(N/B \ log_{M/B} N/B)\; </math> операций ввода-вывода, что означает, что амортизационная стоимость ввода-вывода операции составляет <math>O(1/B \ log_{M/B} N/B)\; </math>. | |||
Следовательно, N элементов могут быть отсортированы за оптимальное число операций ввода-вывода <math>O(N/B \ log_{M/B} N/B)\; </math> при помощи пакетной вставки их в листовое буферное дерево и последующего обхода листьев. Кроме того, буферные деревья также могут использоваться для реализации пакетных очередей с приоритетами на внешнем устройстве памяти. Ардж [3] расширил анализ буферных деревьев и показал, что они также поддерживают реализацию операций DELETEMIN с амортизационной стоимостью в <math>O(1/B \ log_{M/B} N/B)\; </math> операций ввода-вывода. | |||
Следовательно, N элементов могут быть отсортированы за оптимальное число операций ввода-вывода O(N/ | |||
Несколько структур данных внешней памяти были выведены из B-деревьев или используют B-дерево в качестве базовой структуры; более подробное изложение см. в [2]. Одна из таких структур – так называемое сбалансированное по весам B-дерево – особенно хорошо подходит в качестве базы для построения динамических внешних структур данных, имеющих вторичные структуры, присоединенные ко всем или некоторым их вершинам. Предложенное Арджем и Виттером [ ], сбалансированное по весам B-дерево является вариантом B-дерева, у которого все поддерревья вершины имеют приблизительно одинаковое, с поправкой на небольшой константный коэффициент, число листьев. Можно показать, что сбалансированные по весам B-деревья обладают следующим свойством: | Поскольку степень буферного дерева слишком велика, чтобы выполнение непакетных операций было эффективным, Ардж и коллеги [4] исследовали, каким образом буферы могут быть присоединены к дереву многоканального поиска (и впоследствии отсоединены от него) с сохранением степени базовой структуры, равной <math>\Theta (B) \; </math>. Их исследование использует в качестве примера индексную структуру R-дерева, однако представленные в нем техники могут быть перенесены на B-дерево. Доступ к полученной структуре данных осуществляется стандартными методами; к тому же она допускает ''пакетные операции обновления'' – например, массовую загрузку и массовые запросы. Амортизационная стоимость операций ввода-вывода аналогична сложности операций для буферного дерева. | ||
'''B-деревья как базовые структуры''' | |||
Несколько структур данных внешней памяти были выведены из B-деревьев или используют B-дерево в качестве базовой структуры; более подробное изложение см. в [2]. Одна из таких структур – так называемое ''сбалансированное по весам B-дерево'' – особенно хорошо подходит в качестве базы для построения динамических внешних структур данных, имеющих вторичные структуры, присоединенные ко всем или некоторым их вершинам. Предложенное Арджем и Виттером [5], сбалансированное по весам B-дерево является вариантом B-дерева, у которого все поддерревья вершины имеют приблизительно одинаковое, с поправкой на небольшой константный коэффициент, число листьев. Можно показать, что сбалансированные по весам B-деревья обладают следующим свойством: | |||
'''Теорема 7 ([5]).''' В сбалансированном по весам B-дереве повторная балансировка после операции обновления производится путем расщепления или слияния вершин. Если операция повторной балансировки затрагивает вершину v, являющуюся корнем поддерева с w{v) листьями, должны быть выполнены по меньшей мере <math>\Theta (w(v)) \; </math> операций обновления, касающихся листьев ниже v, прежде чем сама вершина v потребует новой балансировки. | |||
При помощи этой теоремы можно получить амортизированные границы для обработки вторичных структур данных, присоединенных к вершинам базового дерева, если только обновление каждой структуры имеет сложность по количеству операций ввода-вывода, линейную относительно числа элементов, хранящихся ниже вершины, к которой они присоединены [2,5]. | При помощи этой теоремы можно получить амортизированные границы для обработки вторичных структур данных, присоединенных к вершинам базового дерева, если только обновление каждой структуры имеет сложность по количеству операций ввода-вывода, линейную относительно числа элементов, хранящихся ниже вершины, к которой они присоединены [2,5]. | ||
Большинство утверждений об амортизации, используемых для (a, b)-деревьев, буферных деревьев и родственных им структур, основаны на теореме, предложенной Хаддлстоном и Мельхорном [13 , теорема 3]. Эта теорема утверждает, что полное число операций повторной балансировки в любой последовательности из N перемешанных операций вставки и удаления, выполняемых на изначально пустом слабом B-дереве (то есть на (a | '''Анализ амортизации''' | ||
Большинство утверждений об амортизации, используемых для (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)-деревьев. | |||
Важнейший факт, используемый для доказательства вышеприведенного утверждения об амортизации, заключается в том, что анализируемая последовательность операций производится над изначально ''пустой'' структурой данных. Джекобсен и коллеги [14] доказали существование ''неэкстремальных'' (a, b)-деревьев, то есть (a, b)-деревьев, у которых только некоторые вершины имеют степень a или b. На базе этого результата они подтвердили вышеприведенное положение о том, что стоимость повторной балансировки последовательности операций представляет собой амортизированную константу также и для операций на изначально непустых структурах данных, из чего следует и соответствующий результат для буферных деревьев. | |||
В контексте параллельных операций на системах баз данных следует отметить, что анализ Хаддлстона и Мельхорна предполагает соотношение <math>b \ge 2a + 2 \; </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] особенно ценно. | Существует множество коммерческих и бесплатных реализаций 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] особенно ценно. | ||
== См. также == | == См. также == | ||
