B-дерево

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

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

Содержание

  • 1 Источник
  • 2 Определение
    • 2.1 Различия в терминологии
  • 3 Неформальное описание
    • 3.1 Варианты
  • 4 Использование B-дерева в базах данных
    • 4.1 Время поиска в отсортированном файле
    • 4.2 Индекс ускоряет поиск
    • 4.3 Вставки и удаление
    • 4.4 Преимущества использования B-дерева для баз данных
  • 5 Высота в лучшем и худшем случае
  • 6 Алгоритмы
    • 6.1 Поиск
    • 6.2 Вставка
    • 6.3 Удаление
      • 6.3.1 Удаление из листового узла
      • 6.3.2 Удаление внутреннего узла
      • 6.3.3 Повторная балансировка после удаления
    • 6.4 Последовательный доступ
    • 6.5 Начальная конструкция
  • 7 В файловых системах
  • 8 Производительность
  • 9 Варианты
    • 9.1 Параллелизм доступа
    • 9.2 Параллельные алгоритмы
  • 10 См. Также
  • 11 Примечания
  • 12 Ссылки
    • 12.1 Оригинальные статьи
  • 13 Внешние ссылки

Источник

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

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

Определение

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

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

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

Внутренние узлы
Внутренние узлы - это все узлы, кроме конечных узлов и корневого узла. Обычно они представлены в виде упорядоченного набора элементов и дочерних указателей. Каждый внутренний узел содержит максимум из U детей и минимум из L дочерних узлов. Таким образом, количество элементов всегда на 1 меньше, чем количество дочерних указателей (элементов находится между L-1 и U-1). U должно быть либо 2L, либо 2L - 1; поэтому каждый внутренний узел заполнен как минимум наполовину. Связь между U и L подразумевает, что два наполовину заполненных узлов могут быть объединены, чтобы образовать объединенный узел, один полный узел может быть разделен на два законных узла (если есть место для проталкивания одного элемента вверх в родительском). Эти свойства позволяют удалять и вставлять новые значения в B-дерево, а также настраивать дерево, чтобы сохранить свойства B-дерева.
Корневой узел
Количество дочерних узлов корневого узла такое же верхнее. limit как внутренние узлы, но не имеет нижнего предела. Например, когда во всем дереве меньше, чем L - 1 элементов, корень будет единственным узлом в дереве без дочерних элементов.
Концевые узлы
В терминологии Ключ, конечные узлы не нет никакой информации. Внутренние узлы, которые находятся на одном уровне выше листьев, являются тем, что другие авторы назвали бы «листья»: эти узлы хранятся только ключи (не более m-1 и не менее m / 2-1, если они не являются корневыми) указатели на узлы, не несущие информации.

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

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

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

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

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

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

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

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

B-дерево (Bayer McCreight 1972) порядка 5 (Knuth 1998).

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

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

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

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

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

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

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

Варианты

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

  • В дереве B + копии ключей хранятся во внутренних узлах; ключи и записи хранятся в листах; кроме того, листовой узел может инициировать указатель на следующий листовой узел для ускорения последовательного доступа.
  • B-дерево уравновешивает большее количество соседних внутренних узлов, чтобы внутренние узлы оставались более плотно упакованными. Этот вариант гарантирует, что некорневые узлы заполнены не менее чем на 2/3 вместо 1/2. Самая дорогостоящая часть операции вставки узла в B-дерево - это разбиение узла, блок B-деревья, чтобы отложить операцию разбиения до тех пор, пока они могут. Чтобы поддерживать это, вместо того, чтобы разделять узел, когда он заполняется, используются его ключи совместно с узлом рядом с ним. Эта операция сброса обходится дешевле, чем разделение памяти, потому что для нее требуется только смещение ключей между используемыми узлами, а не выделение памяти для нового. Для вставки сначала проверяется, есть ли в узле немного свободного места, и если да, новый ключ просто вставляется в узел. Однако, если узел заполнен (у него m - 1 ключей, где m - это порядок максимального количества указателей на поддеревья из одного узла), необходимо проверить, существует ли правый брат и есть ли у некоторое свободное пространство.. Если у правого брата j < m − 1 keys, then keys are redistributed between the two sibling nodes as evenly as possible. For this purpose, m - 1 keys from the current node, the new key inserted, one key from the parent node and j keys from the sibling node are seen as an ordered array of m + j + 1 keys. The array becomes split by half, so that ⌊(m + j + 1)/2⌋ lowest keys stay in the current node, the next (middle) key is inserted in the parent and the rest go to the right sibling. (The newly inserted key might end up in any of the three places.) The situation when right sibling is full, and left isn't is analogous. When both the sibling nodes are full, then the two nodes (current node and a sibling) are split into three and one more key is shifted up the tree, to the parent node. If the parent is full, then spill/split operation propagates towards the root node. Deleting nodes is somewhat more complex than inserting however.
  • B-деревья могут быть преобразованы в деревья статистики, чтобы обеспечить быстрый поиск N-й записи в ключевом порядке или подсчет количества записей между любыми двумя главми и различными другими связанными операции.

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

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

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

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

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

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

Для дальнейшего ускорения поиска ускорить первые 13–14 сравнений (каждое из которых требует доступа к диску).

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

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

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

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

