B-Tree

В этой теме мы разберем:

внутренние, корневые и листовые узлы;
использование В-дерева в базах данных;
поиск в отсортированном файле.

Введение в B-Tree

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

B-Tree порядка m — это дерево, удовлетворяющее следующим свойствам.

Каждый узел имеет не более m потомков.
Каждый внутренний узел имеет не менее ⌈m/2⌉ потомков.
У каждого нелистового узла есть как минимум два потомка.
Все листья появляются на одном уровне.
Нелистовой узел с k дочерними узлами содержит k-1 ключей.

Ключи каждого внутреннего узла действуют как значения разделения, которые делят его поддеревья. Например, если внутренний узел имеет 3 дочерних узла (или поддерева), то он должен иметь 2 ключа — 1 и 2 . Все значения в крайнем левом поддереве будут меньше 1, все значения в среднем поддереве будут между 1 и 2, а все значения в крайнем правом поддереве будут больше 2.

Внутренние узлы

Так называются все узлы, кроме листовых и корневого. Обычно они представлены в виде упорядоченного набора элементов и дочерних указателей. Каждый внутренний узел содержит максимум U потомков и минимум L потомков. Таким образом, количество элементов всегда на 1 меньше, чем количество дочерних указателей (количество элементов находится между L-1 и U-1). U должно быть либо 2L, либо 2L-1, поэтому каждый внутренний узел заполнен как минимум наполовину. Отношения между U и L подразумевают, что два наполовину заполненных узла могут быть соединены, чтобы создать допустимый узел, а один полный узел может быть разделен на два допустимых узла (если есть место, чтобы вставить один элемент в родителя). Эти свойства позволяют удалять и вставлять новые значения в B-Tree, а также настраивать дерево для сохранения свойств B-Tree.

Корневой узел

Количество дочерних узлов корневого узла имеет тот же верхний предел, что и внутренние узлы, но не имеет нижнего предела. Например, когда во всем дереве меньше L-1 элементов, корень будет единственным узлом в дереве без дочерних узлов.

Листовые узлы

Листовые узлы — это фактические объекты/фрагменты данных. Внутренние узлы на один уровень выше этих листовых узлов: эти узлы хранят только ключи (не более m-1 и не менее m/2-1, если они не являются корневыми) и указатели на узлы (по одному для каждого ключа), несущие объекты/фрагменты данных.

B-дерево глубины n+1 может содержать примерно в U раз больше элементов, чем B-дерево глубины n, но стоимость операций поиска, вставки и удаления растет с глубиной дерева. Как и в любом сбалансированном дереве, стоимость растет гораздо медленнее, чем количество элементов.

Некоторые сбалансированные деревья хранят значения только в конечных узлах и используют разные типы узлов для конечных и внутренних узлов. B-деревья хранят значения в каждом узле дерева, кроме конечных.