12. В-деревья
 

Для управления ростом дерева применение идеальной сбалансированности потребовало бы слишком больших затрат на балансировку, поэтому правила балансировки смягчают. Одной из распространенных структур такого типа является В-дерево. Эта структура была разработана Р.Бэйером и Э.Мак-Крейтом в 1972 г. В-деревом порядка п называется сильно ветвящееся дерево сте¬пени 2n + 1 (напомним, что степень узла — это число потомков узла, а степень дерева — наибольшее значение степени всех узлов дерева), обладающее следующими свойствами:
1)   каждый узел, за исключением корня, содержит не менее n и не более 2n ключей (элементов) при заданном постоянном для дерева n (n ≤ m ≤ 2n). Ключи узлов одного уровня упорядочены по возрастанию слева направо;
2)   корень содержит не менее одного и не более 2n ключей;
3)   каждый узел является либо листом, т.е. не имеет потомков, либо имеет (m + 1) потомков, где m — число находящихся в узле ключей;
4)   структура узла включает два массива. Первый массив из 2n ячеек предназна-чен для хранения элементов узла дерева. Второй массив из 2n + 1 ячеек содержит m + 1 указателей на потомков данного узла, остальные указатели — нулевые. Ес-тественно, в листовом узле массив указателей полностью свободен. Указатели деревьев на ВЗУ представляют собой адреса на диске;
5)   все листья дерева расположены на одном уровне.

Таким образом, в В - дереве порядка n с N элементами наихудший случай при поиске потребует log_nN обращений, на которые, как известно, при работе с ВЗУ тратится основная часть времени. Кроме того, коэффициент использования памяти в B-дереве составляет не менее 50%, так как страницы, содержащие узел, заполнены хотя бы наполовину.