B-дерево

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

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

История

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

Bayer и McCreight никогда не объясняли, что означает буква B , если она вообще что-то означает; предлагались Boeing , balance , between , broad , bushy и Bayer . ^{[4] [5] [6]} McCreight сказал, что «чем больше вы думаете о том, что означает буква B в B-деревьях, тем лучше вы понимаете B-деревья». ^[5]

Определение

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

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

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

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

Внутренние узлы (также известные как внутренние узлы ) — это все узлы, за исключением листовых узлов и корневого узла. Обычно они представлены в виде упорядоченного набора элементов и указателей на дочерние элементы. Каждый внутренний узел содержит максимум 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-деревьям неоднородна в терминологии. ^[8]

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

Термин «лист» также непоследователен. Байер и МакКрейт (1972) ^[3] считали, что уровень листьев — это самый низкий уровень ключей, но Кнут считал, что уровень листьев находится на один уровень ниже самых низких ключей. ^[9] Существует много возможных вариантов реализации. В некоторых проектах листья могут содержать всю запись данных; в других проектах листья могут содержать только указатели на запись данных. Эти варианты не являются основополагающими для идеи B-дерева. ^[10]

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

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

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

Структура узла

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

Обратите внимание на следующие определения переменных:

• K : Максимальное количество потенциальных ключей поиска для каждого узла в B-дереве. (это значение постоянно для всего дерева).
• ${\displaystyle pt_{i}}$: Указатель на дочерний узел, который начинает поддерево.
• ${\displaystyle pr_{i}}$: Указатель на запись, в которой хранятся данные.
• ${\displaystyle k_{i}}$: Ключ поиска по индексу узла, начинающемуся с нуля . ${\displaystyle i}$

В B-деревьях для этих узлов поддерживаются следующие свойства:

• Если существует в любом узле дерева B+, то существует в том узле, где . ${\textstyle k_{i}}$ ${\displaystyle k_{i-1}}$ ${\displaystyle i\geq 1}$
• Все листовые узлы имеют одинаковое количество предков (т.е. все они находятся на одинаковой глубине).

Каждый внутренний узел в B-дереве имеет следующий формат:

Каждый конечный узел в B-дереве имеет следующий формат:

Границы узлов приведены в таблице ниже:

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

Для сохранения предопределенного диапазона дочерних узлов внутренние узлы могут быть объединены или разделены.

Обычно количество ключей выбирается в диапазоне от до , где — минимальное количество ключей, а — минимальная степень или фактор ветвления дерева. Фактор 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}$

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

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

Сравнение с другими деревьями

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

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

Варианты

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

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

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

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

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

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

Время поиска одной записи из миллиона в приведенном выше примере составит 20 операций чтения с диска по 10 миллисекунд на операцию чтения с диска, что составляет 0,2 секунды.

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

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

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

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

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

В приведенном выше примере индекс будет содержать 10 000 записей и потребует максимум 14 сравнений для возврата результата. Как и в основной базе данных, последние шесть или около того сравнений во вспомогательном индексе будут находиться в одном и том же блоке диска. Поиск по индексу можно будет выполнить примерно за восемь чтений с диска, а доступ к нужной записи можно будет получить за 9 чтений с диска.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть 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-дерева как ^[20]

