4551
правка
B-дерево (дерево многоканального поиска): различия между версиями
Перейти к навигации
Перейти к поиску
B-дерево (дерево многоканального поиска) (посмотреть исходный код)
Версия от 13:55, 1 ноября 2012
, 1 ноября 2012→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 75: | Строка 75: | ||
== Применение == | == Применение == | ||
Базы данных | '''Базы данных''' | ||
Очереди с приоритетами | Одной из основных причин успеха формата B-деревьев является их тесная связь с базами данных: любая реализация реляционной модели данных Кодда (по случайности, предложенной в том же году, когда были изобретены B-деревья) требует использования эффективного механизма индексирования для поиска и обхода отношений, хранящихся во внешней памяти. Если этот индекс реализуется в форме <math>B^+ \; </math>-дерева, то все ключи хранятся в связанном списке листьев, который индексируется верхними уровнями <math>B^+ \; </math>-дерева, что делает возможными эффективный логарифмический поиск и последовательное сканирование множества ключей. | ||
В силу важности этого механизма индексирования в сообществе разработчиков баз данных был опубликован целый ряд работ, посвященных тому, как встраивать B-деревья и их варианты в системы баз данных и как формулировать алгоритмы, использующие эти структуры. Комер [9] и Грэф [12] дают краткие обзоры ранних и новых результатов, однако из-за огромного количества этих результатов даже такие сжатые обзоры оказываются недостаточно исчерпывающими. Также было показано, что B-деревья хорошо работают в присутствии параллельно выполняемых операций [7], а Мельхорн [17, стр. 212] отмечал, что они демонстрируют особенно высокую производительность при применении подхода с расщеплением сверху вниз. Детали алгоритма расщепления можно найти, к примеру, в учебнике Кормена и коллег [10, глава 18.2]. | |||
'''Очереди с приоритетами''' | |||
B-деревья могут применяться для реализации абстрактного типа данных PRIORITYQUEUE, поскольку наименьший ключ всегда располагается в первом слоте самого левого листа. | B-деревья могут применяться для реализации абстрактного типа данных PRIORITYQUEUE, поскольку наименьший ключ всегда располагается в первом слоте самого левого листа. | ||
Лемма 2. Реализация очереди с приоритетами, использующая B-дерево, поддерживает операцию взятия минимума Min, выполняемую за время O(1) (с O(1) операций ввода-вывода). Все остальные операции (включая операцию понижения ключа DecreaseKey) имеют временную сложность O( | |||
'''Лемма 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)-деревья с a > 2 и b > 2a – 1) в контексте очередей с приоритетами, допускающих слияние. Очереди, допускающие слияние, представляют собой очереди с приоритетами, для которых можно выполнять сцепление и расщепление. Сцепление очередей с приоритетами для множества S1 ф ; и множества S2 ф ; определяется только для случая, если maxfx j x 2 S1g < minfx j x 2 S2g, в результате чего получается одна очередь с приоритетами S1 [ S2. Расщепление очереди с приоритетами для множества S3 ф ; в соответствии с некоторым y 2 dom(S3) приводит к появлению очередей с приоритетами для множества S4 := fx 2 S3 j x < yg и для множества S5 := fx 2 S3 j x > yg (одно из этих множеств может быть пустым). Результат Мельхорна, переформулированный в контексте B-деревьев, выглядит следующим образом: | Мельхорн [17, глава III, 5.3.1] исследовал B-деревья (и более общий случай – (a, b)-деревья с a > 2 и b > 2a – 1) в контексте очередей с приоритетами, допускающих слияние. Очереди, допускающие слияние, представляют собой очереди с приоритетами, для которых можно выполнять сцепление и расщепление. Сцепление очередей с приоритетами для множества S1 ф ; и множества S2 ф ; определяется только для случая, если maxfx j x 2 S1g < minfx j x 2 S2g, в результате чего получается одна очередь с приоритетами 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) операций ввода-вывода. Все границы приведены для наихудшего случая. | Теорема 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) операций ввода-вывода. Все границы приведены для наихудшего случая. | ||