4551
правка
B-дерево (дерево многоканального поиска): различия между версиями
Перейти к навигации
Перейти к поиску
B-дерево (дерево многоканального поиска) (посмотреть исходный код)
Версия от 13:47, 1 ноября 2012
, 1 ноября 2012→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 53: | Строка 53: | ||
'''Теорема 1.''' Высота B-дерева степени <math>m \ge 3 \; </math> с N ключами ограничена значением <math>log_{\mathcal{d}m/2\mathcal{e}} ((N + 1)/2)</math>. | '''Теорема 1.''' Высота B-дерева степени <math>m \ge 3 \; </math> с N ключами ограничена значением <math>log_{\mathcal{d}m/2\mathcal{e}} ((N + 1)/2)</math>. | ||
Теорема 3. B-дерево может использоваться для реализации абстрактного типа данных Dictionary, такого, что операции Find, Insert и Delete на множестве из N элементов из линейно упорядоченной области определений могут быть выполнены за время O( | '''Теорема 2 ([18]).''' Использование памяти большими B-деревьями высокого порядка при условии случайных вставок и удалений составляет приблизительно <math>ln_2 \approx 69% \; </math>. | ||
'''Теорема 3.''' B-дерево может использоваться для реализации абстрактного типа данных Dictionary, такого, что операции Find, Insert и Delete на множестве из N элементов из линейно упорядоченной области определений могут быть выполнены за время <math>O(log N) \; </math> (и <math>O(log_B N) \; </math> операций ввода-вывода) в худшем случае. | |||
Примечание 1. При поточной обработке вершин B-дерева, то есть связывании вершин в соответствии с их номером в порядке обхода графа, операции PREV и NEXT могут быть выполнены за константное время (с константным числом операций ввода-вывода). | Примечание 1. При поточной обработке вершин B-дерева, то есть связывании вершин в соответствии с их номером в порядке обхода графа, операции PREV и NEXT могут быть выполнены за константное время (с константным числом операций ввода-вывода). | ||