4551
правка
B-дерево (дерево многоканального поиска): различия между версиями
Перейти к навигации
Перейти к поиску
B-дерево (дерево многоканального поиска) (посмотреть исходный код)
Версия от 14:18, 1 ноября 2012
, 1 ноября 2012→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 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-деревьев, использующий эту ослабленную постановку задачи и предложенный Арджем [ ], называется буферным деревом. Буферное дерево представляет собой B-деревья степени m 2 &(M/B) (вместо m 2 &(B)), в которых каждой вершине присвоен буфер размера 0{M). Эти буферы используются для сбора обновлений и запросов, передаваемых далее по дереву только в случае, если буфер достаточно полон, чтобы оправдать амортизационные расходы. | Многие приложения (в том числе для сортировки), включающие работу с большими множествами данных, позволяют применять пакетную обработку данных. Вариант B-деревьев, использующий эту ослабленную постановку задачи и предложенный Арджем [ ], называется буферным деревом. Буферное дерево представляет собой B-деревья степени m 2 &(M/B) (вместо m 2 &(B)), в которых каждой вершине присвоен буфер размера 0{M). Эти буферы используются для сбора обновлений и запросов, передаваемых далее по дереву только в случае, если буфер достаточно полон, чтобы оправдать амортизационные расходы. | ||