Изменения

}

</wikitex>

=== Удаление ключа ===

<wikitex>Находим ключ, который необходимо удалить

# Рассмотрим удаление из внутреннего узла. Имеется внутренний узел $x$ и ключ, который нужно удалить, $k$. Если дочерний узел, предшествующий ключу $k$ содержит больше $t - 1$ ключа, то находим $k_1$ – предшественника $k$ в поддереве этого узла. Удаляем его. Заменяем $k$ в исходном узле на $k_1$. Проделываем аналогичную работу, если дочерний узел, следующий за ключом $k$, имеет больше $t - 1$ ключа. Если оба (следующий и предшествующий дочерние узлы) имеют по $t - 1$ ключу, то объединяем этих детей, переносим в них $k$, а далее удаляем $k$ из нового узла. Если сливаются 2 последних потомка корня – то они становятся корнем, а предыдущий корень освобождается.

Для удаления требуется время $O(t log_t n)$ и $O(h)$ дисковых операций.</wikitex>

== Вариации B-дерева ==