4430
правок
B-дерево (дерево многоканального поиска): различия между версиями
Материал из WEGA
B-дерево (дерево многоканального поиска) (посмотреть исходный код)
Версия от 18:37, 1 марта 2016
, 1 марта 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показано 6 промежуточных версий этого же участника) | |||
| Строка 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-дерева как «вездесущую». | ||
== Нотация == | == Нотация == | ||
| Строка 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 | '''Анализ амортизации''' | ||
Большинство утверждений об амортизации, используемых для (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] особенно ценно. | ||
== См. также == | == См. также == | ||
