Глава 2. Основы B- деревьев

Мы отважней чем пчёлы, и ух... длиннее чем деревья...

Винни Пух

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

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

В большинстве литературных источников узлы двоичных деревьев рисуются окружностями. Так как каждый узел отвечает только за один ключ и расщепляет свой диапазон на две части, такого уровня подробности достаточно и он интуитивно ясен. В то же самое время, узлы B- дерева часто изображаются прямоугольниками, а блоки указателей также отражаются в явном виде для выделения имеющейся взаимосвязи между дочерними узлами и ключами разделителя. Рисунок 2-7 показывает двоичное дерево, дерево 2-3 и узлы B- дерева бок о бок, что помогает понять сходства и различия между ними.

Ничто не мешает нам перерисовать двоичное дерево точно так же. Обе структуры имеют аналогичную семантику следования указателям, а отличия начинают проявляться в том как сопровождается их балансировка. Рисунок 2-8 показывает это наводит на мысль о сходстве между BST и B- деревьями: в обоих случаях ключи расщепляют само дерево на поддеревья и применяются для навигации по самом у дереву и поиска искомых ключей. Вы можете сравнить его с Рисунком 2-1.

B- деревья сортированы: ключи внутри самого узла B- дерева находятся в порядке сортировки. Благодаря этому, для определения места некого искомого ключа мы можем применять некий алгоритм, подобный двоичному поиску. Это также подразумевает, что поиск по B- деревьям обладает логарифмической сложностью. Например, поиск искомого ключа среди 4 миллиардов (4 × 109) элементов занимает около 32 сравнений (см. Сложность поиска в В- деревьях для дополнительных сведений по этому вопросу). Когда нам приходится выполнять дисковое позиционирование для каждого из таких сравнений, это значительно замедлило бы нас, но так как узлы B- дерева хранят десятки и даже сотни элементов, нам всего лишь придётся выполнят по одному позиционированию диска для прыжка на следующий уровень. Позднее в этой главе мы обсудим алгоритм поиска более подробно.

При помощи B- деревьев мы можем действенно выполнять как запросы указания, так и запросы диапазона. Запросы указания, выражаемые в большинстве языков запросов знаком предиката равенства (=) определяют место единственного элемента. С другой стороны, запросы диапазона, выражаемые символами предикатов сравнения (<, >, ≤ и ≥) используются для запроса множества элементов данных в распоряжении.

B- состоят из множества узлов. Каждый узел содержит до N ключей и N + 1 указателей на его дочерние узлы. Эти узлы логически разбиваются на три группы:

Эта иерархия показана на Рисунке 2-9.

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

Значение соотношения между ёмкостью такого узла и общим числом ключей, которое он способен содержать именуется заполнением (occupancy).

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

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

Самый первый указатель в таком узле указывает на то поддерево, которое содержит элементы меньше чем значение первого ключа, а самый последний указатель в этом узле указывает на то поддерево, которое содержит элементы больше чем или равные значению для самого последнего ключа. Прочие указатели ссылаются на поддеревья между значениями двух ключей: Ki-1 ≤ Ks < Ki, где K это множество ключей, а Ks это относящийся к определённому поддереву ключ. Рисунок 2-10 отображает такие инварианты.

Некоторые варианты поддеревьев также имеет братские указатели узлов, причём чаще всего на их уровне листьев для упрощения сканирования по диапазону. Такие указатели способствуют обходу возврата к своему родителю для обнаружения своего следующего брата. Некоторые реализации имеют указатели в обоих направлениях, формируя некий двунаправленный список связей на своём уровне листьев, что делает возможным обратные итерации.

Что отличает B- деревья, так это то, что они не создаются сверху вниз (в виде бинарных деревьев поиска), а наоборот - снизу вверх. Общее число листовых узлов растёт, что увеличивает общее число внутренних узлов и высоту дерева.

Поскольку B- деревья резервируют дополнительное пространство внутри узлов для последующих вставок и обновлений, использование хранилища дерева может достигать 50%, но обычно наблюдаются более высокие значения. Более высокая загруженность не оказывает влияние на производительность B- деревьев.

Сложность поиска в B- дереве может быть представлен с двух точек зрения: общего числа блочного обмена и общего числа сравнений, осуществляемых в процессе такого поиска.

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

