Конспект установочных лекций по комплексному курсу Информатика, Теория информации
B-деревья
Другой концепцией для специальных деревьев с интересными свойствами для эффективного управления большими множествами данных являются B-деревья.
Хотя для невырожденных двоичных деревьев их высота растет логарифмически с ростом числа вершин, все же реализация с помощью указателей приводит к заметным дополнительным затратам памяти для целей управления. Компромиссом здесь являются так называемые B-деревья. B-дерево либо пусто, либо содержит по меньшей мере n и самое большее 2n непосредственных поддеревьев. B-дерево над типом m, на котором пусть задан линейный порядок, является тогда элементом приведенного ниже объявления типа btree:
sort btree=emptyôcbt(btree first, seq cell rest)
sort cell=mc(m d, btree bt).
При этом для B-деревьев с порядком n предполагается, что все их последовательности поддеревьев содержат от n до 2n элементов. Элементы данных линейно упорядочены в последовательных вершинах. Таким образом, B-дерево есть упорядоченное дерево со степенью ветвимости между n и 2n.
Добавление элемента в B-дерево делается очень просто. Если для вершины последовательности не находится места (поскольку длина последовательности равна 2n), то эту последовательность можно разбить на две последовательности (длины n) и тем самым снова получить B-дерево.
На основании правил работы с массивами обеспечивается, что эти массивы всегда заполнены, по меньшей мере, наполовину. B-деревья используются, в частности, при хранении больших множеств данных во внешней памяти в связи с банками данных.
