285
правок
Изменения
→Структура
B-дерево является идеально сбалансированным, то есть глубина всех его листьев одинакова.
<wikitex>
Каждый узел B-дерева, кроме корня, содержит от $t - 1$ до $2t - 1$ ключей. Корень содержит от $1$ до $2t - 1$ ключей. $t$ — параметр дерева, не меньший $2$. Каждый внутренний узел, не являющийся корневым, имеет,
таким образом, как минимум t дочерних узлов. Если дерево не является пустым, корень должен содержать как минимум один ключ. Ключи в каждом узле упорядочены. Мы говорим, что узел заполнен $(full)$, если он содержит ровно $2t — 1$ ключей.</wikitex>
Каждый узел B-дерева, кроме корнялистьев, содержит от содержащий ключи <tex>t - 1k_1, ..., k_n</tex> до , имеет <tex>2t - n + 1</tex> ключейсына. Корень содержит от <tex>1i</tex> до -й сын содержит ключи из отрезка <tex>2t [k_{i - 1</tex> ключей. <tex>t</tex> — параметр дерева}; k_i],\: k_0 = -\infty, не меньший <tex>2\: k_{n + 1} = \infty</tex>. Ключи в каждом узле упорядочены.
== Назначение ==
<wikitex>B-деревья разработаны для использования на дисках (в файловых системах) или иных вторичных устройствах хранения информации с прямым доступом, а также в базах данных. B-деревья похожи на красно-чёрные деревья, но они лучше минимизируют количество операций чтения-записи в диске.
