Введение в B-деревья

B-деревья — это сбалансированные деревья поиска, разработанные для эффективной работы на дисковых накопителях или других устройствах вторичного хранения данных с прямым доступом. Они лучше минимизируют количество операций обращения к дискам. Это очень важно, поскольку магнитные диски работают гораздо медленнее, чем оперативная память. Узел B-дерева может иметь много дочерних узлов, от нескольких до тысяч. То есть «коэффициент ветвления» B-дерева может быть довольно большим, хотя обычно он зависит от характеристик используемого дискового накопителя. Если внутренний узел B-дерева x имеет 𝐧[𝐱] ключей, то у x есть 𝐧[𝐱]+𝟏 дочерних узлов. Ключевые моменты видео: 00:00:08 Структура B-дерева 00:01:20 Дисковые структуры данных 00:03:57 Шаблон работы с объектом x 00:05:19 Пример B-дерева высотой 2 с большим количеством ключей 00:07:24 Определение B-деревьев – поля узла 00:08:28 Каждый внутренний узел x также содержит x.n + 1 указателей x.c1, x.c2, …, x.c x.n+1 на свои дочерние узлы. Ключи x.keyi разделяют диапазоны ключей, хранящихся в каждом поддереве: если ki — любой ключ, хранящийся в поддереве с корнем x.ci, то k1 ≤ x.key1 ≤ k2 ≤ x.key2 ≤ ⋯ ≤ x.key x.n ≤ k x.n+1 00:10:07 нижние и верхние границы количества ключей