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

Поскольку B-деревья представляют собой основную индексную структуру для внешнего хранения, результаты приводятся не только в форме RAM-модели вычислений, но и в форме I/O-модели (модели ввода-вывода), введенной Аггарвалом и Виттером [1]. В I/O-модели неконстантными параметрами являются не только количество элементов в экземпляре задачи (N), но и количество элементов, которые могут одновременно храниться в основной памяти (M), и количество элементов, помещающихся в один блок диска (B), а мерой сложности является количество операций ввода-вывода (I/O), необходимых для решения данного экземпляра задачи. Если B-деревья используются в структуре внешней памяти, степень B-дерева (m) обычно выбирается таким образом, чтобы одна вершина помещалась в один блок диска, то есть <math>m \in \Theta(B) \; </math>, и это неявно предполагается везде, где рассматривается I/O-сложность B-деревьев.

 

'''Теорема 1.''' Высота B-дерева степени <math>m \ge 3 \; </math> с N ключами ограничена значением <math>log_{\mathcal{d}m/2\mathcal{e}} ((N + 1)/2)</math>.