Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
Сегодня пятница Распределенные системыГлава 8Основное содержание статьиВ+ деревопринцип.
Сегодняшняя статья является продолжением B-дерева прошлой недели, поэтому новые заинтересованные или забытые студенты предлагают просмотреть предыдущий контент по ссылке ниже.
Hardcore Challenge - Иллюстрирование B-деревьев с нуля
Свойства деревьев B+
Дерево B+ такое же, как дерево BМногостороннее сбалансированное дерево, также называемое деревом с несколькими разветвлениями. Свойства этих двух в основном одинаковы.Прежде чем подробно рассматривать детали, давайте в общих чертах рассмотрим характеристики дерева B+, чтобы получить общее впечатление.
Лично я считаю, что большинство функций дерева B+ такие же, как у дерева B, единственное отличие заключается в следующем:
- Все данные хранятся в листовых узлах, промежуточные узлы не хранят данные
- Количество элементов в промежуточном узле равно количеству поддеревьев, а количество поддеревьев в B-дереве на 1 больше, чем количество элементов
- Листовой узел — это связанный список, в котором можно искать по указателям.
Я выложил картинку, каждый должен чувствовать это интуитивно.
Из приведенного выше рисунка видно, что все элементы, которые появляются в промежуточных узлах, можно найти в листовых узлах, что соответствует тому факту, что все только что упомянутые данные хранятся в листовых узлах. Тогда мы также можем обнаружить, что количество элементов в промежуточном узле равно количеству поддеревьев, что также соответствует интервальному делению. Каждый элемент родительского узла соответствует самому большому элементу в поддереве.
Что касается окончательного связанного списка, то его следует хорошо понимать, это не более чем то, что связанный список появляется в дереве, что выглядит немного по-новому.
Самое большое чувство, которое я испытываю, глядя на картинку выше, — это сходство, оно так похоже на B-дерево, оно как два брата-близнеца. Так что же нам делать с таким знакомым и незнакомым деревом?CRUDШерстяная ткань?
Продолжим смотреть вниз, а перед этим хочу сказать, что хотя дерево B+ является улучшенной версией дерева B, сложность реализации на самом деле снижена. То есть в целом это лучше, чем B-tree.легче реализовать.
Проверка дерева B+
Поскольку все данные в дереве B+ хранятся влистовой узел, поэтому, когда мы ищем, мы должны искать до конечного узла. То есть в середине отводов больше не будет, что упрощает наше суждение и почти больше не требует отхода на время.
Другая особенность заключается в том, что количество элементов в дереве B+ совпадает с количеством поддеревьев, и каждый элемент представляет максимальное значение в поддереве. С этим ограничением мы можем легко определить, в каком поддереве находится искомый элемент. B-дерево может быть за пределами границ, и нам нужно специальное суждение.
В качестве примера, вот B-дерево:
Предположим, что элемент, который мы ищем, равен 12, мы судим по корневому узлу, сначала находим 9 с помощью бинарного поиска и обнаруживаем, что 12 > 9, поэтому мы переходим к самому правому поддереву для проверки.
А если это дерево B+, то оно будет таким: для удобства рисования я опустил горизонтальный указатель в листовом узле.
Видно, что мы можем точно найти соответствующее поддерево прямым делением пополам, мырекурсивно внизДостаточно. Если он за гранью, значит, его точно нет на дереве и его можно вернуть заранее.
Итак, это очень простой поиск по дереву.Следует сказать, что пока вы понимаете форму дерева и идею рекурсии, не должно возникнуть никаких трудностей. Однако важно отметить, что наш поисковый интерфейс предоставляется не только внешнему миру, при вставке нам также необходимо найти соответствующую позицию (узел) перед выполнением вставки. Очевидно, элементы, которые мы хотим вставить, вероятно, не находятся в дереве (иначе это называется вставками), поэтому мы не можем вернуть пустой элемент в данный момент, нам нужно вернуть настоящий узел.
Таким образом, мы можем передать флаг, чтобы отметить, является ли это стадией вставки нашего внутреннего вызова.Флаг по умолчанию имеет значение False, поэтому он не влияет на внешние вызовы.
Если флаг равен True, мы не можем выйти раньше, если не найдем его посередине, и нам нужно продолжить поиск. И мы также можем обновить значение самого правого элемента.
Также используйте приведенное выше изображение в качестве примера:
Если мы вставим элемент 15, все дерево станет:
видеть это,12 в корневом узле заменено на 15, что также соответствует вышеупомянутому узлу, где каждый элемент соответствует максимальному значению в поддереве. Мы также можем сначала вставить, а затем обновить родителя, но мы также можем обновить непосредственно при поиске.Когда мы обнаруживаем, что вставляемый элемент больше, чем самый большой элемент текущего узла, мы напрямую заменяем его, что может сохранить некоторый код.
Давайте посмотрим на код:
def _query(self, node, key, flag=False):
"""
:param node: 当前节点
:param key: 待寻找的key
:param flag: 是否是插入阶段
:return: True/False 是否找到，对应的节点，key在节点中的下标
"""
# 如果是叶子节点，说明没有childs
if node.is_leaf:
# 校验当前是否为空
if node.length == 0:
return False, node, 0
# 二分查找
pos = bisect_left(node.keys, key)
# 如果没找到，返回False
if pos == node.length or node.keys[pos] != key:
return False, node, 0
else:
return True, node, pos
else:
pos = bisect_left(node.keys, key)
# 递归
if pos == len(node.childs):
if not flag:
return False, node, 0
else:
# 如果是插入阶段，待插入的元素大于所有元素
# 直接替换最后一个元素
node.keys[-1] = key
pos -= 1
return self._query(node.childs[pos], key, flag)
Все должны были заметить, что конечный узел B+-дерева представляет собой связанный список, и каждый узел имеетследующий указательуказывает на своего правого брата. Таким образом, мы также можем найти элементы через связанный список, этот код несложно написать, это простообход связанного списка, здесь не так много деталей, давайте посмотрим непосредственно на код:
def seq_query(self, key):
node = self.head
# 循环遍历链表
while node is not None:
# 二分查找是否在当前节点
pos = bisect_left(node.keys, key)
# 如果大于当前的所有元素
if pos == node.length:
# 如果没有后续了说明没找到
if node.next is None:
return False, None
node = node.next
continue
# 如果找到了判断是否是我们要的
if node.keys[pos] == key:
return True, node.values[pos]
else:
return False, None
Рост дерева B+
Второй методдобавить элемент, логика добавления элементов в основном такая же, как и у B-дерева, но есть небольшие изменения.
Подобно B-деревьям, все операции вставки B+-деревьев такжеВстречается в листовых узлах. Итак, мы находим узел, подходящий для вставки этого элемента, через операцию поиска и вставляем его. Поскольку количество элементов в узле ограничено деревом B+, максимальное число не может превышать M, а значит, операция вставки может привести к нелегальности, поэтому нам нужно оценить эту ситуацию.Если вставка приведет к нелегальности, нам нужно принять меры для поддержания характера структуры данных.
Принимаемые меры очень просты.Как и в дереве B, если количество узловых элементов превышает стандартное, торазделять.
Но его операция разделения будет немного отличаться, давайте посмотрим:
Если это B+-дерево 4-го порядка, то при вставке элемента оно разделится. Например, если мы вставим 5, мы можем получить:
Заметили ли вы, что, поскольку при разделении будут созданы два поддерева, верхний узел будет иметьдва элемента, тогда как B-дерево имеет только один элемент.
Но если в корневом узле разделения не произойдет, то будет загружен только один элемент, как и в B-дереве.
Давайте посмотрим на другой пример:
Если мы добавим элемент 12 в этот момент, количество элементов в третьем поддереве превысит предел, и произойдет разделение:
Наш последний узел разделился после вставки элемента, но загрузил только 10 в родительский узел, поскольку 15 уже находится в родительском узле, загружать не нужно.
Конечно, этот граф не является окончательным, и корневой узел явно превышает лимит и нуждается в дальнейшем разбиении, и в итоге становится таким:
Конечно, это только общая логика, и есть много деталей, которые необходимо учитывать в процессе нашей реализации. Например, является ли текущий узел листовым узлом? Если это листовой узел, то у него нет поддеревьев, которые нужно разбить, но есть значения, которые нужно разбить. Если это не конечный узел, после его разделения нам все еще нужно поддерживать его дочерние элементы и базовый связанный список, но, хотя этих деталей много, логика не сложна, пока мы реализуем всеУточните детали, и делатьсистемное тестирование, это не сложно.
Здесь мы ориентируемся на время деленияОбработка следующего указателя, предполагая, что текущий bt_node является конечным узлом, при его разделении будут сгенерированы два новых узла, которые мы назовем lnode и rnode. После этого нам нужно обновить bt_node до родительской ноды и объединить родительскую ноду.Как мы поддерживаем следующий указатель в это время?
Мы можем свободно думать, что следующий из lnode должен указывать на rnode, а следующий из rnode должен указывать на следующий из node, ноКак сделать так, чтобы следующий перед bt_node указывал на lnodeШерстяная ткань?
Один из способов заключается в том, что мы можем передать в функцию левого брата узла, но это потребует много операций. Например, нам нужно сначала найти левого брата, этот поиск на самом деле не простой, потому что левого брата и его может не быть в поддереве, и нам также нужно судить о ситуации, что левого брата не существует. Так что это все еще очень хлопотно, или мы можем сохранить лишний указатель налево, чтобы мы могли легко найти левого брата. Один из способов, о котором я подумал, заключался в том, чтобы использовать трюк с хранилищем ссылок в Python, чтобы избежать этих сложных операций.
Мы предполагаем, что левый родственный узел является братом, а ссылка на узел bt_node хранится в следующем из братьев, то есть адрес узла в памяти. Хитрость заключается в том, чтобы сделать lnode равным bt_node, то есть использовать ссылку lnode, чтобы указать на bt_node, а затем вручную обновить значение в lnode до того, что нам нужно. Таким образом, эта проблема обходится хитрым подходом. Давайте посмотрим на код:
bt_node_next = bt_node.next
lnode = bt_node
# 手动更新lnode
lnode.update()
rnode = BTree.BTreeNode(keys=rkeys, childs=rchilds, is_leaf=bt_node.is_leaf, father=node, pos_in_father=1, values=rvals)
lnode.next = rnode
rnode.next = bt_node_next
Этот код не сложен, но придумать этот трюк непросто, и он требует определенного понимания механизма ссылок Python. Это всего лишь уловка реализации, и к алгоритму отношения не имеет, ученики, которые не понимают, могут его игнорировать.
Поняв это, давайте, наконец, рассмотрим удаление дерева B+.
Удаление дерева B+
Логика удаления дерева B+ и дерева Bточно так же, но детали конкретной операции немного отличаются.
Как и в случае с B-деревьями, все удаления происходят влистовой узел, но поскольку все элементы дерева B+ имеют конечные узлы, нет необходимости рассматривать удаление промежуточных узлов и замену их последующими. Мы можем напрямую найти конечный узел для удаления и обслуживания. Надо сказать, что это намного проще.
удалить напрямую
Как и в B-дереве, если количество элементов листового узла велико, то удалите его напрямую.
Например, на приведенном выше рисунке мы хотим удалить 13. Поскольку листовые узлы богаты, мы можем удалить их напрямую и получить:
Об этом и говорить нечего, но если мы удалим 15, хотя она тоже удаляется напрямую, то будут некоторые проблемы. Думаю, каждый должен был обнаружить, что 15 — это не только один из конечных узлов, но итакже появляются на промежуточных узлах, если убрать 15, то очевидно нужнообновить эту ссылкуна узле.
Нам нужно пройти весь путь назад и изменить их значения на наибольшее значение после удаления 15. Эта деталь здесь не совпадает с B-деревом и на нее нужно обратить внимание. Результат после обновления должен выглядеть так:
Нам также нужно решить, когда мы вернемся назад.Последний измененный узел является самым большим значением в родительском узле, и нам нужно вернуться, потому что самое большое значение в родительском узле также находится в родительском узле родительского узла.Если вам не нужно просто изменять его, не нужно снова возвращаться, давайте посмотрим на код:
def upload(self, bt_node, father, key):
if father is None:
return
# 修改父节点中值
father.keys[bt_node.pos_in_father] = key
grand_fa = father.father
# 如果修改的是父节点中最大的值，继续往上回溯
# 因为父节点中的最大值也在爷爷节点中
if bt_node.pos_in_father == father.length-1 and grand_fa is not None:
self.upload(father, grand_fa, key)
Здесь есть очень интересный момент, то есть, когда я впервые реализовал это, я забыл, что мне нужно продолжать откат, и рассматривал только обновление родительского узла, а не откат все время. Но я протестировал его на большом количестве данных и обнаружил, что он все еще верен.
Я подумал об этом чуть позже и обнаружил, что на самом деле нет необходимости постоянно возвращаться назад. Потому что при поиске мы не можем определить, существует ли элемент в верхнем узле. Например, в приведенном выше примере, если я возвращался только на один уровень, я не возвращался к верхнему уровню. Дерево будет выглядеть так:
То есть 15 все еще хранится в корневом узле, но 15 на данный момент удалено. На самом деле это не влияет на наш поиск, потому что в дереве нет элемента больше 15, мы используем 15 для деления и 13 для деления на верхнем уровнеОба результата одинаковы, то есть рекурсия к поддереву справа. После рекурсии вниз данные верны, поэтому нам нужно только обновить конечные узлы, чтобы подняться на один уровень вверх. Но это только мое суждение. Я пока не придумал контрпример. Я приветствую студентов, у которых есть идеи, чтобы оставить мне сообщение.
Брат Нод Рич
Родственный узел богат. Очень просто мы можем заимствовать его из родственного узла. В отличие от B-дерева, поскольку все узлы находятся на листьях, мы можем напрямую заимствовать элементы родственного узла, но нам нужно обратите внимание на обновление значения в родительском узле.
Например, предположим, что мы хотим удалить 4 на изображении ниже, мы обнаруживаем, что его левый брат имеет расширенные элементы, мыБольше не нужно проходить через родительский узел, вы можете взять его напрямую.
Но после его заимствования будет небольшая проблема, то есть 3 в родительском узле недопустимо, потому что это уже не самый большой элемент в левом поддереве, а самым большим элементом становится 2. Поэтому нам нужно обновить это значение в родительском узле. То же самое и у нас, и у братьев справа, но направление другое, поэтому не буду вдаваться в подробности.
Братские узлы не богаты
Наконец, давайте рассмотрим ситуацию, когда одноуровневые узлы также небогаты. Это похоже на B-деревья, но немного отличается. В текущей ситуации мыБольше не нужно принудительно заимствовать элементы из родительских узлов.Теперь, если подумать, можно понять, что данные в родительском узле все на листьях, так что же еще заимствовать? Таким образом, мы не заимствуем элементы и объединяемся напрямую с братьями и сестрами.
Например, на рисунке ниже, если мы хотим удалить элемент 12, это приведет к нарушению предела, В это время мы напрямую объединяем два узла в красном поле.
После слияния принесетКоличество поддеревьев уменьшено, поэтому мы должны удалить элемент из родительского узла. Давайте посмотрим на картинку выше, и мы обнаружим, что хотим удалить 10 родительских узлов. Здесь мы должны судить, если левый брат объединен с текущим узлом, то мы хотим удалить максимальное значение левого брата, иначе это минимальное значение правого брата. После удаленияподдерживать родительский узел, мы обнаруживаем, что родительский узел больше не соответствует условиям и нуждается в обслуживании.
Очевидно, у него нет богатых братьев и сестер, поэтому мыпродолжать сливаться:
После той же операции мы обнаружили, что в родительском узле текущего узла, то есть корневом узле, остался только один элемент, что является недопустимым, поэтому нам нужно его отбросить и обновить корневой узел.
постскриптум
На данный момент введено добавление, удаление, модификация и проверка нашего дерева B+.Звучит очень страшно структура данных, но на картинке показано всего несколько картинок.Написанный мной код полностью не превышает 500 строк, это не очень страшная структура данных.Страшные числа. Много раз мы боимся таких операций, как деформация и вращение в структуре данных, но на самом деле все изменения мы рисуем в медитации, и их так много туда-сюда.Когда мы сопротивляемся и отступаем, нас побеждает не структура данных или проблема, а мы сдаемся.
Наконец, давайте подумаем над вопросом, почему размещение всех элементов в листовых узлах дерева B+ является оптимизацией? Не увеличивает ли это нагрузку на поиск? Мы могли найти элемент на полпути раньше, но теперь мы должны найти конец Как это можно считать оптимизацией?
Опять же, чтобы ответить на этот вопрос, понимания структур данных недостаточно, нужно еще и комбинировать сценарии использования. Мы все знаем сцену дерева B+, даБазовая структура реализации базы данных. Все мы знаем, что данных в базе данных очень много, и мы не можем хранить все данные в памяти. Произвольное чтение и запись диска очень трудоемки.Все данные мы размещаем на листовых узлах.При большом количестве добавлений и удалений мы можемБудет получать непрерывные данные для пакетных операций, что может сэкономить много времени. Кроме того, дерево B+ предназначено дляПакетное чтение более эффективно, чем B-деревьяНапример, если мы хотим прочитать интервал, мы можем сначала найти узел, а затем получать его пачками через следующий указатель. Наши операции обхода указателей — это последовательное чтение и запись, которые намного быстрее случайного чтения и записи.
То есть оптимизация дерева B+ отражается на чтении и записи диска, а не на алгоритме. Конечно, с точки зрения общей сложности реализации дерево B+ действительно проще. Если вас интересует исходный код, вы можете ответить на официальном аккаунте "В+ дерево", получите мой код, пожалуйста, не любите его.
Сегодняшний рассказ о дереве B+ здесь. Если вы чувствуете, что что-то приобрели, пожалуйста, нажмите здесь.Подпишитесь или сделайте ретвитЧто ж, твое маленькое усилие много значит для меня.
В этой статье используетсяmdniceнабор текста