Изменения

<wikitex>'''B-дерево''' — сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за $O(\log n)$. B-деревья схожи с [[Красно-черное дерево|красно-черными деревьями]] в том, что B-дерево с $n$ узлами имеют высоту $O(\lg log n)$, но отличаются от [[Красно-черное дерево|них]] количеством детей узлов — от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). Сама высота B-дерева может быть значительно меньше чем у [[Красно-черное дерево|красно-черного дерева]], из-за его ветвистости, и, следовательно, основание логарифма, выражающего высоту дерева, может быть намного больше. Таким образом, В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время $O(\lg log n)$

Здесь мы видим преимущества B-деревьев над красно-черными деревьями. Хотя высота деревьев растет как $O(\lg log t)$ в обоих случаях (вспомним, что t — константа), в случае B-деревьев основание логарифмов имеет гораздо большее значение. Таким образом, В-деревья требуют исследования примерно в $\lg log t$ раз меньшего количества узлов по сравнению с красно-черными деревьями. Поскольку исследование узла дерева обычно требует обращения к диску, количество дисковых операций при работе с В-деревьями оказывается существенно сниженным.</wikitex>