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

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

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

Источник

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Варианты

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритмы

Поиск

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

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

Вставка

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

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

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

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

Удаление

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Представление

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

Вариации

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

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

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

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

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

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

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

Примечания

использованная литература

Общий

• Байер, Р .; McCreight, E. (1972), "Организация и ведение крупных упорядоченных индексов" (PDF) , Acta Informatica , 1 (3): 173-189, DOI : 10.1007 / bf00288683 , S2CID  29859053
• Comer, Douglas (июнь 1979), "Вездесущий B-Tree", Computing Surveys , 11 (2): 123-137, DOI : 10,1145 / 356770,356776 , ISSN  0360-0300 , S2CID  101673.
• Кормен, Томас ; Лейзерсон, Чарльз ; Ривест, Рональд ; Стейн, Клиффорд (2001), Введение в алгоритмы (второе издание), MIT Press и McGraw-Hill, стр. 434–454, ISBN 0-262-03293-7. Глава 18: B-деревья.
• Народ, Майкл Дж .; Зеллик, Билл (1992), Файловые структуры (2-е изд.), Addison-Wesley, ISBN 0-201-55713-4
• Кнут, Дональд (1998), Сортировка и поиск , Искусство компьютерного программирования , Том 3 (второе издание), Addison-Wesley, ISBN 0-201-89685-0 |volume=имеет дополнительный текст ( справка ). Раздел 6.2.4: Многонаправленные деревья, стр. 481–491. Кроме того, на стр. 476–477 раздела 6.2.3 (Сбалансированные деревья) обсуждаются 2–3 дерева.

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

• Байер, Рудольф ; МакКрайт, Э. (июль 1970 г.), Организация и ведение крупных упорядоченных индексов , отчет по математическим и информационным наукам № 20, Научно-исследовательские лаборатории Боинга.
• Байер, Рудольф (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-деревьев (Thesis). Государственный университет Айовы.
• Калдырым, Семих (28 апреля 2015 г.). «Файловая организация, ISAM, дерево B + и массовая загрузка» (PDF) . Анкара, Турция: Университет Билкент . С. 4–6.
• «ECS 165B: Внедрение системы баз данных: лекция 6» (PDF) . Калифорнийский университет в Дэвисе . 9 апреля 2010. с. 23.
• «ОБЪЕМНАЯ ВСТАВКА (Transact-SQL) в SQL Server 2017» . Документы Microsoft. 6 сентября 2018.