1294
правки
B-дерево (дерево многоканального поиска): различия между версиями
Материал из WEGA
B-дерево (дерево многоканального поиска) (посмотреть исходный код)
Версия от 04:57, 23 ноября 2024
, 23 ноября 2024→Литература
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 54: | Строка 54: | ||
'''Теорема 2 ([18]).''' Использование памяти большими B-деревьями высокого порядка при условии случайных вставок и удалений составляет приблизительно <math> | '''Теорема 2 ([18]).''' Использование памяти большими B-деревьями высокого порядка при условии случайных вставок и удалений составляет приблизительно <math>ln 2 \approx 69 \% </math>. | ||
| Строка 68: | Строка 68: | ||
В рамках соглашения о том, что каждое обновление B-дерева создает новую «версию» B-дерева, '' | В рамках соглашения о том, что каждое обновление B-дерева создает новую «версию» B-дерева, ''мультиверсионное'' B-дерево (''multiversion B-tree'') представляет собой B-дерево, позволяющее вносить обновления в текущую версию и одновременно поддерживающее запросы к более ранним версиям. | ||
'''Теорема 4 ([8]).''' | '''Теорема 4 ([8]).''' Мультиверсионное B-дерево может быть построено из B-дерева таким образом, что оно будет оптимальным относительно сложности операций Find, Insert и Delete в худшем случае, а также относительно сложности ответа на запросы диапазонов в худшем случае. | ||
== Применение == | == Применение == | ||
| Строка 188: | Строка 188: | ||
18. Yao, A.C.-C.: On random 2-3 trees. Acta Inform. 9, 159-170 (1978) | 18. Yao, A.C.-C.: On random 2-3 trees. Acta Inform. 9, 159-170 (1978) | ||
[[Категория: Совместное определение связанных терминов]] | [[Категория: Совместное определение связанных терминов]] | ||
