B-дерево — это структура, в которой поиск, вставка и удаление держат все листья на одной глубине за счёт того, что узлы умеют расщепляться и сливатьсяобъединяться с соседним узлом, когда в узле остаётся меньше минимально допустимого числа ключей. Вопрос в том, как именно это устроено на уровне отдельного узла: почему переполнение наступает при строго определённом числе ключей, как выбирается дочерний указатель при спуске и что происходит с деревом, когда расщепление или слияниеобъединение дефицитного узла с соседом, при котором разделитель из родителя спускается вниз, а элементы соседа переезжают в один узел доходит до корня. Ниже — механика по шагам.
Спуск к листу: как выбирается указатель на поддерево
Поиск начинается с корня и рекурсивно идёт сверху вниз. На каждом уровне область поиска сужается до указателя на дочернее поддерево, чей диапазон включает искомое значение. Диапазон поддерева задаётся значениями (ключами) в его родительском узле — эти ключи называются разделяющими значениямиключи во внутреннем узле, которые задают границы диапазонов дочерних поддеревьев. Для выбора нужного разделяющего значения и дочернего дерева внутри узла обычно применяется двоичный поискпоиск в отсортированном массиве, который на каждом шаге делит область пополам.
Правило выбора указателя такое. Указатель на поддерево, в котором все ключи поиска Ptискомое значение, которое ищут в дереве удовлетворяют Pt < k0первое разделяющее значение в узле; при наличии ki−1разделяющее значение, стоящее перед ki и kiочередное разделяющее значение в узле — ki−1 < Pt < ki; при наличии только ki−1 — Pt > ki−1. Если ключ уже присутствует, используется указатель на запись со значением Prзначение, равное найденному разделяющему ключу ki = ki, то есть priуказатель на запись со значением, равным ki, когда ki существует, а не указатель на поддерево. В листовом узле pri при существующем ki указывает на запись со значением, равным ki, а при отсутствии ki этот указатель пуст.
Расщепление переполненного узла
Когда к уже заполненному узлу добавляется ещё один элемент, получается гипотетический узелузел, который возник бы, если добавить элемент к заполненному узлу, не проверяя переполнение с U элементами, где U — максимальное число детей внутреннего узла, а L — минимальное. При разбиении один элемент перемещается в родительский узел как разделитель, а оставшиеся U−2 элемента делятся на два допустимых узла.
Если U−1 нечётно, то U=2L, и один новый узел содержит (U−2)/2 = L−1 элементов, а другой — на один элемент больше; оба являются допустимыми. Если U−1 чётно, то U=2L−1, в узле 2L−2 элементов, половина этого числа равна L−1 — минимально допустимому числу элементов на узел. Средний ключ перемещается в родительский узел как разделитель.
Требование делимости U−1 на два допустимых узла нужно, чтобы после переноса одного элемента в родитель и добавления одного элемента оставшееся число элементов можно было поровну или почти поровну распределить между двумя узлами, каждый из которых удовлетворяет минимальному числу элементов.
Если расщепление доходит до корня, создаётся новый корень с одним разделительным значением и двумя детьми; поэтому нижняя граница размера внутренних узлов не применяется к корню. Максимальное число элементов в узле — U−1. При расщеплении узла один элемент переходит к родителю, но один элемент добавляется. Высота дерева увеличивается на один уровень, так как новый корень становится над старым корнем.
Пороги заполненности и их влияние на частоту расщеплений
По Кнуту B-дерево порядка mдерево, в котором каждый узел имеет не более m детей, а порядок m задаёт этот верхний предел числа детей устроено так: каждый узел имеет не более m детей; каждый узел, кроме корня и листьев, имеет не менее ⌈m/2⌉ детей; корневой узел имеет не менее двух детей, если только он не является листом; нелистовой узел с k детьми содержит k−1 ключей.
В терминах внутренних узлов: каждый внутренний узел содержит максимум U детей и минимум L детей, а число элементов всегда на 1 меньше числа указателей на детей (от L−1 до U−1), причём U равно либо 2L, либо 2L−1, поэтому каждый внутренний узел заполнен как минимум наполовину. Порядок m — это максимум детей, то есть U.
Для корня число детей имеет тот же верхний предел, что и у внутренних узлов, но не имеет нижнего предела: например, когда во всём дереве меньше L−1 элементов, корень будет единственным узлом без детей. Именно отсутствие нижнего предела у корня и позволяет дереву существовать с малым числом элементов.
Листовые узлы в терминологии Кнута — это сами объекты данных, а узлы на уровень выше хранят только ключи (не более m−1 и не менее m/2−1, если они не корень) и указатели на данные. Разные нижние границы у внутренних и листовых узлов объясняются тем, что в этой терминологии лист — это сам объект данных, а не узел дерева: узлы на уровень выше хранят только ключи и указатели на данные, поэтому их нижняя граница по числу ключей задаётся отдельно.
Отдельно вводятся два символа. dминимальное число ключей в не-корневом узле, которое поддерживается при удалении — это минимум ключей в не-корневом узле: при слиянии соседей «joining the neighbor would add d keys plus one more key brought down from the neighbor's parent», а при удалении требуется «maintain the d-key minimum for non-root nodes». Kверхняя граница числа ключей в узле, одинаковая для всего дерева — это «Maximum number of potential search keys for each node in a B-tree. (This value is constant over the entire tree.)».
Связь с числом детей задаётся правилом «A non-leaf node with k children contains k−1 keys», а по Кнуту порядок m — это максимум детей. Диапазон от d до 2d ключей возникает потому, что переполненный узел имеет 2d+1 ключей и расщепляется на двух соседей по d ключей, а слияние даёт полностью заполненный узел из 2d ключей.
Диапазон d..2d задаёт минимум d ключей и максимум 2d ключей в узле, где d — минимальное число ключей, а d+1 — минимальная степень (ветвление) дерева. Множитель 2 нужен, чтобы узел можно было расщепить: если в узле 2d ключей, добавление ключа даёт гипотетический узел на 2d+1 ключ, который делится на два узла по d ключей, а средний ключ уходит в родителя, и каждый из получившихся узлов имеет требуемый минимум ключей. Симметрично при удалении: если узел и его сосед имеют по d ключей, удаление ключа из узла (до d−1) компенсируется объединением с соседом, давая полностью заполненный узел на 2d ключей.
Баланс поддерживается при вставке расщеплением переполненного узла на 2d+1 ключ на двух соседей по d ключей с подъёмом среднего ключа в родителя; глубина растёт только при расщеплении корня. При удалении баланс поддерживается слиянием или перераспределением ключей между соседями для сохранения минимума d ключей у не-корневых узлов; глубина уменьшается на единицу, когда корень имеет двух детей с d и (переходно) d−1 ключами и они сливаются с родителем. Поскольку допускается диапазон числа детей, B-деревья не нуждаются в перебалансировке так часто, как другие самобалансирующиеся деревья, но могут тратить часть места впустую, так как узлы не заполнены полностью.
Удаление: заимствование у соседа и слияние
При удалении из листа значение просто удаляется из узла; если после этого возникает недозаполнениесостояние, когда в узле стало меньше минимально допустимого числа элементов, выполняется ребалансировка, начиная с этого листа.
При удалении из внутреннего узла элемент является разделителем для двух поддеревьев, поэтому выбирается новый разделитель — либо наибольший элемент в левом поддереве, либо наименьший в правом; оба находятся в листьях. Новый разделитель удаляется из листа, в котором он находится, и заменяет удаляемый элемент во внутреннем узле. Если после этого лист стал недозаполненным, ребалансировка начинается с этого листа.
Ребалансировка идёт от листа к корню. При наличии у соседа больше минимального числа элементов выполняется поворотперемещение одного элемента от соседа к дефицитному узлу через родителя: разделитель из родителя опускается в дефицитный узел, а на его место в родителе встаёт крайний элемент соседа, иначе выполняется слияние с соседом, что может привести к недозаполнению родителя и продолжить ребалансировку вверх.
Левый поворот
Левый поворот применяется, когда у дефицитного узла существует правый сосед и у этого соседа элементов больше минимума. Сначала разделитель из родителя копируется в конец дефицитного узла — разделитель «опускается» вниз, и дефицитный узел снова получает минимальное число элементов. Затем разделитель в родителе заменяется первым элементом правого соседа: правый сосед теряет один элемент, но всё ещё сохраняет не меньше минимума. После этого дерево снова сбалансировано.
Правый поворот
Правый поворот применяется, когда у дефицитного узла существует левый сосед и в нём больше минимального числа элементов. Сначала разделитель из родителя копируется в начало дефицитного узла — разделитель «опускается» вниз, и дефицитный узел получает минимальное число элементов. Затем разделитель в родителе заменяется последним элементом левого соседа: левый сосед теряет один элемент, но всё ещё сохраняет не меньше минимального числа элементов. После этого дерево снова сбалансировано.
Слияние
При слиянии дефицитного узла с соседом разделитель из родителя копируется в конец левого узла (левый узел может быть дефицитным или соседом с минимальным числом элементов). Затем все элементы из правого узла перемещаются в левый узел, после чего правый узел становится пустым. Из родителя удаляется разделитель вместе с его пустым правым потомком, и родитель теряет один элемент. Слияние применяется, когда оба непосредственных соседа имеют только минимальное количество элементов.
Если после удаления родитель оказывается корнем без элементов, он освобождается, а объединённый узел становится новым корнем; иначе, если в родителе меньше требуемого числа элементов, родитель ребалансируется.
Инвариант минимальной заполненности поддерживается после удаления перераспределением ключей между соседями (ротацией) или объединением (слиянием) узлов. Перераспределение применяется, когда у соседнего узла ключей больше минимума: тогда один ключ перемещается от соседа к обеднённому узлу через родителя. Если ни один сосед не может отдать ключ, обеднённый узел объединяется с соседом, при этом из родителя спускается разделяющий ключзначение в родительском узле, задающее границу между диапазонами его дочерних поддеревьев. Слияние уменьшает число ключей в родителе, поэтому родитель тоже может стать обеднённым и потребовать перераспределения или слияния — процесс идёт вверх к корню. Поскольку минимум не применяется к корню, ситуация, когда единственным обеднённым узлом оказывается корень, допустима.
Как дерево уменьшает высоту при удалении
Дерево уменьшает высоту, когда слияние доходит до корня: если у корня после слияния не осталось элементов, корень удаляется, а его единственный оставшийся ребёнок становится новым корнем, и высота дерева уменьшается на один уровень. Слияние запускается тогда, когда у недостающего узла нет соседа, который может отдать элемент. При этом родитель теряет разделяющий элемент и сам может стать недостающим. То, что корень остаётся единственным недостающим узлом, не является проблемой, так как минимальное число элементов к корню не применяется.
Пограничные случаи: чётное число ключей и выбор медианы
При расщеплении узла один элемент перемещается в родителя, а оставшиеся делятся на два законных узла. Если число элементов U−1 нечётно, то U=2L, и один новый узел получает (U−2)/2 = L−1 элементов, а другой — на один больше, то есть L; оба допустимы. Если U−1 чётно, то U=2L−1, в узле 2L−2 элементов, и половина от них равна L−1 — минимально допустимому числу элементов в узле.
Здесь U — верхняя граница числа детей внутреннего узла, а L — нижняя граница числа детей; число элементов в узле на единицу меньше числа указателей на детей. При альтернативном алгоритме с одним проходом сверху вниз, когда расщепление выполняется заранее без добавления нового элемента, требуется U = 2L, а не U = 2L−1. Именно это условие и объясняет, почему часть учебников накладывает такое требование в определении B-дерева.
Поиск и навигация в узле
Поиск ключа внутри узла выполняется через сравнение ключа x с отсортированными элементами узла и формирование битовой маски, по которой затем определяется номер дочернего узла.
В скалярном варианте маска строится циклом: для каждого элемента узла вычисляется результат сравнения с ключом, результат сдвигается на соответствующий номер бита и добавляется к маске, начиная со старшего разряда. Затем номер дочернего узла получается как позиция первого установленного бита в маске, найденная функцией ffsфункция, которая находит позицию первого установленного бита в маске, минус единица.
В векторном варианте сравнение выполняется сразу над группой из восьми отсортированных элементов: они загружаются одной векторной инструкцией, сравниваются с ключом, и из результата извлекается 8-битная маска. Для узла из 16 элементов маска собирается из двух таких сравнений со сдвигом второго на 8 бит, после чего берётся инверсия:
int mask = ~( cmp(x, &btree[k][0]) + (cmp(x, &btree[k][8]) << 8) );По этой маске с помощью ffs получают правильный номер дочернего узла и переходят к нему.
Как устроен страничный узел
Страничный узелспособ раскладки узла на странице фиксированного размера, при котором данные переменного размера адресуются через массив смещений (slotted page) состоит из трёх компонентов: заголовка с метаданными о странице, ячеек (cells) — «слотов» переменного размера для данных, и массива указателей-смещений (offset pointers) на эти ячейки.
В заголовке страницы SQLite хранятся как минимум два поля: первый байт задаёт тип страницыназначение страницы в дереве: лист таблицы хранит сами записи, а внутренний узел — ключи и ссылки на потомков, а поле cell count сообщает число записей на странице (например, 0x0003 — три записи). После заголовка идёт cell pointer index — список 2-байтовых значений, каждое из которых является смещением соответствующей записи внутри страницы; например, первая запись лежит по смещению 4 073 (0x0fe9), вторая — по 4 050 (0x0fd2). Число записей и смещения нужны при навигации: по ним находится нужная ячейка на странице.
Данные строк упаковываются в конец страницы и заполняются в обратном направлении, а между индексом указателей и областью содержимого остаются нули. Такая раскладка позволяет хранить данные переменного размера и логически переупорядочивать их, меняя лишь позиции указателей в массиве, а не перемещая сами данные.
Для навигации по дереву используются разделяющие ключиключи в текущем узле, по которым определяется дочерний узел, логически содержащий искомый ключ, и поиск рекурсивно продолжается вниз до листа.
Что из этого следует на практике
- Пороги заполненности — не произвольные числа. Минимум d и максимум 2d связаны так, что переполненный узел на 2d+1 ключ всегда делится на двух соседей по d ключей, а слияние двух узлов по d ключей даёт ровно полный узел на 2d ключей. Если выбрать границы иначе, расщепление или слияние перестанет укладываться в допустимые размеры.
- Расщепление и слияние распространяются вверх по дереву. Вставка увеличивает высоту только при расщеплении корня, удаление уменьшает её только при слиянии, дошедшем до корня. Во всех остальных случаях дерево остаётся на прежней глубине.
- Нижняя граница заполненности не применяется к корню. Поэтому дерево может существовать с малым числом элементов, а после слияния корень без элементов просто заменяется своим единственным ребёнком.
- Ребалансировка при удалении выбирает между поворотом и слиянием по одному признаку: есть ли у соседа запас сверх минимума. Поворот сохраняет число узлов, слияние уменьшает его и может поднять недозаполнение на уровень выше.
- Поиск внутри узла сводится к битовой маске и одному вызову ffs. Векторное сравнение собирает ту же маску из 8-битных фрагментов, поэтому скалярный и векторный варианты дают одинаковый номер дочернего узла.
- Раскладка страничного узла отделяет логический порядок от физического. Переупорядочивание записей выполняется сменой позиций указателей, а не перемещением данных, — это и делает страничный узел пригодным для хранения записей переменного размера.
