Конспект установочных лекций по комплексному курсу Информатика, Теория информации


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-деревья используются, в частности, при хранении больших множеств данных во внешней памяти в связи с банками данных.




- Начало -  - Назад -  - Вперед -



Книжный магазин