Отсканируйте QR-код ниже или WeChat, чтобы найти официальную учетную запись.
菜鸟飞呀飞, вы можете следить за публичной учетной записью WeChat, читать дальшеSpring源码分析,Java并发编程а такжеNetty源码系列статья.
Дерево
Дерево — очень распространенная структура данных, по количеству дочерних узлов мы можем разделить дерево на двоичное дерево и дерево с несколькими ветками. Дерево с не более чем двумя дочерними узлами на узел называется двоичным деревом.Типичные двоичные деревья включают двоичное дерево поиска, полное двоичное дерево, полное двоичное дерево, двоичное сбалансированное дерево и красно-черное дерево. Дерево с более чем двумя дочерними узлами называется полидеревом.Обычные полидеревья включают B-дерево и B+ дерево.
B-дерево и B+-дерево — это своего рода дерево многостороннего поиска, которое произошло от двоичного дерева поиска и часто используется в индексной структуре базы данных, а B+-дерево и B-дерево имеют много общего и их легко спутать, поэтому эта статья поставит их вместе для изучения и сравнения.
B-Tree
B-дерево также называют B-деревом.Многие люди видят B+дерево (B+Tree), поэтому они часто рассматривают B-дерево и B-дерево как два вида деревьев.На самом деле B-дерево и B-дерево такое же дерево (Слово B-Tree переводится как B-дерево). (Это «многие люди» включает и автора. Автор — новичок. Сначала B-Tree, B-tree и B+Tree рассматривались как три вида деревьев. Позже я проверил в Интернете, чтобы выяснить это).
Для структуры данных дерева существует концепция описания структуры дерева, называемая степенью (также называемой порядком), которая описывает количество дочерних узлов в узле, например, двоичное дерево, каждый узел имеет не более двух дочерних узлов. , поэтому степень (порядок) бинарного дерева равна 2. Для B-дерева также существует понятие порядка, например, B-дерево 5-го порядка, что означает, что каждый узел имеет не более 5 дочерних узлов.
Для B-дерева порядка m оно обладает следующими свойствами:
- Каждый узел имеет не более m дочерних узлов;
- Каждый нелистовой узел (кроме корневого узла) содержит не менее m/2 дочерних узлов;
- Если корневой узел не является конечным узлом, то корневой узел имеет как минимум два дочерних узла;
- Для нелистового узла он может хранить до m-1 ключевых слов (под так называемыми ключевыми словами можно понимать данные, хранящиеся на узле);
- На каждом узле все ключевые слова упорядочены слева направо и от меньшего к большему;
- Значение левого поддерева каждого ключевого слова меньше текущего ключевого слова, а значение правого поддерева больше текущего ключевого слова;
- Каждый узел содержит индекс и данные (это важно помнить, это одно из самых важных отличий от B+Tree, описанного ниже).
Из приведенных выше свойств для корневого узла B-дерева диапазон количества ключевых слов составляет 1
1. Вставьте
При вставке данных в B-Tree m-порядка, чтобы обеспечить свойства вышеупомянутого B-Tree, нам необходимо вставить ключевые слова (вставить данные) по следующим правилам: после вставки ключевых слов в текущий узел, Определить, являются ли количество ключевых слов текущего узла меньше или равно m-1, если меньше, то вставка заканчивается, иначе текущий узел нужно разделить, как разделить? Разделить на m/2, чтобы сформировать левую и правую части, то есть два новых дочерних узла, а затем переместить ключевое слово на m/2 в родительский узел (разделить от середины).
Для B-дерева 5-го порядка (то есть некорневых узлов, диапазон количества ключевых слов 2
Затем, когда мы снова вставляем 20, в текущем узле хранится 5 ключевых слов. Поскольку текущее дерево является деревом 5-го порядка, каждый узел может хранить не более 4 ключевых слов. Текущий узел разделяется. Как разделить? Это разделить узел на левую и правую части от середины (м/2) (5/2 округлить до 3), поэтому разделить с места, где находится число 30, а затем поместить число 30 в родительский узел (Поскольку родительский узел в это время пуст, создается новый узел, а затем в узел помещается 30), и тогда два числа 20 и 25 слева от 30 образуют новый узел, а два числа на правые 40 и 50 составляют новый узел, и эти два новых узла указывают на левую и правую стороны ключевого слова 30 соответственно. Схематическая диаграмма выглядит следующим образом:
Продолжайте вставлять данные 15, 10, 13 в дерево. При вставке до 13 мы обнаруживаем, что количество ключевых слов в узле снова превышает m-1, поэтому нам нужно снова разбить узел. В это время средний номер 15 отделяется и помещается в родительский узел, а оставшиеся левая и правая части составляют новые узлы соответственно.
Продолжайте вставлять данные в дерево еще раз: 18, 60, 55, 45, 26, 17, 8, 3, 5. Наконец, структура B-Tree показана на рисунке ниже.
Все изображения, размещенные в статье, являются статическими изображениями.Если вы хотите испытать динамический процесс вставки данных B-Tree, вы можете перейти на следующий обучающий веб-сайт, чтобы вручную вставить данные и испытать динамический процесс вставки данных. (URL:Ууууу, в это время Джейд А. Квота из США/~Карри Лакса/виз…Очень хороший сайт для изучения структур данных и алгоритмов)
2. Найдите
Операция поиска B-Tree относительно проста, аналогична поиску в двоичном дереве поиска.
- Начать поиск с корневого узла, пройтись по ключевым словам корневого узла по очереди и найти первое ключевое слово, которое не меньше искомых данных;
- Определить, равны ли искомые данные текущему ключевому слову, и если да, вернуть данные;
- Если он не равен, это указывает, меньше ли данных для поиска, чем текущее ключевое слово, поэтому введите левое поддерево текущего ключевого слова для поиска, процесс поиска аналогичен процессу поиска корневого узла, и выше шаги можно повторять.
Взяв данные B-дерева выше в качестве примера, найдите число 10. Сначала начните поиск с корневого узла.Первое ключевое слово не менее 10 равно 20. Поскольку данные для поиска 10 не равны ключевому слову 20, введите левое поддерево ключевого слова 20 для поиска, а указатель указывает к ключевому слову 8. Узел, где расположены , 15, первое ключевое слово не менее 10 в этом узле равно 15, поэтому введите левое поддерево ключевого слова 15 для поиска, в это время указатель указывает на узел, где ключевые слова 10 и 13, и обнаруживаем, что ключ 10 в этом узле равен искомым данным, поэтому он возвращается. (Как показано на рисунке ниже, красным цветом обозначен путь в процессе поиска)
Если вам нужно число 60, процесс такой же, как описано выше, начните с корневого узла и обнаружите, что все ключевые слова в корневом узле меньше 60, поэтому введите правое поддерево последнего ключевого слова корневого узла. для поиска, то есть введите ключевое слово 20 search в правом поддереве . Точно так же обнаруживается, что в узлах, где расположены ключевые слова 30 и 50, все ключевые слова меньше 60, поэтому введите правое поддерево последнего ключевого слова 50 текущего узла для поиска и, наконец, найдите 60 и верните данные. Как показано на рисунке ниже, красным цветом обозначен путь в процессе поиска)
3. Удалить
В процессе вставки данных в B-Tree, чтобы удовлетворить свойства B-Tree, будет происходить процесс разбиения узлов посередине.Также в процессе удаления данных можно удалить определенный ключевое слово и вызвать неудовлетворенность.Связанный характер B-Tree уже не актуален, поэтому будут возникать ситуации типа слияния узлов в процессе удаления.Процесс удаления относительно сложен, но в целом его можно отнести к следующим три сценария.
- Если это листовой узел, после удаления ключевого слова количество ключевых слов в листовом узле не меньше m/2, затем удалите ключевое слово напрямую;
- Если это листовой узел, то после удаления ключевых слов количество ключевых слов в листовом узле меньше, чем m / 2. В это время свойства B-дерева не удовлетворяются, поэтому необходимо заимствовать ключевые слова из родственные узлы. Если количество ключевых слов в родственном узле больше, чем m/2, то вы можете заимствовать, сначала переместить родительский узел в текущий узел, а затем переместить ключевое слово родственного узла в родительский узел; если ключ родственный узел Количество слов меньше или равно m / 2. Предполагая, что родственный узел предоставляет ключевое слово, количество его собственных ключевых слов меньше m / 2, и это не соответствует природе B-дерева. , поэтому его нельзя использовать в настоящее время.Кстати, после удаления ключевого слова, которое нужно удалить, переместите родительский узел сюда, а затем объедините текущий узел и родственный узел.
- Если это нелистовой узел для удаления ключевого слова, то вам нужно сначала удалить текущее ключевое слово, затем использовать наименьшее ключевое слово в правом поддереве, чтобы заполнить текущую позицию, а затем удалить только что добавленное ключевое слово из правого поддерева. Это снова операция удаления B-Tree. (Наименьшее ключевое слово в правом поддереве должно быть в конечном узле, поэтому процесс удаления заключается в удалении ключевого слова в конечном узле, что является процессом сценария 1 и сценария 2).
В сочетании с конкретными примерами приведенные выше три сценария приведены в качестве примеров для иллюстрации процесса операции удаления, взяв в качестве примера следующие данные.
Удалите из B-дерева ключевое слово 29. Поскольку узел, в котором находится ключевое слово 29, является конечным узлом, при удалении 29 количество ключевых слов в текущем узле равно 3, что означает, что осталось много ключевых слов. после удаления.Если m/2 (5/2=2), вышеупомянутый сценарий 1 выполняется, то ключевое слово может быть удалено напрямую.
Продолжайте удалять из B-дерева ключевое слово 55. Поскольку узел, в котором находится ключевое слово 55, является конечным узлом, при удалении 55 количество ключевых слов, оставшихся в текущем узле, равно 1, что меньше m/2. , поэтому для одноуровневых узлов необходимо заимствовать ключевые слова. В родственных узлах текущего узла есть 4 ключевых слова (40, 45, 47, 49), которые больше, чем m/2, поэтому ключевые слова можно одолжить, что соответствует первому случаю сценария 2. Поэтому сначала удалите ключевое слово 55, затем переместите ключевое слово 50 в родительском узле на текущий узел, а затем переместите ключевое слово 49 в родственном узле в родительский узел, как показано на диаграмме ниже.
Продолжайте удалять из B-дерева ключевое слово 17. Поскольку узел, в котором находится ключевое слово 17, является конечным узлом, при удалении 17 количество ключевых слов, оставшихся в текущем узле, равно 1, что меньше m/2. , поэтому для одноуровневых узлов необходимо заимствовать ключевые слова. В родственных узлах текущего узла есть 2 ключевых слова (10, 13), которые меньше, чем m/2, поэтому ключевые слова нельзя одолжить, что соответствует второму случаю сценария 2. Поэтому сначала удалите ключевое слово 17, затем переместите ключевое слово 15 в родительском узле на текущий узел, а затем объедините текущий узел с родственным узлом (узлы, в которых расположены ключевые слова 10 и 13). Схематическая диаграмма выглядит следующим образом.
Затем мы обнаружили, что при удалении ключевого слова 17 мы удалили ключевое слово из родительского узла (узла, где находится ключевое слово 8), и в его родительском узле осталось только одно ключевое слово, а родительский узел снова не соответствует природа B-Tree, так что мы должны продолжать. Пусть родительский узел найдет свои собственные одноуровневые узлы, чтобы продолжить заимствование ключевых слов.В это время у родительского узла нет одноуровневых узлов слева, поэтому он находит правые одноуровневые узлы (узлы, в которых расположены ключевые слова 30 и 49) для заимствования ключевых слов. Оказывается, количество ключевых слов узла-сестра справа не превышает m/2.Если узел-брат выдает ключевые слова, это не соответствует природе, поэтому на этот раз он соответствует второму сценарию сценарий 2 мы упоминали выше ситуацию, поэтому узлы необходимо объединить. Итак, следующая операция: переместите родительский узел ключевого слова 8 в узел, где находится 8, а затем объедините узлы, где находятся ключевые слова 8 и 30, 49. Схематическая диаграмма выглядит следующим образом:
Продолжайте удалять из B-дерева ключевое слово 20. В настоящее время узел, в котором находится 20, не является конечным узлом, поэтому сценарий 3 выполняется. Поэтому удалите ключевое слово 20 напрямую, затем возьмите наименьшее ключевое слово 25 из правого поддерева 20 и заполните им позицию 20, и, наконец, удалите ключевое слово 25 из узла правого поддерева.Процесс удаления также может соответствовать сценарии удаления листовых узлов выше. Схематическая диаграмма выглядит следующим образом:
Выше приведен процесс удаления ключевых слов в дереве B. По сравнению с процессом вставки и поиска процесс удаления более сложен, поэтому лучше всего перейти к этомуВизуальный сайтучиться. (Открыть на ПК, URL:Ууууу, в это время Джейд А. Квота из США/~Карри Лакса/виз…На этом веб-сайте визуализации при удалении ключевых слов нелистовых узлов заполняется самое большое ключевое слово в левом поддереве, а при объяснении этой статьи заполняется наименьшее ключевое слово в правом поддереве. , оба должны удовлетворять свойствам B-дерева и гарантировать, что все ключевые слова на каждом узле упорядочены. В процессе изучения структур данных и алгоритмов не нужно останавливаться на деталях, главное научиться думать.
Суммировать
Суммируйте момент. В этой статье в основном объясняются связанные свойства B-Tree и подробно описывается процесс вставки, поиска и удаления с помощью схематического представления. В примере в статье я намеренно не добавлял повторяющиеся данные в B-дерево, так что мне делать, если я добавляю повторяющиеся данные в B-дерево? Если есть повторяющиеся числа, нам нужно только решить, поместить повторяющиеся числа в левое поддерево или правое поддерево при вставке, какую сторону вы можете определить сами. При поиске данных нельзя прекращать поиск сразу после нахождения фрагмента данных, соответствующего требованиям, и нужно продолжать поиск до тех пор, пока не появятся первые данные, не соответствующие требованиям. Аналогично, при удалении также нужно удалить все данные.
Объем ограничен, поэтому знания, связанные с B+Tree и индексацией базы данных, будут представлены в следующем блоге.