B + дерево - B+ tree

Простой пример дерева B +, связывающий ключи 1–7 со значениями данных d ₁ -d ₇ . Связанный список (красный) позволяет быстро перемещаться по порядку. Фактор ветвления этого конкретного дерева = 4. ${\ displaystyle b}$

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

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

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

Все файловые системы ReiserFS , NSS , XFS , JFS , ReFS и BFS используют этот тип дерева для индексации метаданных; BFS также использует деревья B + для хранения каталогов. NTFS использует деревья B + для индексации метаданных каталогов и связанных с безопасностью. EXT4 использует деревья экстентов (модифицированная структура данных B + tree) для индексации экстентов файлов. APFS использует деревья B + для хранения сопоставлений идентификаторов объектов файловой системы с их местоположениями на диске, а также для хранения записей файловой системы (включая каталоги), хотя конечные узлы этих деревьев не имеют указателей-братьев. Системы управления реляционными базами данных, такие как IBM DB2 , Informix , Microsoft SQL Server , Oracle 8 , Sybase ASE и SQLite, поддерживают этот тип дерева для индексов таблиц. Системы управления базами данных типа "ключ-значение", такие как CouchDB и Tokyo Cabinet, поддерживают этот тип дерева для доступа к данным.

Обзор

Порядок или коэффициент ветвления b дерева B + измеряет емкость узлов (т. Е. Количество дочерних узлов) для внутренних узлов в дереве. Фактическое количество дочерних узлов для узла, обозначаемого здесь m , ограничено для внутренних узлов, так что . Корень является исключением: у него может быть всего два дочерних элемента. Например, если порядок дерева B + равен 7, каждый внутренний узел (кроме корня) может иметь от 4 до 7 дочерних узлов ; у корня может быть от 2 до 7. Конечные узлы не имеют потомков, но ограничены так, что количество ключей должно быть не меньше и не больше . В ситуации, когда дерево B + пусто или содержит один узел, корнем является единственный лист. Этому узлу разрешено не иметь ключей, если это необходимо и не больше . ${\ Displaystyle \ lceil b / 2 \ rceil \ leq m \ leq b}$${\ Displaystyle \ lceil b / 2 \ rceil}$${\ displaystyle b}$${\ displaystyle b-1}$

Тип узла	Тип детей	Мин. Количество детей	Максимальное количество детей	Пример ${\ displaystyle b = 7}$	Пример ${\ displaystyle b = 100}$
Корневой узел (когда это единственный узел в дереве)	Записи	0	${\ displaystyle b-1}$	0–6	1–99
Корневой узел	Внутренние узлы или конечные узлы	2	б	2–7	2–100
Внутренний узел	Внутренние узлы или конечные узлы	${\ Displaystyle \ lceil b / 2 \ rceil}$	б	4–7	50–100
Листовой узел	Записи	${\ Displaystyle \ lceil b / 2 \ rceil}$	${\ displaystyle b}$	4–7	50–100

Алгоритмы

Поиск

Корень B + Tree представляет собой весь диапазон значений в дереве, где каждый внутренний узел является подинтервалом.

Ищем значение k в B + Tree. Начиная с корня, мы ищем лист, который может содержать значение k . На каждом узле мы выясняем, по какому внутреннему указателю мы должны следовать. Внутренний узел B + Tree имеет не более ≤ дочерних элементов, каждый из которых представляет отдельный подинтервал. Мы выбираем соответствующий узел, выполняя поиск по ключевым значениям узла. ${\ displaystyle d}$${\ displaystyle b}$

function search(k) is
    return tree_search(k, root)

function: tree_search(k, node) is
    if node is a leaf then
        return node
    switch k do
    case k ≤ k_0
        return tree_search(k, p_0)
    case k_i < k ≤ k_{i+1}
        return tree_search(k, p_{i+1})
    case k_d < k
        return tree_search(k, p_{d})

Этот псевдокод предполагает, что дубликаты недопустимы.

Сжатие префиксного ключа

• Важно увеличить разветвление, так как это позволяет более эффективно направлять поиск на конечный уровень.
• Записи индекса предназначены только для «прямого трафика», поэтому мы можем их сжать.

Вставка

• Выполните поиск, чтобы определить, в какой сегмент должна помещаться новая запись.
• Если корзина не заполнена (максимум записей после вставки), добавьте запись. ${\ displaystyle b-1}$
• В противном случае перед вставкой новой записи
  • разделите ведро.
    • исходный узел имеет ⎡ (L + 1) / 2⎤ элементов
    • новый узел имеет ⎣ (L + 1) / 2⎦ элементов
  • Переместите ⎡ (L + 1) / 2⎤-й ключ в родительский и вставьте новый узел в родительский.
  • Повторяйте до тех пор, пока не найдете родителя, которого не нужно разделять.
• Если корень разделяется, относитесь к нему как к пустому родительскому элементу и разделяйте его, как показано выше.

B-деревья растут у корней, а не у листьев.

Массовая загрузка

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

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

Примечание :

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

Характеристики

Для б -ого обобщенного В + дереве с ч уровней индекса:

• Максимальное количество хранимых записей ${\ displaystyle n _ {\ max} = b ^ {h} -b ^ {h-1}}$
• Минимальное количество хранимых записей ${\ displaystyle n _ {\ min} = 2 \ left \ lceil {\ tfrac {b} {2}} \ right \ rceil ^ {h-1} -2 \ left \ lceil {\ tfrac {b} {2}} \ right \ rceil ^ {h-2}}$
• Минимальное количество ключей ${\ displaystyle n _ {\ mathrm {kmin}} = 2 \ left \ lceil {\ tfrac {b} {2}} \ right \ rceil ^ {h-1} -1}$
• Максимальное количество ключей ${\ displaystyle n _ {\ mathrm {kmax}} = b ^ {h} -1}$
• Пространство, необходимое для хранения дерева, составляет ${\ Displaystyle О (п)}$
• Вставка записи требует операций ${\ Displaystyle О (\ журнал _ {b} п)}$
• Для поиска записи требуются операции ${\ Displaystyle О (\ журнал _ {b} п)}$
• Для удаления (ранее расположенной) записи требуются операции ${\ Displaystyle О (\ журнал _ {b} п)}$
• Выполнение запроса диапазона с k элементами, встречающимися в пределах диапазона, требует операций ${\ Displaystyle О (\ журнал _ {b} п + к)}$

Выполнение

Листья (самые нижние индексные блоки) дерева B + часто связаны друг с другом в связанный список; это делает запросы диапазона или (упорядоченную) итерацию по блокам проще и эффективнее (хотя вышеупомянутая верхняя граница может быть достигнута даже без этого добавления). Это не приводит к значительному увеличению занимаемого места или ухода за деревом. Это иллюстрирует одно из значительных преимуществ B + -дерева перед B-деревом; в B-дереве, поскольку не все ключи присутствуют в листьях, такой упорядоченный связанный список не может быть построен. Таким образом, дерево B + особенно полезно в качестве индекса системы баз данных, где данные обычно находятся на диске, поскольку оно позволяет дереву B + фактически обеспечивать эффективную структуру для размещения самих данных (это описывается как структура индекса «Альтернатива 1 ").

Если система хранения имеет размер блока B байтов, а ключи, которые должны быть сохранены, имеют размер k, возможно, наиболее эффективным деревом B + является дерево, где . Хотя теоретически в одноразовой записи нет необходимости, на практике часто бывает немного лишнего места, занимаемого индексными блоками (например, ссылки на связанный список в конечных блоках). Наличие индексного блока, который немного больше, чем фактический блок системы хранения, означает значительное снижение производительности; поэтому предпочтительнее проявлять осторожность. ${\ displaystyle b = {\ tfrac {B} {k}} - 1}$

Если узлы дерева B + организованы как массивы элементов, то вставка или удаление элемента может занять значительное время, поскольку в среднем потребуется сдвинуть половину массива. Чтобы решить эту проблему, элементы внутри узла могут быть организованы в двоичное дерево или дерево B + вместо массива.

Деревья B + также могут использоваться для данных, хранящихся в ОЗУ. В этом случае разумным выбором для размера блока будет размер строки кэша процессора.

Пространственная эффективность деревьев B + может быть улучшена с помощью некоторых методов сжатия. Одна из возможностей - использовать дельта-кодирование для сжатия ключей, хранящихся в каждом блоке. Для внутренних блоков экономия места может быть достигнута за счет сжатия ключей или указателей. Для строковых ключей пространство можно сэкономить, используя следующую технику: Обычно i -я запись внутреннего блока содержит первый ключ блока . Вместо хранения полного ключа мы могли бы сохранить кратчайший префикс первого ключа блока, который строго больше (в лексикографическом порядке), чем последний ключ блока i . Существует также простой способ сжатия указателей: если мы предположим, что некоторые последовательные блоки хранятся непрерывно, тогда будет достаточно хранить только указатель на первый блок и количество последовательных блоков. ${\ displaystyle i + 1}$${\ displaystyle i + 1}$${\ Displaystyle я, я + 1, ... я + к}$

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

История

Дерево B было впервые описано в статье « Организация и ведение крупных упорядоченных индексов». Acta Informatica 1 : 173–189 (1972) Рудольфа Байера и Эдварда М. МакКрайта . Не существует единой статьи, представляющей концепцию дерева B +. Вместо этого идея сохранения всех данных в листовых узлах неоднократно упоминается как интересный вариант. Одним из первых исследований B-деревьев, также покрывающих B +-деревья, является Дуглас Комер . Комер отмечает, что дерево B + использовалось в программном обеспечении доступа к данным VSAM от IBM, и ссылается на опубликованную IBM статью 1973 года.

Смотрите также

• Дерево двоичного поиска
• B-дерево
• Алгоритм разделяй и властвуй

Рекомендации

Внешние ссылки

• Дерево B + в Python, используемое для реализации списка
• Примечания к индексу B + Tree доктора Монжа
• Оценка производительности CSB + -деревьев на многопоточных архитектурах
• Влияние размера узла на производительность B + -деревьев с учетом кеширования
• Фрактальная предварительная выборка B + -деревьев
• На пути к pB + -деревьям в полевых условиях: варианты реализации Выбор и производительность
• Структуры индекса с учетом кеширования для баз данных в основной памяти
• Cache Oblivious B (+) - деревья
• Сила B-деревьев: реализация B + Tree в CouchDB
• B + Визуализация дерева
• B + -деревья Кертту Поллари-Мальми
• Структуры данных B-деревья и B + деревья

Реализации

• Интерактивная реализация B + Tree на C
• Интерактивная реализация B + Tree на C ++
• Реализация B + дерева на основе памяти в виде библиотеки шаблонов C ++
• Улучшение предыдущего
• Реализация дерева B + на основе потоков в виде библиотеки шаблонов C ++
• Реализация B + Tree на JavaScript с открытым исходным кодом
• Реализация B + деревьев на Perl
• Реализации B + деревьев на Java / C # / Python
• C # B + tree и связанные структуры данных "A-List"
• B + Tree на основе файлов на C # с поддержкой потоков и MVCC
• Быстрое полупостоянное дерево B + в памяти на TypeScript / JavaScript, лицензия MIT
• JavaScript B + Tree, лицензия MIT
• JavaScript B + Tree, интерактивный и открытый исходный код