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

Не путать с Двоичное дерево.

B-дерево
Тип	Дерево (структура данных)
Изобрел	1970[1]
Изобретенный	Рудольф Байер, Эдвард М. МакКрайт
Сложность времени в нотация большой O
Алгоритм Средний Худший случай Космос O (п) O (п) Поиск O (журнал п) O (журнал п) Вставлять O (журнал п) O (журнал п) Удалить O (журнал п) O (журнал п)

В Информатика, а B-дерево самобалансирующийся древовидная структура данных который поддерживает отсортированные данные и позволяет выполнять поиск, последовательный доступ, вставки и удаления в логарифмическое время. B-дерево обобщает двоичное дерево поиска, что позволяет создавать узлы с более чем двумя дочерними элементами.^[2] в отличие от других самобалансирующиеся бинарные деревья поиска, B-дерево хорошо подходит для систем хранения, которые читают и записывают относительно большие блоки данных, такие как диски. Обычно используется в базы данных и файловые системы.

Источник

B-деревья были изобретены Рудольф Байер и Эдвард МакКрайт во время работы в Исследовательские лаборатории Boeing, с целью эффективного управления страницами индекса для больших файлов с произвольным доступом. Основное предположение заключалось в том, что индексы будут настолько объемными, что в основную память могут поместиться только небольшие фрагменты дерева. Статья Байера и МакКрайта, Организация и обслуживание крупных заказных индексов,^[1] был впервые распространен в июле 1970 г. и позже опубликован в Acta Informatica.^[3]

Байер и МакКрайт так и не объяснили, что такое B означает: Боинг, сбалансированный, широкий, кустистый, и Байер были предложены.^[4][5][6] МакКрайт сказал, что «чем больше вы думаете о том, что означает B в B-деревьях, тем лучше вы понимаете B-деревья».^[5]

Определение

Согласно определению Кнута, B-дерево порядка м дерево, удовлетворяющее следующим свойствам:

1. Каждый узел имеет не более м дети.
2. Каждый нелистовой узел (кроме корневого) имеет не менее ⌈м/ 2⌉ дочерние узлы.
3. У корня есть по крайней мере два потомка, если это не листовой узел.
4. Нелистовой узел с k дети содержат k - 1 ключ.
5. Все листья находятся на одном уровне и не несут никакой информации.

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

Внутренние узлы

Внутренние узлы - это все узлы, кроме конечных узлов и корневого узла. Обычно они представлены в виде упорядоченного набора элементов и дочерних указателей. Каждый внутренний узел содержит максимум из U дети и минимум из L дети. Таким образом, количество элементов всегда на 1 меньше, чем количество дочерних указателей (количество элементов находится между L−1 и U−1). U должно быть либо 2L или 2L−1; поэтому каждый внутренний узел заполнен как минимум наполовину. Отношения между U и L подразумевает, что два наполовину заполненных узла могут быть объединены в легальный узел, а один полный узел может быть разделен на два законных узла (если есть место для проталкивания одного элемента вверх в родительский). Эти свойства позволяют удалять и вставлять новые значения в B-дерево, а также настраивать дерево, чтобы сохранить свойства B-дерева.

Корневой узел

Количество дочерних узлов корневого узла имеет тот же верхний предел, что и внутренние узлы, но не имеет нижнего предела. Например, если меньше, чем L−1 элемента во всем дереве, корень будет единственным узлом в дереве без дочерних элементов.

Листовые узлы

По терминологии Кнута, листовые узлы не несут никакой информации. Внутренние узлы, расположенные на один уровень выше листьев, другие авторы назвали бы «листьями»: эти узлы хранят только ключи (не более м-1, и не менее м/ 2-1, если они не являются корнем) и указатели на узлы, не несущие информации.

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

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

Различия в терминологии

Литература по B-деревьям неоднородна по своей терминологии.^[7]

Байер и МакКрайт (1972),^[3] Комер (1979),^[2] и другие определяют порядок B-дерева как минимальное количество ключей в некорневом узле.^[8] указывает, что терминология неоднозначна, поскольку неясно максимальное количество ключей. B-дерево порядка 3 может содержать максимум 6 ключей или максимум 7 ключей. Knuth (1998) избегает проблемы, определяя порядок быть максимальным количеством дочерних элементов (которое на единицу больше максимального количества ключей).^[9]

Период, термин лист также противоречиво. Байер и МакКрайт (1972)^[3] Считал конечный уровень самым низким уровнем ключей, но Кнут считал конечный уровень на один уровень ниже самых низких ключей.^[10] Есть много возможных вариантов реализации. В некоторых конструкциях листья могут содержать всю запись данных; в других конструкциях листья могут содержать только указатели на запись данных. Этот выбор не является фундаментальным для идеи B-дерева.^[11]

Для простоты большинство авторов предполагает, что в узел помещается фиксированное количество ключей. Основное предположение состоит в том, что размер ключа фиксирован, а размер узла фиксирован. На практике могут использоваться ключи переменной длины.^[12]

Неформальное описание

B-дерево (Байер и МакКрайт, 1972 г. ) порядка 5 (Кнут 1998 ).

В B-деревьях внутренние (не листовой ) узлы могут иметь переменное количество дочерних узлов в пределах некоторого заранее определенного диапазона. Когда данные вставляются или удаляются из узла, количество его дочерних узлов изменяется. Чтобы сохранить заданный диапазон, внутренние узлы могут быть объединены или разделены. Поскольку разрешен диапазон дочерних узлов, B-деревья не нуждаются в повторной балансировке так часто, как другие самобалансирующиеся деревья поиска, но могут тратить некоторое пространство, поскольку узлы не полностью заполнены. Нижняя и верхняя границы количества дочерних узлов обычно фиксированы для конкретной реализации. Например, в 2–3 дерево (иногда называемый 2–3 B-дерево), каждый внутренний узел может иметь только 2 или 3 дочерних узла.

Каждый внутренний узел B-дерева содержит ряд ключи. Ключи действуют как значения разделения, которые разделяют его поддеревья. Например, если внутренний узел имеет 3 дочерних узла (или поддерева), тогда он должен иметь 2 ключа: ${\displaystyle a_{1}}$ и ${\displaystyle a_{2}}$. Все значения в крайнем левом поддереве будут меньше ${\displaystyle a_{1}}$, все значения в среднем поддереве будут между ${\displaystyle a_{1}}$ и ${\displaystyle a_{2}}$, и все значения в крайнем правом поддереве будут больше, чем ${\displaystyle a_{2}}$.

Обычно количество клавиш варьируется от ${\displaystyle d}$ и ${\displaystyle 2d}$, куда ${\displaystyle d}$ - минимальное количество ключей, а ${\displaystyle d+1}$ это минимум степень или же фактор ветвления дерева. На практике ключи занимают больше всего места в узле. Коэффициент 2 гарантирует, что узлы можно разделить или объединить. Если внутренний узел имеет ${\displaystyle 2d}$ ключей, то добавление ключа к этому узлу может быть выполнено путем разделения гипотетического ${\displaystyle 2d+1}$ ключевой узел на два ${\displaystyle d}$ ключевые узлы и перемещение ключа, который был бы посередине, на родительский узел. Каждый разделенный узел имеет необходимое минимальное количество ключей. Аналогичным образом, если внутренний узел и его сосед имеют ${\displaystyle d}$ keys, то ключ может быть удален из внутреннего узла путем объединения его со своим соседом. Удаление ключа сделает внутренний узел ${\displaystyle d-1}$ ключи; присоединение к соседу добавило бы ${\displaystyle d}$ ключи плюс еще один сбитый от родителя соседа. В результате получается полностью полный узел ${\displaystyle 2d}$ ключи.

Количество ветвей (или дочерних узлов) от узла будет на единицу больше, чем количество ключей, хранящихся в узле. В 2-3 B-дереве внутренние узлы будут хранить либо один ключ (с двумя дочерними узлами), либо два ключа (с тремя дочерними узлами). B-дерево иногда описывается параметрами ${\displaystyle (d+1)}$—${\displaystyle (2d+1)}$ или просто с наивысшим порядком ветвления, ${\displaystyle (2d+1)}$.

B-дерево сохраняется сбалансированным после вставки путем разделения потенциально переполненного узла из ${\displaystyle 2d+1}$ ключи, в два ${\displaystyle d}$-key братьев и сестер и вставить ключ среднего значения в родительский. Глубина увеличивается только тогда, когда корень раскалывается, сохраняя равновесие. Точно так же B-дерево сохраняется сбалансированным после удаления путем слияния или перераспределения ключей между братьями и сестрами для поддержания ${\displaystyle d}$-ключевой минимум для некорневых узлов. Слияние уменьшает количество ключей в родительском элементе, что может вынудить его объединить или перераспределить ключи со своими братьями и сестрами и так далее. Единственное изменение глубины происходит, когда у корня есть два дочерних элемента: ${\displaystyle d}$ и (временно) ${\displaystyle d-1}$ ключи, и в этом случае два брата и сестры и родитель объединяются, уменьшая глубину на единицу.

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

B-деревья имеют существенные преимущества по сравнению с альтернативными реализациями, когда время доступа к данным узла значительно превышает время, затрачиваемое на обработку этих данных, потому что тогда стоимость доступа к узлу может быть амортизирована за счет нескольких операций внутри узла. Обычно это происходит, когда данные узла находятся в вторичное хранилище Такие как Дисковый привод. Увеличивая количество ключей в каждом внутренний узел, высота дерева уменьшается и количество дорогостоящих обращений к узлам уменьшается. К тому же ребалансировка дерева происходит реже. Максимальное количество дочерних узлов зависит от информации, которая должна храниться для каждого дочернего узла, и размера полного дисковый блок или аналогичного размера во вторичном хранилище. Хотя 2-3 B-дерева легче объяснить, на практике B-деревья, использующие вторичное хранилище, требуют большого количества дочерних узлов для повышения производительности.

Варианты

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

• в B + дерево, копии ключей хранятся во внутренних узлах; ключи и записи хранятся в листах; кроме того, листовой узел может включать указатель на следующий листовой узел для ускорения последовательного доступа.^[2]
• B^* tree уравновешивает большее количество соседних внутренних узлов, чтобы внутренние узлы были более плотно упакованы.^[2] Этот вариант гарантирует, что некорневые узлы заполнены не менее чем на 2/3 вместо 1/2.^[13] Поскольку самая дорогостоящая часть операции вставки узла в B-дерево - это разбиение узла, B^*-деревья создаются, чтобы отложить операцию разбиения на столько, сколько они могут.^[14] Чтобы поддерживать это, вместо того, чтобы немедленно разделять узел, когда он заполняется, его ключи используются совместно с узлом рядом с ним. Эта операция сброса обходится дешевле, чем разделение, потому что она требует только смещения ключей между существующими узлами, а не выделения памяти для нового.^[14] Для вставки сначала проверяется, есть ли в узле немного свободного места, и если да, новый ключ просто вставляется в узел. Однако, если узел заполнен (на нем м − 1 ключи, где м - это порядок дерева как максимальное количество указателей на поддеревья из одного узла), необходимо проверить, существует ли правый брат и есть ли у него некоторое свободное пространство. Если у правого брата j < м − 1 ключи, то ключи перераспределяются между двумя родственными узлами как можно более равномерно. Для этого м - 1 ключи от текущего узла, вставленный новый ключ, один ключ от родительского узла и j ключи из родственного узла рассматриваются как упорядоченный массив м + j + 1 ключи. Массив делится пополам, так что ⌊(м + j + 1)/2⌋ младшие ключи остаются в текущем узле, следующий (средний) ключ вставляется в родительский, а остальные переходят к правому брату.^[14] (Вновь вставленный ключ может оказаться в любом из трех мест.) Ситуация, когда правый брат заполнен, а левый - нет, аналогична.^[14] Когда оба одноуровневых узла заполнены, тогда два узла (текущий узел и одноуровневый узел) разделяются на три, и еще один ключ перемещается вверх по дереву к родительскому узлу.^[14] Если родительский элемент заполнен, то операция разлива / разделения распространяется на корневой узел.^[14] Однако удаление узлов несколько сложнее, чем вставка.
• B-деревья можно превратить в деревья статистики порядка для быстрого поиска N-й записи в ключевом порядке или подсчета количества записей между любыми двумя записями и различных других связанных операций.^[15]

Использование B-дерева в базах данных

Время искать отсортированный файл

Обычно алгоритмы сортировки и поиска характеризуются количеством операций сравнения, которые должны выполняться с использованием обозначение порядка. А бинарный поиск отсортированной таблицы с N записи, например, можно сделать примерно за ⌈ бревно₂ N ⌉ сравнения. Если бы в таблице было 1000000 записей, то можно было бы найти конкретную запись с максимально 20 сравнениями: ⌈ бревно₂ (1,000,000) ⌉ = 20.

Исторически большие базы данных хранились на дисках. Время чтения записи на диске намного превышает время, необходимое для сравнения ключей, когда запись становится доступной. Время для чтения записи с диска требует время поиска и задержка вращения. Время поиска может составлять от 0 до 20 или более миллисекунд, а задержка вращения составляет в среднем около половины периода вращения. Для привода 7200 об / мин период вращения составляет 8,33 миллисекунды. Для такого привода, как Seagate ST3500320NS, время поиска от трека к треку составляет 0,8 миллисекунды, а среднее время поиска чтения составляет 8,5 миллисекунды.^[16] Для простоты предположим, что чтение с диска занимает около 10 миллисекунд.

Таким образом, наивно, что время, чтобы найти одну запись из миллиона, потребовало бы 20 чтений с диска умножить на 10 миллисекунд на чтение с диска, что составляет 0,2 секунды.

Время будет не так уж и плохо, потому что отдельные записи сгруппированы на диске блокировать. Блок диска может составлять 16 килобайт. Если каждая запись имеет размер 160 байтов, то в каждом блоке может храниться 100 записей. Вышеуказанное время чтения с диска было фактически для всего блока. Как только головка диска находится в нужном положении, один или несколько блоков диска могут быть прочитаны с небольшой задержкой. При 100 записях на блок последние 6 или около того сравнений не требуют чтения с диска - все сравнения выполняются в пределах последнего прочитанного блока диска.

Чтобы ускорить поиск, нужно ускорить первые 13–14 сравнений (каждое из которых требует доступа к диску).

Индекс ускоряет поиск

Значительного улучшения можно добиться с помощью индекс. В приведенном выше примере начальное чтение с диска сузило диапазон поиска в два раза. Это можно существенно улучшить, создав вспомогательный индекс, содержащий первую запись в каждом блоке диска (иногда называемый разреженный индекс ). Этот вспомогательный индекс будет составлять 1% от размера исходной базы данных, но его можно искать быстрее. Поиск записи во вспомогательном индексе укажет нам, какой блок искать в основной базе данных; после поиска по вспомогательному индексу нам пришлось бы искать только в этом одном блоке основной базы данных - за счет еще одного чтения с диска. Индекс будет содержать 10 000 записей, поэтому потребуется не более 14 сравнений. Как и в основной базе данных, последние шесть или около того сравнений во вспомогательном индексе будут на одном и том же блоке диска. Индекс можно было найти примерно за восемь чтений с диска, а к желаемой записи можно было получить доступ за 9 чтений с диска.

Трюк с созданием вспомогательного индекса можно повторить, чтобы создать вспомогательный индекс к вспомогательному индексу. Это сделало бы индекс aux-aux, который потребовал бы всего 100 записей и поместился бы в один дисковый блок.

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

Вспомогательные индексы превратили задачу поиска из двоичного поиска, требующего примерно бревно₂ N диск читает до одного, требующего только бревно_б N диск читает где б - коэффициент блокировки (количество записей в блоке: б = 100 записей на блок в нашем примере; бревно₁₀₀ 1,000,000 = 3 читает).

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

Вставки и удаления

Если база данных не изменяется, то компиляция индекса проста, и индекс не нужно изменять. Если есть изменения, то управление базой данных и ее индексом усложняется.

Удалить записи из базы данных относительно просто. Индекс может оставаться прежним, а запись можно просто пометить как удаленную. База данных остается в отсортированном порядке. При большом количестве удалений поиск и хранение становятся менее эффективными.

Вставки в отсортированный последовательный файл могут быть очень медленными, поскольку необходимо освободить место для вставляемой записи. Чтобы вставить запись перед первой, необходимо сдвинуть все записи на одну вниз. Такая операция слишком дорога, чтобы быть практичной. Одно из решений - оставить несколько пробелов. Вместо того, чтобы плотно упаковывать все записи в блок, в блоке может быть некоторое свободное пространство для последующих вставок. Эти пробелы будут отмечены, как если бы они были «удаленными» записями.

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

Преимущества использования B-дерева для баз данных

B-дерево использует все идеи, описанные выше. В частности, B-дерево:

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

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

Высота в лучшем и худшем случае

Позволять час ≥ –1 быть высотой классического B-дерева (см. Дерево (структура данных) § Терминология для определения высоты дерева). Позволять п ≥ 0 быть количеством записей в дереве. Позволять м - максимальное количество дочерних узлов, которое может иметь узел. Каждый узел может иметь не более м−1 ключи.

Можно показать (например, по индукции), что B-дерево высоты час со всеми полностью заполненными узлами имеет п = м^час+1–1 записи. Следовательно, оптимальная высота (т.е. минимальная высота) B-дерева равна:

${\displaystyle h_{\mathrm {min} }=\lceil \log _{m}(n+1)\rceil -1}$

Позволять ${\displaystyle d}$ быть минимальным количеством потомков, которое может иметь внутренний (не корневой) узел. Для обычного B-дерева ${\displaystyle d=\left\lceil m/2\right\rceil .}$

Комер (1979) и Кормен и др. (2001) дают наихудшую высоту (максимальную высоту) B-дерева как^[17]

${\displaystyle h_{\mathrm {max} }=\left\lfloor \log _{d}{\frac {n+1}{2}}\right\rfloor .}$

Алгоритмы

Поиск

Поиск похож на поиск в двоичном дереве поиска. Начиная с корня, дерево рекурсивно просматривается сверху вниз. На каждом уровне поиск сокращает свое поле зрения до дочернего указателя (поддерева), диапазон которого включает значение поиска. Диапазон поддерева определяется значениями или ключами, содержащимися в его родительском узле. Эти предельные значения также известны как значения разделения.

Двоичный поиск обычно (но не обязательно) используется внутри узлов для поиска значений разделения и интересующего дочернего дерева.

Вставка

Пример вставки B-дерева на каждой итерации. Узлы этого B-дерева имеют не более трех дочерних элементов (порядок Кнута 3).

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

1. Если узел содержит меньше, чем максимально допустимое количество элементов, то есть место для нового элемента. Вставьте новый элемент в узел, сохраняя порядок элементов узла.
2. В противном случае узел заполнен, равномерно разделите его на два узла так:
   1. Одна медиана выбирается из элементов листа и нового элемента.
   2. Значения меньше медианы помещаются в новый левый узел, а значения больше медианы помещаются в новый правый узел, причем медиана действует как значение разделения.
   3. Значение разделения вставляется в родительский узел, что может привести к его разделению и так далее. Если узел не имеет родителя (т.е. узел был корнем), создайте новый корень над этим узлом (увеличивая высоту дерева).

Если разделение идет полностью до корня, он создает новый корень с одним значением разделителя и двумя дочерними элементами, поэтому нижняя граница размера внутренних узлов не применяется к корню. Максимальное количество элементов на узел составляет U−1. Когда узел разделяется, один элемент перемещается к родительскому, но добавляется один элемент. Итак, должно быть возможно разделить максимальное число U−1 элементов на два легальных узла. Если это число нечетное, то U=2L и один из новых узлов содержит (U−2)/2 = L−1 элементов и, следовательно, является допустимым узлом, а другой содержит еще один элемент, и, следовательно, он также допустим. Если U−1 четно, то U=2L−1, поэтому имеется 2L−2 элемента в узле. Половина этого числа составляет L−1 - минимальное количество элементов, разрешенное на узел.

Альтернативный алгоритм поддерживает одиночный проход вниз по дереву от корня к узлу, где будет происходить вставка, с упреждающим разделением любых полных узлов, встречающихся на пути. Это предотвращает необходимость вызова родительских узлов в память, что может быть дорогостоящим, если узлы находятся во вторичной памяти. Однако, чтобы использовать этот алгоритм, мы должны иметь возможность отправить один элемент родительскому элементу и разделить оставшиеся U−2 элемента на два допустимых узла без добавления нового элемента. Это требует U = 2L скорее, чем U = 2L−1, что объясняет, почему некоторые^{[который? ]} учебники предъявляют это требование при определении B-деревьев.

Удаление

Есть две популярные стратегии удаления из B-дерева.

1. Найдите и удалите элемент, затем реструктурируйте дерево, чтобы сохранить его инварианты, ИЛИ ЖЕ
2. Сделайте один проход вниз по дереву, но перед входом в узел (посещением) реструктурируйте дерево так, чтобы, как только удаляется ключ, его можно было удалить, не вызывая необходимости в дальнейшей реструктуризации.

В приведенном ниже алгоритме используется первая стратегия.

При удалении элемента следует учитывать два особых случая:

1. Элемент во внутреннем узле является разделителем для его дочерних узлов.
2. Удаление элемента может привести к тому, что его узел окажется ниже минимального количества элементов и дочерних элементов.

Порядок действий в этих случаях приводится ниже.

Удаление из листового узла

1. Найдите значение, которое нужно удалить.
2. Если значение находится в листовом узле, просто удалите его из узла.
3. Если происходит недостаточное заполнение, перебалансируйте дерево, как описано в разделе «Ребалансировка после удаления» ниже.

Удаление с внутреннего узла

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

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

Ребалансировка после удаления

Восстановление баланса начинается с листа и продолжается к корню, пока дерево не будет сбалансировано. Если удаление элемента из узла привело к тому, что он стал меньше минимального размера, тогда некоторые элементы должны быть перераспределены, чтобы свести все узлы к минимуму. Обычно перераспределение включает перемещение элемента из одноуровневого узла, у которого больше минимального количества узлов. Эта операция перераспределения называется вращение. Если ни один из братьев и сестер не может сэкономить элемент, то дефектный узел должен быть слился с братом или сестрой. Слияние приводит к тому, что родительский элемент теряет разделительный элемент, поэтому родительский элемент может стать несовершенным и потребовать повторной балансировки. Слияние и ребалансировка могут продолжаться вплоть до корня. Поскольку минимальное количество элементов не применяется к корню, сделать корень единственным дефектным узлом не проблема. Алгоритм ребалансировки дерева следующий:^{[нужна цитата ]}

• Если правый брат неполноценного узла существует и имеет больше, чем минимальное количество элементов, то поверните влево.
  1. Скопируйте разделитель от родителя до конца недостающего узла (разделитель сдвигается вниз; дефектный узел теперь имеет минимальное количество элементов)
  2. Замените разделитель в родительском элементе первым элементом правого брата (правый брат теряет один узел, но все еще имеет по крайней мере минимальное количество элементов)
  3. Дерево теперь сбалансировано
• В противном случае, если левый брат неполноценного узла существует и имеет больше, чем минимальное количество элементов, то поверните вправо.
  1. Скопируйте разделитель из родительского узла в начало дефектного узла (разделитель перемещается вниз; дефектный узел теперь имеет минимальное количество элементов)
  2. Замените разделитель в родительском элементе последним элементом левого брата (левый брат теряет один узел, но все еще имеет по крайней мере минимальное количество элементов)
  3. Дерево теперь сбалансировано
• В противном случае, если у обоих непосредственных братьев и сестер есть только минимальное количество элементов, затем слияние с одноуровневым братом, помещая их разделитель, снятый с их родителя.
  1. Скопируйте разделитель в конец левого узла (левый узел может быть дефектным узлом или может быть братом с минимальным количеством элементов)
  2. Переместите все элементы из правого узла в левый узел (левый узел теперь имеет максимальное количество элементов, а правый узел - пустой)
  3. Удалите разделитель из родителя вместе с его пустым правым дочерним элементом (родитель теряет элемент)
     • Если родительский элемент является корнем и теперь не имеет элементов, то освободите его и сделайте объединенный узел новым корнем (дерево становится более мелким).
     • В противном случае, если родительский элемент имеет меньше, чем требуется, количество элементов, тогда повторно сбалансируйте родительский элемент.

Примечание: Операции перебалансировки различны для деревьев B + (например, вращение отличается, потому что у родительского элемента есть копия ключа) и B^*-дерево (например, три брата и сестры объединяются в двух братьев и сестер).

Последовательный доступ

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

Начальное строительство

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

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

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

В файловых системах

Помимо использования в базах данных, B-дерево (или § Варианты ) также используется в файловых системах, чтобы обеспечить быстрый произвольный доступ к произвольному блоку в конкретном файле. Основная проблема - поворот файлового блока ${\displaystyle i}$ адрес в блок диска (или, возможно, в сектор головки блока цилиндров ) адрес.

Некоторые операционные системы требуют от пользователя выделения максимального размера файла при его создании. Затем файл можно выделить как непрерывные блоки диска. В этом случае, чтобы преобразовать адрес блока файла ${\displaystyle i}$ в адрес блока диска операционная система просто добавляет адрес блока файла ${\displaystyle i}$ по адресу первого блока диска, составляющего файл. Схема проста, но размер файла не может превышать созданный.

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

MS-DOS, например, использовали простой Таблица размещения файлов (ТОЛСТЫЙ). В FAT есть запись для каждого блока диска,^{[примечание 1]} и эта запись определяет, используется ли его блок файлом, и если да, то какой блок (если есть) является следующим дисковым блоком того же файла. Таким образом, размещение каждого файла представлено как связанный список в таблице. Чтобы найти дисковый адрес файлового блока ${\displaystyle i}$, операционная система (или дисковая утилита) должна последовательно следовать за списком связанных файлов в FAT. Хуже того, чтобы найти свободный дисковый блок, он должен последовательно сканировать FAT. Для MS-DOS это не было огромным штрафом, потому что диски и файлы были небольшими, а в FAT было мало записей и относительно короткие цепочки файлов. в FAT12 файловая система (использовалась на гибких дисках и ранних жестких дисках), их было не более 4080 ^{[заметка 2]} записей, а FAT обычно находится в памяти. По мере того, как диски становились больше, архитектура FAT начала сталкиваться с недостатками. На большом диске, использующем FAT, может потребоваться выполнить чтение с диска, чтобы узнать, где на диске находится блок файла, который нужно прочитать или записать.

ТОП-20 (и, возможно, Техас ) использовали дерево уровня от 0 до 2, которое имеет сходство с B-деревом^{[нужна цитата ]}. Дисковый блок состоял из 512 36-битных слов. Если файл умещается в 512 (2⁹) word block, то каталог файлов будет указывать на этот блок физического диска. Если файл умещается в 2¹⁸ слова, тогда каталог будет указывать на вспомогательный индекс; 512 слов этого индекса будут либо NULL (блок не выделяется), либо указывать на физический адрес блока. Если файл умещается в 2²⁷ слова, тогда каталог будет указывать на блок, содержащий индекс aux-aux; каждая запись будет либо иметь значение NULL, либо указывать на вспомогательный индекс. Следовательно, блок физического диска на 2²⁷ Word файл мог быть расположен на двух дисках чтения и чтения на третьем.

Файловая система Apple HFS +, Microsoft NTFS,^[19] AIX (jfs2) и некоторые Linux файловые системы, такие как btrfs и Ext4, используйте B-деревья.

B^*-деревья используются в HFS и Reiser4 файловые системы.

DragonFly BSD с МОЛОТОК файловая система использует модифицированное B + -дерево.^[20]

Спектакль

B-дерево растет медленнее с увеличением объема данных, чем линейность связанного списка. По сравнению с пропускаемым списком обе структуры имеют одинаковую производительность, но B-дерево лучше масштабируется для роста. п. А Т-образное дерево, за база данных основной памяти систем, аналогичен, но более компактен.

Вариации

Параллельный доступ

Леман и Яо^[21] показали, что всех блокировок чтения можно избежать (и, таким образом, значительно улучшить одновременный доступ), связав блоки дерева на каждом уровне вместе с указателем «следующий». Это приводит к древовидной структуре, в которой операции вставки и поиска спускаются от корня к листу. Блокировки записи требуются только при изменении блока дерева. Это максимизирует параллелизм доступа для нескольких пользователей, что является важным соображением для баз данных и / или других основанных на B-дереве. ISAM методы хранения. Цена, связанная с этим улучшением, заключается в том, что пустые страницы не могут быть удалены из btree во время обычных операций. (Однако см. ^[22] для различных стратегий для реализации слияния узлов и исходного кода в.^[23])

Патент США 5283894, выданный в 1994 г., по-видимому, показывает способ использования «метода метадоступа». ^[24] чтобы разрешить одновременный доступ к дереву B + и его изменение без блокировок. Этот метод обращается к дереву «вверх» как для поиска, так и для обновлений с помощью дополнительных индексов в памяти, которые указывают на блоки на каждом уровне в кеш-памяти блоков. Никакой реорганизации для удалений не требуется, и в каждом блоке нет указателей «следующий», как в Lehman и Yao.

Параллельные алгоритмы

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

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

• B + дерево
• R-дерево
• Красно-черное дерево
• 2–3 дерева
• 2–3–4 дерева

Примечания

1. Для FAT то, что называется «дисковым блоком», в документации FAT называется «кластером», который представляет собой группу фиксированного размера из одного или нескольких непрерывных физических дисков. сектора. Для целей данного обсуждения кластер не имеет существенных отличий от физического сектора.
2. Два из них были зарезервированы для специальных целей, поэтому только 4078 могли фактически представлять дисковые блоки (кластеры).

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

1. Bayer, R .; МакКрайт, Э. (июль 1970 г.). «Организация и обслуживание крупных заказных индексов» (PDF). Материалы семинара 1970 г. ACM SIGFIDET (ныне SIGMOD) по описанию, доступу и управлению данными - SIGFIDET '70. Научно-исследовательские библиотеки Boeing. п. 107. Дои:10.1145/1734663.1734671.
2. Comer 1979.
3. Байер и МакКрайт, 1972 г..
4. Comer 1979, п. 123 сноска 1.
5. Вайнер, Питер Г. (30 августа 2013 г.). "4- Эдвард М. МакКрайт" - через Vimeo.
6. «Стэнфордский центр профессионального развития». scpd.stanford.edu. Архивировано из оригинал на 2014-06-04. Получено 2011-01-16.
7. Фолк и Зеллик 1992, п. 362.
8. Фолк и Зеллик 1992.
9. Кнут 1998, п. 483.
10. Фолк и Зеллик 1992, п. 363.
11. Байер и МакКрайт (1972) избежал проблемы, заявив, что элемент индекса представляет собой (физически смежную) пару (Икс, а) куда Икс это ключ, и а это некоторая сопутствующая информация. Связанная информация может быть указателем на запись или записи в произвольном доступе, но на самом деле это не имеет значения. Байер и МакКрайт (1972) заявляет: «Для этой статьи дополнительная информация не представляет интереса».
12. Фолк и Зеллик 1992, п. 379.
13. Кнут 1998, п. 488.
14. Томашевич, Майло (2008). Алгоритмы и структуры данных. Белград, Сербия: Akademska misao. С. 274–275. ISBN  978-86-7466-328-8.
15. Счетные B-деревья, дата обращения 25.01.2010
16. Seagate Technology LLC, Руководство по продукту: Barracuda ES.2 Serial ATA, Rev. F., публикация 100468393, 2008 г. [1], стр. 6
17. Comer 1979, п. 127; Cormen et al. 2001 г., стр. 439–440
18. "Кэшировать забытые B-деревья". Государственный университет Нью-Йорка (SUNY) в Стоуни-Брук. Получено 2011-01-17.
19. Марк Руссинович. "Внутри Windows 2000 NTFS, часть 1". Сеть разработчиков Microsoft. В архиве из оригинала 13 апреля 2008 г.. Получено 2008-04-18.
20. Мэттью Диллон (21.06.2008). "Файловая система HAMMER" (PDF).
21. Lehman, Philip L .; Яо, с. Бинг (1981). «Эффективная блокировка для параллельных операций над B-деревьями». Транзакции ACM в системах баз данных. 6 (4): 650–670. Дои:10.1145/319628.319663.
22. http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA232287&Location=U2&doc=GetTRDoc.pdf
23. «Загрузки - btree с высоким уровнем параллелизма - Код B-дерева с высоким уровнем параллелизма на языке C - Хостинг проекта GitHub». Получено 2014-01-27.
24. «Метод одновременного метадоступа к индексу B-дерева без блокировки для кэшированных узлов».

Общий

• Байер, Р.; МакКрайт, Э. (1972), «Организация и обслуживание крупных заказных индексов» (PDF), Acta Informatica, 1 (3): 173–189, Дои:10.1007 / bf00288683
• Комер, Дуглас (Июнь 1979 г.), "Вездесущее B-дерево", Вычислительные опросы, 11 (2): 123–137, Дои:10.1145/356770.356776, ISSN  0360-0300.
• Кормен, Томас; Лейзерсон, Чарльз; Ривест, Рональд; Штейн, Клиффорд (2001), Введение в алгоритмы (Второе изд.), MIT Press and McGraw-Hill, pp. 434–454, ISBN  0-262-03293-7. Глава 18: B-деревья.
• Народ, Майкл Дж .; Зеллик, Билл (1992), Файловые структуры (2-е изд.), Эддисон-Уэсли, ISBN  0-201-55713-4
• Кнут, Дональд (1998), Сортировка и поиск, Искусство программирования, Том 3 (Второе изд.), Эддисон-Уэсли, ISBN  0-201-89685-0. Раздел 6.2.4: Многонаправленные деревья, стр. 481–491. Кроме того, стр. 476–477 раздела 6.2.3 (Сбалансированные деревья) обсуждают 2-3 дерева.

Оригинальные статьи

• Байер, Рудольф; МакКрайт, Э. (Июль 1970 г.), Организация и обслуживание крупных заказных индексов, Отчет по математическим и информационным наукам № 20, Научно-исследовательские лаборатории Boeing.
• Байер, Рудольф (1971), Двоичные B-деревья для виртуальной памяти, Материалы семинара ACM-SIGFIDET 1971 года по описанию данных, доступу и контролю, Сан-Диего, Калифорния.

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

• Лекция по B-дереву Дэвид Скот Тейлор, SJSU
• Визуализация B-Tree (нажмите "init")
• Анимированная визуализация B-Tree
• B-дерево и UB-дерево в Scholarpedia Куратор: доктор Рудольф Байер
• B-деревья: сбалансированные древовидные структуры данных
• Словарь алгоритмов и структур данных NIST: B-дерево
• Учебник по B-дереву
• Реализация InfinityDB BTree
• Cache Oblivious B (+) - деревья
• Словарь алгоритмов и словарных статей для B * -дерева
• Структуры открытых данных - Раздел 14.2 - B-деревья, Пэт Морин
• Счетные B-деревья
• B-Tree .Net, современная виртуализированная реализация RAM и Disk

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

• Шетти, Сумья Б. (2010). Настраиваемая пользователем реализация B-деревьев (Тезис). Государственный университет Айовы.
• Калдырым, Семих (28 апреля 2015 г.). «Файловая организация, ISAM, дерево B + и массовая загрузка» (PDF). Анкара, Турция: Билькентский университет. С. 4–6.
• «ECS 165B: Внедрение системы баз данных: лекция 6» (PDF). Калифорнийский университет в Дэвисе. 9 апреля 2010. с. 23.
• «ОБЪЕМНАЯ ВСТАВКА (Transact-SQL) в SQL Server 2017». Документы Microsoft. 6 сентября 2018.