С точки зрения числа сравнений, значением основания логарифма является 2, так как поиск ключа внутри каждого узла осуществляется при помощи двоичного поиска. Каждое сравнение делит пополам пространство поиска, поэтому сложность равна log2 M.

Знание такого отличия между общим числом позиционирований и общим числом сравнений помогает нам получить интуитивное понимание относительно того как выполняются поиски и осознание какова сложность поиска, причём с обеих точек зрения.

В учебных руководствах и статьях (например, [KNUTH98]), сложность поиска в B- дереве обычно приводится как log M. В анализе сложности обычно не используется основание логарифма, так как изменение значения основания просто добавляет некий постоянный множитель, а умножение на некий постоянный множитель не изменяет сложность. Например, имея ненулевое значение постоянного множителя c, O(|c| × n) == O(n) [KNUTH97].

Теперь, когда мы рассмотрели саму структуру и внутреннюю организацию B- деревьев, мы можем определить алгоритмы для поиска, вставки и удалений. Для поиска некой записи в B- дереве нам приходится выполнять отдельный просмотр от корня до листа. Предметом такого поиска является обнаружение искомого ключа или его предка. Обнаружение точного соответствия применяется для запросов указания, обновлений и удалений; поиск его предка полезен для сканирований и вставок диапазона.

Такой алгоритм запускается с самого корня и осуществляет двоичный поиск, сравнивая значение искомого ключа с теми ключами, которые в узле самого корня пока не отыщет самый первый ключ разделителя, который больше чем величина искомого значения. Это определяет место искомого поддерева. Как мы уже обсуждали ранее, ключи индекса расщепляют своё дерево на поддеревья с границами между двумя соседними ключами. Как только мы находим искомое поддерево, мы следуем за тем указателем, который соответствует ему и продолжает тот же самый процесс поиска (определяет место значения ключа разделителя, следуя за его указателем) пока мы не достигнем некого целевого терминального узла, в котором мы либо обнаруживаем искомый ключ или делаем заключение что он не представлен в своём предке.

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

В процессе своего запроса указания данный поиск выполнен после обнаружения или неудачного результата для значения искомого ключа. На протяжении соответствующего сканирования диапазона итерации начинают с самого ближней найденной пары ключ- значение и продолжается по последующим братским указателям {того же самого уровня родства} пока не будет достигнут конец этого диапазона или не используется весь диапазон предиката.

В относящейся к данной теме литературе вы можете обнаружить различные способы описания счётчиков ключа и дочерних смещений. [BAYER72] ссылается на определённое зависящее от устройства натуральное число k, которое представляет некий оптимальный размер страницы. В этом случае страницы способны содержать от k до 2k ключей, однако может быть частично заполненной от по крайней мере k + 1 и максимально 2k + 1 указателями на дочерние узлы. Узел корня может содержать от 1 до 2k ключей. Далее вводится некое число l и утверждается, что любая нетерминальная страница может иметь l + 1 ключей.

Другие источники, к примеру, [GRAEFE11], описывают узлы как способные содержать до N ключей разделителей и N + 1 указателей, в остальном семантика и инварианты аналогичны.

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

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

Когда наш целевой узел не обладает достаточным доступным пространством, мы говорим что этот узел переполнен [NICHOLS66] и приходится расщеплять его на два для помещения таких новых данных. Более точно, этот узел расщепляется при соблюдении следующих условий:

Расщепление осуществляется посредством выделения необходимого нового узла, переноса в него половины его элементов из подвергающегося расщеплению узла и добавления его самого первого ключа и указателя в его родительский узел. В таком случае мы говорим что продвигается (promoted) новый ключ. Значение индекса, в котором выполняется данное расщепление имеет название точкой расщепления (также именующейся его средней точкой). Все элементы после такой точки расщепления (включая точку расщепления в случае деления нетерминального узла) перемещаются в такой вновь создаваемый братский {того же самого родственного уровня} узел, а все остальные элементы остаются в самом делимом узле.

Когда наш родительский узел заполнен и не обладает доступным пространством для таких продвигаемых ключа и указателя для своего вновь создаваемого узла, он также должен быть расщеплён. Эта операция может рекурсивно распространяться по всему пути до его корня.

