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