4551
правка
B-дерево (дерево многоканального поиска): различия между версиями
Перейти к навигации
Перейти к поиску
B-дерево (дерево многоканального поиска) (посмотреть исходный код)
Версия от 14:22, 1 ноября 2012
, 1 ноября 2012→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 104: | Строка 104: | ||
Многие приложения (в том числе для сортировки), включающие работу с большими множествами данных, позволяют применять пакетную обработку данных. Вариант B-деревьев, использующий эту ослабленную постановку задачи и предложенный Арджем [ ], называется буферным деревом. Буферное дерево представляет собой B-деревья степени m | Многие приложения (в том числе для сортировки), включающие работу с большими множествами данных, позволяют применять пакетную обработку данных. Вариант B-деревьев, использующий эту ослабленную постановку задачи и предложенный Арджем [3], называется ''буферным деревом''. Буферное дерево представляет собой B-деревья степени <math>m \in \Theta (M/B) \; </math> (вместо <math>m \in \Theta (B) \; </math>), в которых каждой вершине присвоен буфер размера <math>\Theta (M) \; </math>. Эти буферы используются для сбора обновлений и запросов, передаваемых далее по дереву только в случае, если буфер достаточно полон, чтобы оправдать амортизационные расходы. | ||
'''Теорема 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 элементов могут быть отсортированы за оптимальное число операций ввода-вывода O(N/BlogM/B N/B) при помощи пакетной вставки их в листовое буферное дерево и последующего обхода листьев. Кроме того, буферные деревья также могут использоваться для реализации пакетных очередей с приоритетами на внешнем устройстве памяти. Ардж [ ] расширил анализ буферных деревьев и показал, что они также поддерживают реализацию операций DELETEMIN с амортизационной стоимостью в O(1/BlogM/B N/B) операций ввода-вывода. | Следовательно, N элементов могут быть отсортированы за оптимальное число операций ввода-вывода O(N/BlogM/B N/B) при помощи пакетной вставки их в листовое буферное дерево и последующего обхода листьев. Кроме того, буферные деревья также могут использоваться для реализации пакетных очередей с приоритетами на внешнем устройстве памяти. Ардж [ ] расширил анализ буферных деревьев и показал, что они также поддерживают реализацию операций DELETEMIN с амортизационной стоимостью в O(1/BlogM/B N/B) операций ввода-вывода. | ||
Поскольку степень буферного дерева слишком велика, чтобы выполнение непакетных операций было эффективным, Ардж и коллеги [4] исследовали, каким образом буферы могут быть присоединены к дереву многоканального поиска (и впоследствии отсоединены от него) с сохранением степени базовой структуры, равной 0{B). Их исследование использует в качестве примера индексную структуру R-дерева, однако представленные в нем техники могут быть перенесены на B-дерево. Доступ к полученной структуре данных осуществляется стандартными методами; к тому же она допускает пакетные операции обновления – например, массовую загрузку и массовые запросы. Амортизационная стоимость операций ввода-вывода аналогична сложности операций для буферного дерева. | Поскольку степень буферного дерева слишком велика, чтобы выполнение непакетных операций было эффективным, Ардж и коллеги [4] исследовали, каким образом буферы могут быть присоединены к дереву многоканального поиска (и впоследствии отсоединены от него) с сохранением степени базовой структуры, равной 0{B). Их исследование использует в качестве примера индексную структуру R-дерева, однако представленные в нем техники могут быть перенесены на B-дерево. Доступ к полученной структуре данных осуществляется стандартными методами; к тому же она допускает пакетные операции обновления – например, массовую загрузку и массовые запросы. Амортизационная стоимость операций ввода-вывода аналогична сложности операций для буферного дерева. | ||