Структуры данных и модели вычислений


Б-деревья


Б-деревья — это один из видов сбалансированных деревьев, обеспечивающих эффективное хранение информации на магнитных дисках и других устройствах с прямым доступом. Б-деревья похожи на красно-черные, разница в том, что в Б-дереве узел может иметь много детей, на практике до тысячи, в зависимости от характеристик используемого диска. Благодаря этому константа в оценке для высоты дерева существенно меньше, чем для красно-черных деревьев. Как и красно-черные деревья, Б-деревья позволяют реализовать многие операции с множествами размера за время .

Узел, хранящийключей, имеетдетей. Хранящиеся в ключи служат границами, разделяющими всех его потомков на групп; за каждую группу отвечает один из потомков . При поиске в Б-дереве мы сравниваем искомый ключ с ключами, хранящимися в , и по результатам сравнения выбираем одного из потомков.




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



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