1294
правки
B-дерево (дерево многоканального поиска): различия между версиями
Материал из WEGA
B-дерево (дерево многоканального поиска) (посмотреть исходный код)
Версия от 04:57, 23 ноября 2024
, 23 ноября 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показано 11 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
Ключевые слова и синонимы: [[деревья многоканального поиска]] | Ключевые слова и синонимы: [[Дерево многоканального поиска|деревья многоканального поиска]] | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача связана с хранением линейно упорядоченного множества элементов таким образом, чтобы операции 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-дерева как «вездесущую». | ||
== Нотация == | == Нотация == | ||
| Строка 10: | Строка 10: | ||
''B-дерево'' представляет собой дерево многоканального поиска, определенное следующим образом (определение Байера и Маккрейта [6] было переформулировано Кнутом [16, глава 6.2.4] и Корменом и коллегами [10, глава 18.1]): | ''B-дерево'' представляет собой дерево многоканального поиска, определенное следующим образом (определение Байера и Маккрейта [6] было переформулировано Кнутом [16, глава 6.2.4] и Корменом и коллегами [10, глава 18.1]): | ||
'''Определение 1.''' Пусть <math>m \ge 3</math> – целое положительное число. Дерево T представляет собой ''B-дерево степени m'', если оно пусто или удовлетворяет следующим условиям: | '''Определение 1.''' Пусть <math>m \ge 3</math> – целое положительное число. Дерево T представляет собой ''[[B-дерево степени m]]'', если оно пусто или удовлетворяет следующим условиям: | ||
1. Все листья T находятся на одном и том же уровне T. | 1. Все листья T находятся на одном и том же уровне T. | ||
| Строка 26: | Строка 26: | ||
<math>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> | <math>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, и рекурсивно исполняется для этого поддерева. Поскольку процесс поиска управляется ключами вершины, они также называются ''элементами маршрутизации''. | Чтобы произвести поиск по B-дереву для заданного ключа x, алгоритм начинает с корня дерева, которым является текущая вершина. Если x соответствует одному из ключей текущей вершины, поиск успешно завершается. В противном случае, если текущая вершина представляет собой лист, поиск завершается неуспешно. Если ключи текущей вершины не содержат x, а текущая вершина не является листом, алгоритм определяет уникальное поддерево с корнем в потомке текущей вершины, которое может содержать x, и рекурсивно исполняется для этого поддерева. Поскольку процесс поиска управляется ключами вершины, они также называются ''элементами маршрутизации (routing elements)''. | ||
== Варианты и расширения == | == Варианты и расширения == | ||
Кнут [16] определяет ''B*-дерево'' как B-дерево, для которого свойство 3 определения 1 меняется следующим образом: каждая вершина, помимо корневой, содержит не менее 2m/3 ключей. | Кнут [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. | ''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)-деревья реализуются как листовые деревья. | Хаддлстон и Мельхорн [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-дерево представляет собой (b/2; b)-дерево, если b является четным, или (a; 2a – 1)-дерево (для нечетных b). Небольшое различие между четной и нечетной максимальной степенью приобретает значимость в контексте важного утверждения Хаддлстона и Мельхорна об амортизации (см. ниже), в котором должно выполняться неравенство <math>b \ge 2 \; </math>. Это утверждение в конечном итоге привело к тому, что (a, b)-деревья с <math>b \ge 2a \; </math> получили специальное название – ''[[слабые B-деревья]]'' [13]. | ||
== Операции обновления == | == Операции обновления == | ||
| Строка 54: | Строка 54: | ||
'''Теорема 2 ([18]).''' Использование памяти большими B-деревьями высокого порядка при условии случайных вставок и удалений составляет приблизительно <math> | '''Теорема 2 ([18]).''' Использование памяти большими B-деревьями высокого порядка при условии случайных вставок и удалений составляет приблизительно <math>ln 2 \approx 69 \% </math>. | ||
| Строка 68: | Строка 68: | ||
В рамках соглашения о том, что каждое обновление B-дерева создает новую «версию» B-дерева, '' | В рамках соглашения о том, что каждое обновление B-дерева создает новую «версию» B-дерева, ''мультиверсионное'' B-дерево (''multiversion B-tree'') представляет собой B-дерево, позволяющее вносить обновления в текущую версию и одновременно поддерживающее запросы к более ранним версиям. | ||
'''Теорема 4 ([8]).''' | '''Теорема 4 ([8]).''' Мультиверсионное B-дерево может быть построено из B-дерева таким образом, что оно будет оптимальным относительно сложности операций Find, Insert и Delete в худшем случае, а также относительно сложности ответа на запросы диапазонов в худшем случае. | ||
== Применение == | == Применение == | ||
| Строка 97: | Строка 97: | ||
'''Теорема 5 (теорема 6, глава III, 5.3.1 в [7]).''' Если множества | '''Теорема 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>. Эти буферы используются для сбора обновлений и запросов, передаваемых далее по дереву только в случае, если буфер достаточно полон, чтобы оправдать амортизационные расходы. | |||
Несколько структур данных внешней памяти были выведены из B-деревьев или используют B-дерево в качестве базовой структуры; более подробное изложение см. в [2]. Одна из таких структур – так называемое сбалансированное по весам B-дерево – особенно хорошо подходит в качестве базы для построения динамических внешних структур данных, имеющих вторичные структуры, присоединенные ко всем или некоторым их вершинам. Предложенное Арджем и Виттером [ ], сбалансированное по весам B-дерево является вариантом B-дерева, у которого все поддерревья вершины имеют приблизительно одинаковое, с поправкой на небольшой константный коэффициент, число листьев. Можно показать, что сбалансированные по весам B-деревья обладают следующим свойством: | '''Теорема 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> операций ввода-вывода. | |||
Поскольку степень буферного дерева слишком велика, чтобы выполнение непакетных операций было эффективным, Ардж и коллеги [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, 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++, являющиеся компонентами библиотеки | |||
Важнейший факт, используемый для доказательства вышеприведенного утверждения об амортизации, заключается в том, что анализируемая последовательность операций производится над изначально ''пустой'' структурой данных. Джекобсен и коллеги [14] доказали существование ''неэкстремальных'' (a, b)-деревьев, то есть (a, b)-деревьев, у которых только некоторые вершины имеют степень a или b. На базе этого результата они подтвердили вышеприведенное положение о том, что стоимость повторной балансировки последовательности операций представляет собой амортизированную константу также и для операций на изначально непустых структурах данных, из чего следует и соответствующий результат для буферных деревьев. | |||
В контексте параллельных операций на системах баз данных следует отметить, что анализ Хаддлстона и Мельхорна предполагает соотношение <math>b \ge 2a + 2 \; </math> в случае использования алгоритма расщепления сверху вниз. Однако можно показать, что даже в общем случае несколько расщеплений вершин (в контексте амортизации) производятся неподалеку от корня. | |||
'''Ссылки на код''' | |||
Существует множество коммерческих и бесплатных реализаций 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] особенно ценно. | |||
== См. также == | == См. также == | ||
| Строка 170: | Строка 187: | ||
18. Yao, A.C.-C.: On random 2-3 trees. Acta Inform. 9, 159-170 (1978) | 18. Yao, A.C.-C.: On random 2-3 trees. Acta Inform. 9, 159-170 (1978) | ||
[[Категория: Совместное определение связанных терминов]] | |||
