4551
правка
B-дерево (дерево многоканального поиска): различия между версиями
Перейти к навигации
Перейти к поиску
B-дерево (дерево многоканального поиска) (посмотреть исходный код)
Версия от 14:28, 1 ноября 2012
, 1 ноября 2012→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 110: | Строка 110: | ||
Следовательно, N элементов могут быть отсортированы за оптимальное число операций ввода-вывода O(N/ | Следовательно, N элементов могут быть отсортированы за оптимальное число операций ввода-вывода <math>O(N/B \ log_{M/B} N/B)\; </math> при помощи пакетной вставки их в листовое буферное дерево и последующего обхода листьев. Кроме того, буферные деревья также могут использоваться для реализации пакетных очередей с приоритетами на внешнем устройстве памяти. Ардж [3] расширил анализ буферных деревьев и показал, что они также поддерживают реализацию операций DELETEMIN с амортизационной стоимостью в <math>O(1/B \ log_{M/B} N/B)\; </math> операций ввода-вывода. | ||
Несколько структур данных внешней памяти были выведены из 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] особенно ценно. | ||