B + дерево

редактировать

B + tree

Временная сложность в нотации большого O

Алгоритм	Среднее значение	Худший случай
Пробел	O (n)	O (n)
Поиск	O (log n)	O (log n + log L)
Вставить	O (log n)	O (M * log n + log L)
Удалить	O (log n)	O (M * log n + log L)

Простой пример дерева B +, связывающий ключи 1–7 со значениями данных d 1-d7. Связанный список (красный) позволяет быстро перемещаться по порядку. Фактор ветвления этого конкретного дерева равен

b {\ displaystyle b}

b

= 4.

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

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

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

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

Содержание

1 Обзор
2 Алгоритмы
- 2.1 Поиск
- 2.2 Сжатие префиксного ключа
- 2.3 Вставка
- 2.4 Массовая загрузка
3 Характеристики
4 Реализация
5 История
6 См. Также
7 Ссылки
8 Внешние ссылки
- 8.1 Реализации

Обзор

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

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

Алгоритмы

Поиск

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

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

функция search (k) isreturn tree_search (k, root)

function : tree_search (k, node) isifnode is a leaf then return node switch k docase 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 Этот псевдокод предполагает, что нет дубликаты разрешены.
Сжатие префиксного ключа
Важно увеличить разветвление, так как это позволяет более эффективно направлять поиск на конечный уровень.
Записи индекса предназначены только для «прямого трафика», поэтому мы может их сжать.
Вставка
Выполните поиск, чтобы определить, в какой сегмент должна помещаться новая запись.
Если сегмент не заполнен (максимум  $b - 1 {\ displaystyle b -1}$  $b-1$ записей после вставки), добавьте запись.
В противном случае, перед вставкой новой записи разделите сегмент. исходный узел имеет ⎡ (L + 1) / 2⎤ элементов
новый узел имеет ⎣ (L + 1) / 2⎦ элементов
Переместить ⎡ (L + 1) / 2 ⎤ -ый ключ к родительскому и вставьте новый узел в родительский.
Повторяйте до тех пор, пока не будет найден родительский элемент, который не нужно разделять.
Если корень разделяется, относитесь к нему так, как если бы он имел пустой родительский и разделенный, как указано выше.
B-деревья растут у корня, а не у листьев.
Массовая загрузка
Учитывая набор записей данных, мы хотим создать Индекс дерева B + по некоторому ключевому полю. Один из подходов - вставить каждую запись в пустое дерево. Однако это довольно дорого, потому что каждая запись требует, чтобы мы начинали с корня и спускались до соответствующей конечной страницы. Эффективная альтернатива - использовать массовую загрузку.
Первый шаг - отсортировать записи данных в соответствии с ключом поиска в порядке возрастания.
Мы выделяем пустую страницу в качестве корня и вставляем в нее указатель на первую страницу записей.
Когда корень заполнен, мы разделяем корень и создаем новую корневую страницу.
Продолжайте вставлять записи в крайнюю правую страницу индекса чуть выше конечного уровня, пока все записи не будут проиндексировано.
Примечание:
когда крайняя правая страница индекса выше конечного уровня заполняется, она разделяется;
это действие может, в свою очередь, вызвать разделение крайнего правого индекса страница на один шаг ближе к корню;
разделение происходит только на крайнем правом пути от корня до конечного уровня.
Характеристики
Для дерева B + b-порядка с h уровни индекса:
Максимальное количество сохраняемых записей:  $n max = bh - bh - 1 {\ displaystyle n _ {\ max} = b ^ {h} -b ^ {h-1}}$  ${\ displaystyle n _ {\ max} = b ^ {h} -b ^ {h-1}}$ 
Минимальное количество сохраняемых записей:  $n min = 2 ⌈ b 2 ⌉ h - 1-2 ⌈ b 2 ⌉ h - 2 {\ 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 _ {\ min} = 2 \ левый \ lceil {\ tfrac {b} {2}} \ right \ rceil ^ {h-1} -2 \ left \ lceil {\ tfrac {b} {2}} \ right \ rceil ^ {h-2}}$ 
минимальное количество ключей составляет  $nkmin = 2 ⌈ b 2 ⌉ h - 1-1 {\ displaystyle n _ {\ mathrm {kmin}} = 2 \ left \ lceil {\ tfrac {b} {2}} \ right \ rceil ^ {h-1} -1}$  ${\ displaystyle n _ {\ mathrm {kmin}} = 2 \ left \ lceil {\ tfrac {b} {2}} \ right \ rceil ^ {h-1} -1}$ 
Максимальное количество ключей:  $nkmax = bh - 1 {\ displaystyle n _ {\ mathrm {kmax}} = b ^ {h} -1}$  ${\ displaystyle n _ {\ mathrm {kmax}} = b ^ {h} -1}$ 
Для хранения дерева требуется  $O (n) {\ displaystyle O (n)}$  $O (n)$ 
Для вставки записи требуется  $O (log b ⁡ n) {\ displaystyle O (\ log _ {b } n)}$  $О (\ log _ {b} n)$ операции
Для поиска записи требуется  $O (log b ⁡ n) {\ displaystyle O (\ log _ {b} n)}$  $О (\ log _ {b} n)$ операции
Для удаления (ранее расположенной) записи требуется  $O (log b ⁡ n) {\ displaystyle O (\ log _ {b} n)}$  $О (\ log _ {b} n)$ операций
Выполнение запроса диапазона с k элементами, встречающимися внутри диапазона, требует  $O (log b ⁡ n + k) {\ displaystyle O (\ log _ {b} n + k)}$  $O (\ log _ {b} n + k)$ операций
Реализация
Листы (самые нижние индексные блоки) B + деревья часто связаны друг с другом в связном списке; это делает запросы диапазона или (упорядоченную) итерацию по блокам более простым и эффективным (хотя вышеупомянутая верхняя граница может быть достигнута даже без этого добавления). Это не приводит к значительному увеличению занимаемого места или ухода за деревом. Это иллюстрирует одно из значительных преимуществ B + -дерева перед B-деревом; в B-дереве, поскольку не все ключи присутствуют в листьях, такой упорядоченный связанный список не может быть построен. Таким образом, дерево B + особенно полезно в качестве индекса системы баз данных, где данные обычно находятся на диске, поскольку оно позволяет дереву B + фактически обеспечивать эффективную структуру для размещения самих данных (это описывается как структура индекса «Альтернатива 1 ").
Если система хранения имеет размер блока B байтов, а ключи, которые должны быть сохранены, имеют размер k, возможно, наиболее эффективным деревом B + является такое, где  $b = B k - 1 {\ displaystyle b = {\ tfrac {B} {k}} - 1}$  ${\ displaystyle b = {\ tfrac {B} {k}} - 1}$ . Хотя теоретически в одноразовой записи нет необходимости, на практике часто бывает немного дополнительного места, занимаемого индексными блоками (например, ссылки на связанный список в конечных блоках). Наличие индексного блока, который немного больше, чем фактический блок системы хранения, означает значительное снижение производительности; поэтому предпочтительнее проявлять осторожность.
Если узлы дерева B + организованы как массивы элементов, то вставка или удаление элемента может занять значительное время, поскольку в среднем потребуется сдвинуть половину массива. Чтобы решить эту проблему, элементы внутри узла могут быть организованы в двоичное дерево или дерево B + вместо массива.
B + деревья также могут использоваться для данных, хранящихся в RAM. В этом случае разумным выбором для размера блока будет размер строки кэша процессора.
Эффективность использования пространства для деревьев B + может быть улучшена с помощью некоторых методов сжатия. Одна из возможностей - использовать дельта-кодирование для сжатия ключей, хранящихся в каждом блоке. Для внутренних блоков экономия места может быть достигнута за счет сжатия ключей или указателей. Для строковых ключей пространство можно сэкономить, используя следующую технику: Обычно i-я запись внутреннего блока содержит первый ключ блока  $i + 1 {\ displaystyle i + 1}$  $i+1$ . Вместо хранения полного ключа мы могли бы сохранить кратчайший префикс первого ключа блока  $i + 1 {\ displaystyle i + 1}$  $i+1$ , который строго больше (в лексикографическом порядке), чем последний ключ блока i. Существует также простой способ сжатия указателей: если предположить, что некоторые последовательные блоки  $i, i + 1,... i + k {\ displaystyle i, i + 1,... i + k}$  ${\ displaystyle i, i + 1,... я + k}$ хранятся непрерывно, тогда будет достаточно сохранить только указатель на первый блок и количество последовательных блоков.
Все вышеупомянутые методы сжатия имеют некоторые недостатки. Во-первых, необходимо распаковать полный блок, чтобы извлечь единственный элемент. Один из методов решения этой проблемы - разделить каждый блок на подблоки и сжать их отдельно. В этом случае при поиске или вставке элемента потребуется только распаковать или сжать субблок, а не весь блок. Другой недостаток методов сжатия заключается в том, что количество хранимых элементов может значительно варьироваться от блока к другому в зависимости от того, насколько хорошо элементы сжаты внутри каждого блока.
История
B-дерево впервые было описано в статье «Организация и обслуживание крупных упорядоченных индексов». Acta Informatica 1: 173–189 (1972) Рудольф Байер и Эдвард М. МакКрейт. Не существует единой статьи, представляющей концепцию дерева B +. Вместо этого идея сохранения всех данных в листовых узлах неоднократно упоминается как интересный вариант. Ранний обзор B-деревьев, также покрывающих B +-деревья, - это Дуглас Комер. Комер отмечает, что дерево B + использовалось в программном обеспечении доступа к данным IBM VSAM, и он ссылается на опубликованную IBM статью 1973 года.
См. Также
Дерево двоичного поиска 
B- дерево 
Алгоритм разделяй и властвуй 
Ссылки
Внешние ссылки
В Викиучебнике есть книга по теме: Реализация алгоритма / Деревья / B + дерево 
Wikimedia Commons содержит носители, относящиеся к B-деревьям.
B + дереву в Python, используемому для реализации списка 
Dr. Примечания к индексу B + Tree от Monge 
Оценка производительности CSB + -деревьев на многопоточных архитектурах 
Влияние размера узла на производительность B + -деревьев с учетом кеширования 
Фрактальная предварительная выборка B + -деревьев 
К pB + -деревьям в поле: реализации Выбор и производительность 
Структуры индекса с учетом кэша для баз данных в основной памяти 
Cache Oblivious B (+) - деревья 
Сила B-деревьев: CouchDB B + реализация дерева 
B + Tree Визуализация 
B + -деревья от Kerttu Pollari-Malmi 
Структуры данных B-деревья и B + деревья 
Реализации
Реализация интерактивного B +-дерева в C 
Интерактивная реализация B +-дерева в C ++ 
Память реализация дерева B + на основе библиотеки шаблонов C ++ 
Реализация дерева B + на основе потока как библиотека шаблонов C ++ 
Реализация дерева B + с открытым исходным кодом 
Реализация деревьев B + на Perl 
Реализации деревьев B + на Java / C # / Python 
Дерево B + C # и связанные структуры данных «A-List» 
Дерево B + на основе файлов в C # с потоком добавление и поддержка MVCC 
Быстрое полупостоянное B + дерево в памяти в TypeScript / JavaScript, лицензия MIT 
JavaScript B + Tree, лицензия MIT 
JavaScript B + Tree, Interactive and Open Source