Вспомогательные индексы превратили проблему поиска из двоичного поиска, требующего примерно log 2 N операций чтения с диска, до одного, требующего только журнала b N операций чтения с диска, где b - это коэффициент блокировки (количество записей в блоке: b = 100 записей в блоке в нашем примере; журнал 100 1000000 = 3 чтения).

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

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

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

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

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

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

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

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

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

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

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

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

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

hmin = ⌈ log m ⁡ (n + 1) ⌉ - 1 {\ displaystyle h _ {\ mathrm {min}} = \ lceil \ log _ {m} (n + 1) \ rceil -1}{\ displaystyle h _ {\ mathrm {min} } = \ lceil \ log _ {m} (n + 1) \ rceil -1}

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

Comer (1979) и Cormen et al. (2001) дают наихудшую высоту (максимальную высоту) B-дерева как

h m a x = ⌊ log d ⁡ n + 1 2 ⌋. {\ displaystyle h _ {\ mathrm {max}} = \ left \ lfloor \ log _ {d} {\ frac {n + 1} {2}} \ right \ rfloor.}{\ displaystyle h _ {\ mathrm {max}} = \ left \ lfloor \ log _ {d} {\ frac {n + 1} {2}} \ right \ rfloor.}

Алгоритмы

Поиск

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

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

Вставка

Пример вставки B-дерева на каждой итерации. Узлы этого B-дерева имеют не более 3 дочерних элементов (порядок Кнута 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. Найдите и удалите элемент, затем реструктурируйте дерево, чтобы сохранить его инварианты, OR
  2. Сделайте один проход вниз по дереву, но перед входом (посещением) узла реструктурируйте дерево так, чтобы после удаления ключа был при обнаружении, его можно удалить, не вызывая необходимости в дальнейшей реструктуризации.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Начальная конструкция

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

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

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

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

Помимо использования в базах данных, B-дерево (или § Варианты) также используется в файловых системах для обеспечения быстрого произвольного доступа к произвольным block in a particular file. The basic problem is turning the file block i {\displaystyle i}i address into a disk block (or perhaps to a cylinder-head-sector ) address.

Some operating systems require the user to allocate the maximum size of the file when the file is created. The file can then be allocated as contiguous disk blocks. In that case, to convert the file block address i {\displaystyle i}i into a disk block address, the operating system simply adds the file block address i {\displaystyle i}i to the address of the first disk block constituting the file. The scheme is simple, but the file cannot exceed its created size.

Other operating systems allow a file to grow. The resulting disk blocks may not be contiguous, so mapping logical blocks to physical blocks is more involved.

MS-DOS, for example, used a simple File Allocation Table (FAT). The FAT has an entry for each disk block, and that entry identifies whether its block is used by a file and if so, which block (if any) is the next disk block of the same file. So, the allocation of each file is represented as a linked list in the table. In order to find the disk address of file block i {\displaystyle i}i , the operating system (or disk utility) must sequentially follow the file's linked list in the FAT. Worse, to find a free disk block, it необходимо последовательно сканировать FAT. Для MS-DOS это не было огромным штрафом, потому что диски и файлы были небольшими, а в FAT было мало записей и относительно короткие цепочки файлов. В файловой системе FAT12 (использовавшейся на гибких дисках и ранних жестких дисках) было не более 4080 записей, и FAT обычно находилась в памяти. По мере того, как диски становились больше, архитектура FAT начала сталкиваться с недостатками. На большом диске, использующем FAT, может потребоваться выполнить чтение с диска, чтобы узнать, где на диске находится блок файла, который нужно прочитать или записать.

TOPS-20 (и, возможно, TENEX ) использовал дерево уровней от 0 до 2, которое имеет сходство с B-деревом. Дисковый блок состоял из 512 36-битных слов. Если файл помещается в блок из 512 (2) слов, то каталог файла будет указывать на этот блок физического диска. Если файл умещается в 2 слова, тогда каталог будет указывать на вспомогательный индекс; 512 слов этого индекса будут либо NULL (блок не выделяется), либо указывать на физический адрес блока. Если файл умещается в 2 слова, тогда каталог будет указывать на блок, содержащий индекс aux-aux; каждая запись будет либо NULL, либо указывать на вспомогательный индекс. Следовательно, блок физического диска для файла из 2 слов может быть расположен при двух чтениях с диска и чтении на третьем.

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

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

DragonFly BSD в HAMMER файловая система использует модифицированное B + -дерево.

Производительность

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

Варианты

Параллелизм доступа

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

United St. Патент 5283894, выданный в 1994 году, по-видимому, показывает способ использования «метода метадоступа» для одновременного доступа и модификации дерева B + без блокировок. Этот метод обращается к дереву «вверх» как для поиска, так и для обновлений с помощью дополнительных индексов в памяти, которые указывают на блоки на каждом уровне в кеш-памяти блоков. Никакой реорганизации для удалений не требуется, и в каждом блоке нет указателей «следующий», как в Lehman и Yao.

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

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

См.

Примечания

Ссылки

Генерал

Исходные статьи

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

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

На Викискладе есть носители, связанные с B-деревьями.

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

Последняя правка сделана 2021-05-11 14:23:48
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте