Изменения

Каждый узел дерева, кроме листьев, содержащий ключи <tex>k_1, ..., k_n</tex>, имеет <tex>n + 1</tex> сына. <tex>i</tex>-й сын содержит ключи из отрезка <tex>[k_{i - 1}; k_i],\: k_0 = -\infty,\: k_{n + 1} = \infty</tex>.

== Назначение ==

<wikitex>B-деревья разработаны для использования на дисках (в файловых системах) или иных вторичных устройствах хранения информации с прямым доступом, а также в базах данных. B-деревья походи на красно-чёрные деревья, но они лучше минимизируют количество операций чтения-записи в диске.

В типичном приложении с B-деревом, объём хранимой информации так велик, что вся она просто не может храниться в основной памяти единовременно. Алгоритмы B-дерева копируют выбранные страницы (мера информации на дисках; обычно, от $2^{11}$ до $2^{14}$ Байт) с диска в основную память по мере надобности и записывает обратно на диск страницы, которые были изменены. Алгоритмы B-дерева хранят лишь определённое количество страниц в основной памяти в любой момент времени; таким образом, объём основной памяти не ограничивает размер B-деревьев, которыми можно управлять.</wikitex>

== Операции ==

B-деревья представляют собой сбалансированные деревья, поэтому время выполнения стандартных операций в них пропорционально высоте. Однако, как уже было упомянуто выше, алгоритмы B-дерева созданы специально для работы с дисками (или другими носителями информации) и базами данных (или иными видами представления большого количества информация), минимизируя количество операций ввода-вывода.