4431
правка
B-дерево (дерево многоканального поиска): различия между версиями
Материал из WEGA
B-дерево (дерево многоканального поиска) (посмотреть исходный код)
Версия от 13:49, 1 ноября 2012
, 1 ноября 2012→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 62: | Строка 62: | ||
Примечание 1. При поточной обработке вершин B-дерева, то есть связывании вершин в соответствии с их номером в порядке обхода графа, операции PREV и NEXT могут быть выполнены за константное время (с константным числом операций ввода-вывода). | Примечание 1. При поточной обработке вершин B-дерева, то есть связывании вершин в соответствии с их номером в порядке обхода графа, операции PREV и NEXT могут быть выполнены за константное время (с константным числом операций ввода-вывода). | ||
Одномерный запрос диапазона ищет все ключи, попадающие в заданный диапазон запросов. | Одномерный ''запрос диапазона'' ищет все ключи, попадающие в заданный диапазон запросов. | ||
'''Лемма 1.''' B-дерево поддерживает одномерные запросы диапазонов с временной сложностью <math>O(log N + K) \; </math> (и <math>O(log_B N + K/B) \; </math> операций ввода-вывода) в худшем случае, где K – количество возвращаемых ключей. | |||
Теорема 4 ([8]). Мультиверсия B-дерева может быть построена из B-дерева, являющегося оптимальным относительно сложности операций Find, Insert и Delete в худшем случае, а также относительно сложности ответа на запросы диапазонов в худшем случае. | |||
В рамках соглашения о том, что каждое обновление B-дерева создает новую «версию» B-дерева, ''мультиверсия'' B-дерева представляет собой B-дерево, позволяющее вносить обновления в текущую версию и одновременно поддерживающее запросы к более ранним версиям. | |||
'''Теорема 4 ([8]).''' Мультиверсия B-дерева может быть построена из B-дерева, являющегося оптимальным относительно сложности операций Find, Insert и Delete в худшем случае, а также относительно сложности ответа на запросы диапазонов в худшем случае. | |||
== Применение == | == Применение == | ||