${\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 =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, что объясняет, почему некоторые ^{[ which? ]} учебники налагают это требование при определении B-деревьев.

Удаление

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

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

Приведенный ниже алгоритм использует предыдущую стратегию.

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

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

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

Удаление из конечного узла

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вариации

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

Lehman и Yao ^[25] показали, что всех блокировок чтения можно избежать (и, таким образом, значительно улучшить параллельный доступ), связав блоки дерева на каждом уровне вместе указателем «следующий». Это приводит к древовидной структуре, в которой как операции вставки, так и операции поиска спускаются от корня к листу. Блокировки записи требуются только при изменении блока дерева. Это максимизирует параллельный доступ нескольких пользователей, что является важным соображением для баз данных и/или других методов хранения ISAM на основе B-дерева . Стоимость, связанная с этим улучшением, заключается в том, что пустые страницы не могут быть удалены из B-дерева во время обычных операций. (Однако см. ^[26] для различных стратегий реализации слияния узлов и исходный код в ^[27] )

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

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

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

кленовое дерево

Maple tree — это B-дерево, разработанное для использования в ядре Linux с целью снижения числа конфликтов при блокировке в управлении виртуальной памятью. ^{[29] [30] [31]}

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

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

Примечания

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

Ссылки

1. Bayer, R.; McCreight, E. (июль 1970 г.). "Организация и обслуживание больших упорядоченных индексов" (PDF) . Труды семинара ACM SIGFIDET (теперь SIGMOD) 1970 г. по описанию данных, доступу и управлению - SIGFIDET '70 . Научно-исследовательские лаборатории Boeing. стр. 107. doi :10.1145/1734663.1734671. S2CID  26930249.
2. Комер 1979.
3. Bayer & McCreight 1972.
4. Комер 1979, стр. 123 сноска 1.
5. Weiner, Peter G. (30 августа 2013 г.). "4- Edward M McCreight" – через Vimeo.
6. "Стэнфордский центр профессионального развития". scpd.stanford.edu . Архивировано из оригинала 2014-06-04 . Получено 2011-01-16 .
7. Knuth 1998, стр. 483.
8. Фолк и Зеллик 1992, стр. 362.
9. Folk & Zoellick 1992, стр. 363.
10. Bayer & McCreight (1972) обошли эту проблему, заявив, что элемент индекса — это (физически смежная) пара ( x ,  a ), где x — ключ, а a — некоторая связанная информация. Связанная информация может быть указателем на запись или записи в случайном доступе, но что это было на самом деле не имеет значения. Bayer & McCreight (1972) утверждают: «Для этой статьи связанная информация не представляет дальнейшего интереса».
11. Фолк и Зеллик 1992, стр. 379.
12. Навате, Рамез Эльмасри, Шамкант Б. (2010). Основы систем баз данных (6-е изд.). Река Аппер-Сэддл, Нью-Джерси: Pearson Education. стр. 652–660. ISBN 9780136086208.{{cite book}}: CS1 maint: multiple names: authors list (link)
13. Кнут 1998, стр. 488.
14. Томашевич, Майло (2008). Алгоритмы и структуры данных . Белград, Сербия: Академская мисао. стр. 274–275. ISBN 978-86-7466-328-8.
15. Ригин AM, Шершаков SA (2019-09-10). "SQLite RDBMS Extension for Data Indexing Using B-tree Modifications". Труды Института системного программирования РАН . 31 (3). Институт системного программирования РАН (ИСП РАН): 203–216. doi : 10.15514/ispras-2019-31(3)-16 . S2CID  203144646 . Получено 29.08.2021 .
16. Подсчитанные B-деревья, получены 25.01.2010
17. Руководство по продукту: Barracuda ES.2 Serial ATA, Rev. F., публикация 100468393 (PDF) . Seagate Technology LLC. 2008. стр. 6.
18. Клеппманн, Мартин (2017). Проектирование приложений с интенсивным использованием данных. Севастополь, Калифорния : O'Reilly Media . стр. 80. ISBN 978-1-449-37332-0.
19. Ян Яннинк. «Реализация удаления в B+-деревьях». Раздел «4 Ленивое удаление».
20. Комер 1979, с. 127; Кормен и др. 2001, стр. 439–440.
21. "Удаление в B-дереве" (PDF) . cs.rhodes.edu . Архивировано (PDF) из оригинала 2022-10-09 . Получено 24 мая 2022 .
22. "Cache Oblivious B-trees". Государственный университет Нью-Йорка (SUNY) в Стоуни-Брук . Получено 17.01.2011 .
23. Марк Руссинович (30 июня 2006 г.). "Внутри Win2K NTFS, часть 1". Microsoft Developer Network . Архивировано из оригинала 13 апреля 2008 г. Получено 2008-04-18 .
24. Мэтью Диллон (21.06.2008). "Файловая система HAMMER" (PDF) . Архивировано (PDF) из оригинала 09.10.2022.
25. Lehman, Philip L.; Yao, s. Bing (1981). «Эффективная блокировка для параллельных операций на B-деревьях». ACM Transactions on Database Systems . 6 (4): 650–670. doi : 10.1145/319628.319663 . S2CID  10756181.
26. Ван, Пол (1 февраля 1991 г.). "Углубленный анализ параллельных алгоритмов B-дерева" (PDF) . dtic.mil . Архивировано из оригинала (PDF) 4 июня 2011 г. . Получено 21 октября 2022 г. .
27. "Загрузки - high-concurrency-btree - Высококонкурентный код B-Tree на языке C - Хостинг проектов GitHub". GitHub . Получено 27.01.2014 .
28. «Безблокировочный параллельный метод метадоступа индекса B-дерева для кэшированных узлов».
29. Знакомимся с кленами (LWN.net)
30. Maple Tree (документация ядра Linux)
31. Знакомимся с Maple Tree (LWN.net / github)

Источники

• Байер, Р.; МакКрейт , Э. (1972). «Организация и ведение больших упорядоченных индексов» (PDF) . Acta Informatica . 1 (3): 173–189. doi :10.1007/bf00288683. S2CID  29859053..
• Комер, Дуглас (июнь 1979 г.). «Вездесущее B-дерево». 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-е изд.). Эддисон-Уэсли. 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-tree и UB-tree на Scholarpedia Куратор: д-р Рудольф Байер
• B-деревья: сбалансированные древовидные структуры данных. Архивировано 05.03.2010 на Wayback Machine.
• Словарь алгоритмов и структур данных NIST: B-дерево
• Учебное пособие по B-дереву
• Реализация InfinityDB BTree
• Кэш-забывчивые B(+)-деревья
• Словарь алгоритмов и структур данных, статья для B*-дерева
• Открытые структуры данных - Раздел 14.2 - B-деревья, Пэт Морин
• Подсчитанные B-деревья
• B-Tree .Net, современная виртуализированная реализация RAM и Disk

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

• Шетти, Соумья Б. (2010). Настраиваемая пользователем реализация B-деревьев (диссертация). Университет штата Айова.
• Калдырым, Семих (28 апреля 2015 г.). «Организация файлов, ISAM, дерево B+ и массовая загрузка» (PDF) . Анкара, Турция: Университет Билькента . стр. 4–6. Архивировано (PDF) из оригинала 2022-10-09.
• "ECS 165B: Реализация системы баз данных: Лекция 6" (PDF) . Калифорнийский университет в Дэвисе . 9 апреля 2010 г. стр. 23. Архивировано (PDF) из оригинала 2022-10-09.
• «BULK INSERT (Transact-SQL) в SQL Server 2017». Microsoft Docs. 6 сентября 2018 г.