B-дерево:бинарные деревья поиска

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

. В узком смысле, B-дерево хранит ключи в своих внутренних узлах, но не всегда хранит эти ключи в записях на листьях. Общий класс включает такие вариации, как дерево B+ и дерево B*.
В дереве B+ копии ключей хранятся во внутренних узлах; ключи и записи хранятся в листьях; кроме того, листовой узел может включать указатель на следующий листовой узел для ускорения последовательного доступа.
Дерево B * балансирует больше соседних внутренних узлов, чтобы держать внутренние узлы более плотно упакованными. Этот вариант гарантирует, что некорневые узлы по крайней мере на 2/3 заполнены вместо ½. Поскольку самой дорогостоящей частью операции вставки узла в B-дерево является разбиение узла, B * -деревья создаются, чтобы отложить операцию разбиения до тех пор, пока это возможно. Вместо того, чтобы сразу разделять узел, когда он становится полным, его ключи совместно используются с узлом рядом с ним. Эта операция менее затратна, чем разделение, поскольку она требует только перемещения ключей между существующими узлами, не выделяя память для нового узла. Для вставки сначала проверяется, есть ли в узле некоторое свободное пространство, и если да, то новый ключ просто вставляется в узел. Однако, если узел заполнен он должен быть проверен, существует ли правильный родственный элемент и имеет ли он некоторое свободное пространство.
Обычно алгоритмы сортировки и поиска характеризуются количеством операций сравнения, которые необходимо выполнить с использованием нотации порядка. Двоичный поиск отсортированной таблицы с N записями, например, можно выполнить примерно в log2(n) сравнений. Если бы таблица имела 1 000 000 записей, то конкретную запись можно было бы найти не более чем с 20 сравнениями: ⌈ log2(1 000 000) ⌉ = 20.
Поиск аналогичен поиску в двоичном дереве поиска