B-дерево (дерево многоканального поиска): различия между версиями

'''Теорема 2 ([18]).''' Использование памяти большими B-деревьями высокого порядка при условии случайных вставок и удалений составляет приблизительно <math>ln_2 \approx 69 \% </math>.

В рамках соглашения о том, что каждое обновление B-дерева создает новую «версию» B-дерева, ''мультиверсия'' B-дерева представляет собой B-дерево, позволяющее вносить обновления в текущую версию и одновременно поддерживающее запросы к более ранним версиям.

'''Теорема 4 ([8]).''' Мультиверсия B-дерева может быть построена из B-дерева, являющегося оптимальным относительно сложности операций Find, Insert и Delete в худшем случае, а также относительно сложности ответа на запросы диапазонов в худшем случае.