После того как наше дерево достигает своей ёмкости (то есть расщепление преодолело весь путь вверх до своего корня), нам приходится расщеплять сам узел корня. После расщепления своего узла корня, выделяется некий новый корень, содержащий ключ точки расщепления. Наш старый корень (теперь содержащий лишь половину своих записей) переводится на свой следующий уровень совместно с его вновь созданным собратом, увеличивая значение высоты дерева на единицу. Значение высоты дерева изменяется при расщеплении его узла корня и выделении нового корня или когда два узла сливаются для формирования некого нового узла. На уровнях терминальных и промежуточных узлов само дерево растёт лишь горизонтально.

Рисунок 2-11 отображает полностью заполненный терминальный узел в процессе вставки своего нового элемента 11. В самой середине такого заполненного узла мы проводим соответствующую линию, оставляя половину его элементов в самом узле и перемещая все остальные элементы во вновь создаваемый. Значение точки расщепления помещается в их родительский узел для того чтобы служить ключом разделителя.

Рисунок 2-12 показывает соответствующий процесс расщепления полностью заполненного нетерминального (то есть корневого или внутреннего) узла в процессе вставки нашего нового элемента 11. Для выполнения расщепления мы вначале создаём какой- то новый узел и перемещаем в него элементы, начинающиеся с индекса N/2 + 1. Сама точка расщепления продвигается в своего родителя.

Поскольку расщепления нетерминального узла всегда некое олицетворение распространяемых с располагающихся ниже уровней расщеплений, мы получаем некий дополнительный указатель (на вновь создаваемый узел в своём следующем уровне). Когда его родитель не обладает достаточным пространством, его также приходится расщеплять.

Не имеет значения расщепляется ли терминальный или нетерминальный узел (то есть содержит ли этот узел ключи и значения или только сами ключи). В случае расщепления листа, ключи перемещаются совместно со связанными с ними значениями.

После завершения такого расщепления у нас имеются два узла и приходится прикрепляться к правильному для завершения вставки. Для этого мы можем применять инварианты значения ключа вставки. Если значение вставляемого ключа меньше чем значение продвигаемого, мы завершаем операцию вставкой в сам расщепляемый узел. В противном случае мы выполняем вставку во вновь созданный.

Чтобы подвести итог, расщепление узла выполняется четырьмя шагами:

Для удалений прежде всего нам необходимо определить место своего целевого листа. Когда этот лист найден, удаляются связанные с ним ключ и значение.

Если соседние узлы имеют слишком мало значений (то есть когда их занятость падает ниже порогового значения), такие находящиеся на одном родственном уровне узлы сливаются. Подобный случай имеет название потерей значимости (underflow, антипереполнением). [BAYER72] определяет два сценария потери значимости: если два смежных узла имеют общего предка и их содержимые помещаются в один узел, их содержимое следует слить (выполнить конкатенацию); когда их содержимое не умещается в одном узле, ключи перераспределяются между ними для восстановления баланса (см. Повторная балансировка). Более точно, два узла сливаются когда имеют место следующие обстоятельства:

Рисунок 2-13 показывает слияние при удалении элемента 15. Для этого мы перемещаем элементы из одного из братьев в другой. Как правило, элементы из первого брата перемещаются в левого, но это может быть выполнено и иначе когда фиксирована соответствующий порядок ключа.

Рисунок 2-14 показывает два нетерминальных узла одного родственного уровня, которые подлежат слиянию в процессе удаления элемента 10. Когда мы соединяем их элементы, они помещаются в одном узле, поэтому мы можем иметь один узел вместо двух. В процессе слияния нетерминальных узлов, нам приходится вытолкнуть соответствующий ключ разделителя из их родителей (то есть понизить его). Общее число указателей уменьшается на один, так как подобное слияние является продвижением удаления соответствующего указателя с нижнего уровня, вызывающего удаления надлежащей страницы. В точности как и при расщеплении, слияние способно продвигаться по всему пути до уровня корня.

Итак, чтобы суммировать, слияние узлов выполняется в три шага, в предположении что соответствующий элемент уже удалён:

Одной из технологий, часто реализуемой в B- деревьях для снижения общего числа расщеплений и слияний является ребалансировка, которая обсуждается в разделе Повторная балансировка.

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

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

Мы можем применять эти знания для создания B- деревьев в памяти. Для создания дисковой реализации нам потребуется углубиться в подробности того как выкладывать узлы B- дерева на диск и составить схему диска при помощи форматов кодирования данных.