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

B + дерево
Тип	Дерево (структура данных)
Сложность времени в нотация большой O

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

{ displaystyle b}

=4.

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

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

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

В ReiserFS, НСС, XFS, JFS, ReFS, и BFS все файловые системы используют этот тип дерева для индексации метаданных; BFS также использует деревья B + для хранения каталогов. NTFS использует деревья B + для индексации метаданных, связанных с каталогами и безопасностью. EXT4 использует деревья экстентов (модифицированная структура данных B + tree) для индексации экстентов файлов.^[3] Системы управления реляционными базами данных Такие как IBM DB2,^[4] Informix,^[4] Microsoft SQL Server,^[4] Оракул 8,^[4] Sybase ASE,^[4] и SQLite^[5] поддерживают этот тип дерева для индексов таблиц. Системы управления базами данных типа "ключ-значение", такие как CouchDB^[6] и Токийский кабинет^[7] поддерживают этот тип дерева для доступа к данным.

Обзор

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

Тип узла	Тип детей	Мин. Количество детей	Максимальное количество детей	Пример ${ displaystyle b = 7}$	Пример ${ displaystyle b = 100}$
Корневой узел (когда это единственный узел в дереве)	Записи	1	${ displaystyle b-1}$	1–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 +. Начиная с корня, ищем лист, который может содержать значение k. На каждом узле мы выясняем, по какому внутреннему указателю мы должны следовать. Внутренний узел B + Tree имеет не более ${ displaystyle d}$ ≤ ${ displaystyle b}$ children, где каждый из них представляет отдельный подинтервал. Мы выбираем соответствующий узел, выполняя поиск по ключевым значениям узла.

функция поиск(k) является    возвращаться tree_search (k, корень)

функция: tree_search (k, узел) является    если узел - это лист тогда        возвращаться узел выключатель k делать    дело k ≤ k_0 возвращаться tree_search (k, p_0) дело k_i возвращаться tree_search (k, p_ {i + 1}) дело k_d возвращаться tree_search (k, p_ {d})

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

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

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

Вставка

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

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

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

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

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

Примечание :

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

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

Для $б$ -дерево порядка 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 п _ { 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 + фактически обеспечивать эффективную структуру для размещения самих данных (это описано в^[4]^:238 как индексная структура «Альтернатива 1»).

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

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

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

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

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

История

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

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

внешняя ссылка

Реализации

[Navathe-1] а ^б ^c ^d Навате, Рамез Эльмасри, Шамкант Б. (2010). Основы систем баз данных (6-е изд.). Верхняя Сэдл-Ривер, Нью-Джерси: Pearson Education. С. 652–660. ISBN 9780136086208.

[2] ttp://www.seanster.com/BplusTree/BplusTree.html

[practical-book-3] Джампаоло, Доминик (1999). Практическое проектирование файловой системы с файловой системой Be (PDF). Морган Кауфманн. ISBN 1-55860-497-9. Архивировано из оригинал (PDF) на 2017-02-13. Получено 2014-07-29.

[DMS-4] а ^б ^c ^d ^е ^ж Рамакришнан Рагу, Герке Йоханнес - Системы управления базами данных, Высшее образование Макгроу-Хилл (2000), 2-е издание (en), стр. 267

[SQLite-5] Обзор SQLite версии 3

[CouchDB-6] Руководство CouchDB (см. Примечание после 3-го абзаца)

[TC-7] Ссылка на Токийский кабинет В архиве 12 сентября 2009 г. Wayback Machine

[8] "ECS 165B: Лекция 6 по внедрению системы баз данных" (PDF). UC Davis CS отдел. 9 апреля 2010 г. С. 21–23.

[9] "Вездесущее B-дерево ", ACM Computing Surveys 11 (2): 121–137 (1979).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Древовидные структуры данных
Деревья поиска (динамические наборы /ассоциативные массивы )	2–3 2–3–4 AA (а, б) AVL B B + B * B^Икс (Оптимально ) Бинарный поиск Танцы HTree Интервал Статистика заказов (Левый ) Красный – черный Козел отпущения Splay Т Treap UB Сбалансированный по весу
Кучи	Двоичный Биномиальный Brodal Фибоначчи Левый Сопряжение Перекос ван Эмде Боас Слабый
Пытается	Ctrie C-trie (сжатый ADT) Хеш Radix Суффикс Тернарный поиск X-быстрый Y-быстро
Пространственный деревья разделения данных	Мяч BK BSP Декартово Гильберт Р k-d (скрытый k-d ) M Метрическая MVP Octree Приоритет R Quad р R + Р* Сегмент Вице-президент Икс
Другие деревья	Крышка Экспоненциальный Фенвик Палец Индекс фрактального дерева Слияние Хеш-календарь iDistance K-арый Левый ребенок, правый брат Ссылка / вырезать Лог-структурированное слияние Меркл PQ Классифицировать SPQR Вершина