Структура данных — дерево

Оригинальная ссылка:блог Прошлое и Ванга / 2018/06-T...

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

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

бинарное дерево

Двоичное дерево - Двоичное деревопредставляет собой древовидную структуру с не более чем двумя ветвями на узел (то есть нет узлов со степенью ветвления больше 2).

Классификация

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

траверс

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

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

бинарное дерево поиска

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

Сложность поиска, вставки, удаления равнавысота дерева,ожидать $O(\log_2^n)$ , наихудший O(n) (последовательность упорядочена, дерево вырождается в линейную таблицу)

Динамическое отображение бинарного дерева поиска:visualgo.net/zh/bst

дефект

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

Итак, было много улучшенийСбалансированное деревоструктура, удовлетворяющая наихудшему случаю высоты дерева $O(\log_2^n)$ , какРазвернуть дерево, сбалансированное двоичное дерево (SBT),АВЛ-дерево, красно-черное дерево и т.д.

красно-черное дерево

Красно-черное дерево - Красно-черное деревоявляется самобалансирующимся бинарным деревом поиска.В дополнение к свойствам бинарного дерева поиска оно также удовлетворяет следующим пяти свойствам:

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

преимущество баланса

Приведенные выше ограничения обеспечивают ключевые свойства красно-черных деревьев:Самый длинный путь от корня к листу не превышает удвоенного кратчайшего пути

Доказательство: обратите внимание на свойства 4 и 5. Если предположить, что на кратчайшем пути a от корня до листа есть n черных узлов, то самый длинный путь b должен состоять из чередующихся красных и черных узлов, причем все пути имеют одинаковое количество черных узлов. , Это означает, что количество черных узлов в b также равно n, но количество красных узлов в b не может превышать количество черных узлов, иначе свойство 4 (принцип ящика) будет нарушено, поэтому самый длинный путь от корня до лист не превысит кратчайший путь в два раза

регулировать

Поскольку каждое красно-черное дерево также является специализированным бинарным деревом поиска, операции только для чтения в красно-черном дереве аналогичны операциям только для чтения в обычном бинарном дереве поиска. Однако вставка и удаление красно-черного дерева приводит к тому, что свойства красно-черного дерева больше не совпадают. Требуется небольшое количество для восстановления свойств красно-черного дерева $O(\log_2^n)$ изменения цвета (которые на самом деле очень быстрые) и не более трех поворотов дерева (два для операций вставки). Хотя вставка и удаление сложны, время операции может оставаться таким же. $O(\log_2^n)$ Второсортный.

Когда красно-черное дерево изменяется, его необходимо настроить с помощью [обесцвечивания] и [поворота], а вращение делится на [левое вращение] и [правое вращение].

Чтобы изменить цвет, чтобы изменить цвет
Левша: поворот на X逆时针Поверните два узла X-Y красно-черного дерева так, чтобы родительский узел был заменен его правым дочерним элементом, а сам спустился к левому дочернему элементу.

Правое вращение: поворот на X顺时针Поверните два узла X-Y красно-черного дерева так, чтобы родительский узел был заменен его левым дочерним элементом, а сам спустился к правому дочернему элементу.

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

Вставить и удалить

вставить узел

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

Следовательно, шаги вставки следующие: Красно-черное дерево находит позицию в соответствии с правилами бинарного дерева поиска и вставляет новый узел z. Левый и правый потомки z оба являются нулевыми листовыми узлами, а узел z сначала красный, а затем в соответствии со следующими условиями. Выполните такие операции, как вращение с изменением цвета, и, наконец, добейтесь баланса.

Случай 1: еслиТекущий узел является корневым узлом, чтобы удовлетворить свойству 2, этот узел z сразу окрашивается в черный цвет
Случай 2: еслиРодительский узел текущего узла черный, т.к. свойства 2 и 4 не нарушаются, красно-черное дерево не уничтожается, так что в это время ничего не делать

Например, при вставке 12 на приведенный выше рисунок выполняется случай 2:

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

Сценарий 3: ЕслиРодительский узел текущего узла красныйиДругой дочерний узел (дядя-узел) дедушкиного узла красный.
Сценарий 4:Родительский узел текущего узла красный,дядя узел черныйили ноль, позиция текущего узла относительно его родителя и позиция родителя относительно его прародителяне с той стороны
Сценарий 5:Родительский узел текущего узла красный,дядя узел черныйили ноль, позиция текущего узла относительно его родителя и позиция родителя относительно его прародителяна той же стороне

Далее основное внимание уделяется тому, как настроить последние три ситуации.

Сценарий 3

当前结点的父结点是红色且祖父结点的另一个子结点(叔叔结点)是红色

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

Шаги решения: Покрасьте родительский узел и узел дяди текущего узла в черный цвет, а узел дедушки покрасьте в красный цвет, а затем обработайте узел дедушки как новый узел (то есть указатель текущего узла указывает на узел дедушки), перепроверьте различные ситуации и настроить

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

Вставляем элемент 21, и текущий узел указывает на 21:

В этот момент обнаружится, что два красных соединения 21 и 22 конфликтуют со свойством 4, но узел 21 удовлетворяет ситуации 3. После ремонта:

В этот момент текущий узел указывает на прародительский узел 21, что равно 25. И 25 узлов тоже столкнулись с проблемой ситуации 3, продолжаем ремонт:

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

Сценарий 4

当前结点的父结点是红色，叔叔结点是黑色或者 nil，当前结点相对其父结点的位置和父节点相对祖父节点的位置不在同侧

Шаги решения:

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

На основе вышеприведенного рисунка продолжаем вставлять 5 этот элемент:

Можно видеть, что 5 является левым дочерним элементом родительского узла, а родительский узел является правым дочерним элементом узла прародителя.Другой стороной является случай 4. Направьте текущий узел на родительский узел 6 из 5 и поверните вправо с 6 в качестве точки опоры:

В это время текущим узлом является 6, и 6 является правым дочерним элементом родительского узла 5, а родительский узел 5 также является правым дочерним элементом родительского узла 1. С той же стороны он превращается в ситуацию 5, и продолжайте смотреть вниз.

Сценарий 5

当前结点的父结点是红色，叔叔结点是黑色或者 nil，当前结点相对其父结点的位置和父节点相对祖父节点的位置在同侧

Шаги решения:

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

На основе предыдущего рисунка измените узел 5, чтобы он стал черным, узел 1 — красным, а затем поверните влево с 1 в качестве точки опоры:

восстановить равновесие

удалить узел

При удалении узла X первым шагом является определение того, являются ли оба потомка непустыми.Если оба непусты, он обрабатывается в соответствии с правилами бинарного дерева поиска:

При удалении узла X с двумя непустыми поддеревьями мы можем найти наибольший элемент в левом поддереве (или наименьший элемент в правом поддереве) и положить это максимальное значениекопироватьДля узла X замените только исходное значение, которое нужно удалить, не меняя цвет узла.

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

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

Возьмем в качестве примера граф, где треугольники представляют потенциально пустые поддеревья:

Узел X является удаляемым узлом.Обнаружено, что два его поддерева не пусты.Можно найти наибольший элемент Max в левом поддереве (или наименьший элемент Min в правом поддереве) и положить значение Max (или Минимальное значение) Скопируйте в X, чтобы перезаписать исходное значение, не изменяйте другие атрибуты, а затем удалите узел Max (или узел Min), вы можете ясно видеть, что самый ценный узел будет иметь не более одного непустого поддерева.

Следующий шаг — решить проблему удаления узла X, имеющего не более одного непустого поддерева.

Простой случай:

Если оба сына X пусты, т. е. оба являются листьями, мы рассматриваем любого из них как его сына.
еслиX - красный узел, его отец и сын должны быть черными, так простозамените его своим черным сыномЭто нормально, это не нарушает свойства 3 и 4, все пути через удаленный узел просто на один красный узел меньше, что гарантирует сохранение свойства 5.
еслиX черный, а его сын красный, если просто удалить этот черный узел,заменить его красным сыном, что нарушает свойство 5, мы можемперекрась своего сына в чёрного, то все пути, которые когда-либо проходили через X, будут проходить через его черного сына, сохраняющего свойство 5

Если X и его сын оба черные, это сложная ситуация, выделяем

Начнем с замены удаляемого узла X его дочерними элементами. Для удобства назовите этого нового старшего сына N, назовите его брата S, используйте P для вызова нового отца N, SL для вызова левого сына S и SR для вызова правого сына S.

Следует рассмотреть шесть сценариев:

Сценарий 1

N - новый корень

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

Случаи 2, 5 и 6 включают разные левые и правые случаи, и применяется только одно лечение.

Сценарий 2

S красный

Поменяйте местами цвета брата S и отца P
Если N является левым узлом своего родителя, мы делаем левый поворот родителя N, превращая красного брата в дедушку N.
Если N является правым узлом своего родителя, мы поворачиваем вправо родителя N, превращая красного брата в дедушку N.

После выполнения этих двух операций, хотя количество черных узлов на всех путях не изменилось, теперь у N есть черный брат и красный родитель, поэтому мы можем перейти к случаю 4, случаю 5 или случаю 6.

Сценарий 3

Отец N, сын S и S все черные

Перекрасить S в красный цвет
Возьмите P в качестве нового N, начните со случая 1 и выполните балансировку на P.

В этом случае мы просто перерисовываем S в красный цвет. В результате все пути через S имеют на одну черную вершину меньше. Это уравновешивается удалением исходного родителя X N, что приводит к тому, что на один черный узел меньше для всех путей через N. Однако все пути, проходящие через P, теперь имеют на один черный узел меньше, чем пути, не проходящие через P, так что свойство 5 по-прежнему нарушается. Чтобы исправить это, мы начинаем с случая 1 и делаем ребалансировку на P

Сценарий 4

Сыновья S и S черные, но отец N красный.

Поменяйте местами цвета брата N S и отца P

В этом случае мы просто меняем цвета брата и отца N. Это не влияет на количество черных узлов на путях, которые не проходят через N, но добавляет один к количеству черных узлов на путях, которые проходят через N, дополняя черные узлы, которые были удалены на этих путях.

Сценарий 5

S — черный, один из сыновей S — красный, а положение красного сына совпадает с положением N относительно отца.ипсилатеральный

Если N является левым узлом его родителя, левый дочерний элемент S красный, а правый дочерний элемент черный, выполните правый поворот на S
Если N является правым узлом своего родителя, левый дочерний узел S черный, а правый дочерний элемент красный, выполните левый поворот на S
Поменяйте S местами с его красным сыном перед ним.

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

В случаях 5 и 6 цвет родительского узла P может быть как черным, так и красным.

Сценарий 6

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

Поменяйте местами цвета отца N P и S
Если N является правым узлом своего отца, а левый сын S красный, а правый сын черный, сделайте правый поворот на отце N и сделайте левого сына S черным
Если N — левый узел своего отца, левый сын S — черный, а правый сын — красный, выполните левое вращение на отце N и сделайте правого сына S черным.

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

пример

Возьмите предыдущую картинку в качестве примера

Пробуем удалить каждый узел снизу вверх:

Если мы хотим удалить элемент 1, то по второму правилу в простом случае мы можем удалить 1 напрямую и заменить его нулевым узлом, а обработка элементов 6, 12 и 21 одинакова.
Если вы хотите удалить элемент 5, так как левое и правое поддеревья не пусты, найдите максимальное значение левого поддерева 1 (или минимальное значение правого поддерева 6) и замените 5 найденным значением (здесь просто замена значения, больше ничего не меняется), затем перейдите к удалению 1 узла, который переходит к проблеме 1
Если мы хотим удалить элемент 11, то по третьему пункту простого случая мы сразу удаляем 11, и заменяем его дочерним узлом 12, и при этом затемняем 12, обработка элемента 22 такая же, как и это
Если вы хотите удалить элемент 25, так как левое и правое поддеревья не пусты, найдите максимальное значение левого поддерева 22 (или минимальное значение правого поддерева 27), заменим здесь 25 на значение 22, а цвет остается неизменным. Затем перейдите к удалению 22 узлов, что становится предыдущей проблемой.
Если вы хотите удалить элемент 27, черный нулевой листовой узел заменяет узел 27, потому что у родственного узла 22 есть красный дочерний элемент, и он находится слева, а положение нулевого узла относительно родителя 25 отличается. , который относится к случаю 6, поэтому первый шаг — поменять местами цвета 22 и 25, затем повернуть вправо с 25 в качестве точки поворота, а затем закрасить узел 21 черным цветом.
Если вы хотите удалить элемент 8, выберите минимальное значение правого поддерева 11, чтобы заменить 8. Затем перейдите к удалению узла 11, соответствующего вопросу 3.
Если вы хотите удалить элемент 17, выберите для левого поддерева максимальное значение 15 и замените 17. Затем перейдите к удалению узла 15, процесс увидит следующий вопрос
Если вы хотите удалить элемент 15, и удаленный элемент, и замененный элемент будут черными, что является сложным случаем. Убедитесь, что его тип может соответствовать случаю 2. Элемент 15 — это удаленный X, и он заменен нулевым узлом, то есть N, 17 — P, а 25 — S. Согласно вышеизложенному, первый шаг — заменить P и цвет S., а затем поверните налево с точкой опоры P. В это время у N есть черный брат 22 и красный отец 17:

В это время брату N S становится 22, P становится 17, а левому ребенку S становится красный 21, что относится к случаю 5. S поворачивается вправо и меняет цвета 22 и 21:

В это время брат N S становится черным 21, но красный дочерний узел 21 становится правой стороной, попадая в ситуацию 6.

Узел P 17 поворачивается влево и закрашивает правый узел S, и в это время дерево возвращается к равновесию.

Если вы хотите удалить корневой узел 14, возьмите максимальное значение 12 в левом поддереве вместо 14. Затем перейдите к удалению узла 12, соответствующего проблеме 1.

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

Динамическое отображение красно-черного дерева:Ууууу, в это время Джейд А. Квота из США/~Карри Лакса/виз…

Практические проблемы

Красно-черное дерево по-прежнему является типичной двоичной структурой дерева поиска и в основном используется в реализации некоторых типов карт и наборов, таких как TreeMap в Java и set/map/multimap в C++. Временная сложность его поиска $O(\log_2^n)$ Что касается глубины дерева, уменьшение глубины дерева может повысить эффективность поиска.

Хэш-карта Java и карта golang реализованы с помощью хэшей.

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

Основная идея заключается в использовании多叉树结构, поэтому появляется следующее дерево сбалансированного многоканального поиска

B-дерево (B-дерево)

B-дерево, которое является B-деревом, не читается как B-минус дерево

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

определение

Существует два определения B-деревьев: одно — B-дерево, ограниченное порядком (описано ниже), а другое — B-дерево, ограниченное степенью (описано во введении к алгоритму). два похожи. номер для определения

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

Диапазон количества ключевых слов для всех узлов, кроме корневого узла: [ $\lceil\frac m2\rceil$ -1, m-1]
Если нелистовой узел содержит n ключевых слов, имеется n+1 поддеревьев, и диапазон количества поддеревьев можно узнать из диапазона ключевых слов: [ $\lceil\frac m2\rceil$ , m]
Корневой узел содержит не менее одного ключевого слова и имеет не менее двух дочерних элементов (если только в дереве B нет только одного узла: корневого узла), то есть диапазон количества ключевых слов корневого узла: [1, m -1], диапазон количества детей: [2, m]
Все листовые узлы находятся в одном слое, то есть высота одинаковая
Ключевые слова в каждом узле упорядочены от меньшего к большему, а элементы k-1 в узле точно соответствуют диапазону значений элементов, содержащихся в k дочерних элементах.

Фигура является типичной2-3-4 ДеревьяСтруктура также является B-деревом порядка 4. Запрос элементов из графа требует не более 3 дисковых операций ввода-вывода для доступа к нужным нам узлам данных Чтение блоков данных узла в память, а затем поиск указанных элементов будет очень быстрым. Если те же данные представлены красно-черным деревом, высота дерева сильно увеличится, что приведет к увеличению количества узлов обхода, увеличению количества обращений к диску и снижению производительности поиска.

Для B-дерева из n элементов высоты h и порядка m: На высоту дерева B влияет количество поддеревьев, содержащихся в каждом узле.Если количество дочерних узлов равно $\lceil\frac m2\rceil$ , то количество слоев наибольшее, что является худшим случаем, если количество дочерних узлов максимально равно m, количество слоев будет наименьшим, что является лучшим случаем. Так что есть

\log _m{(n + 1)} \leq h \leq \log _{\lceil\frac m2\rceil}{(\frac{n + 1}{2})} + 1

база $\lceil\frac m2\rceil$ Оно может быть очень большим, например, m может достигать нескольких тысяч, чтобы конечное значение h было как можно меньше, а высота дерева была относительно небольшой при условии определенного количества ключевых слов.

На практике каждый узел в B-дереве может содержать большое количество информации о ключевых словах и ветвях в соответствии с реальной ситуацией (но не может превышать размер блока диска. Согласно различным дискам, общий размер блока составляет около 1 КБ~). 4k); таким образом глубина дерева уменьшается, что означает, что при поиске элемента, пока несколько узлов считываются в память с внешнего диска, можно быстро получить доступ к искомым данным.

найти

Структуру узла можно определить как:

type BTNode struct {
  KeyNum   int       // 关键字个数，math.Ceil(m/2)-1 <= KeyNum < 阶数 m
  Parent   *BTNode   // 指向父节点的指针
  IsLeaf   bool      // 是否为叶子，叶子节点 children 为 nil
  Key      []int     // 关键字切片，长度为 KeyNum
  Children []*BTNode // 子节点指针切片，长度为 KeyNum+1
}

В качестве примера возьмем корневой узел приведенного выше дерева 2-3-4:

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

вставлять

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

Вставьте шаги:

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

Или возьмем приведенное выше дерево 2-3-4 (порядок m = 4) в качестве примера, вставляем элементы по очереди

Сначала вставьте 1, 2, 3, потому что количество ключевых слов не превышает m-1, поэтому вы можете напрямую вставить:

При вставке 4 количество ключевых слов узла достигает m, и его нужно разбить, здесь в качестве промежуточного слова можно выбрать 3 (или 2).После разбиения:

Продолжайте вставлять 5 и 7, соответствующие листовому узлу, где находится 4:

При вставке 8 его также необходимо разбить, переместить среднее слово 5 вверх к родительскому узлу, 4 становится левым поддеревом 5, а 7 8 становится правым поддеревом 5:

Последующие шаги аналогичны и не будут описываться по одному.

Удалить

Операция удаления относится к удалению указанного ключевого слова в узле B-дерева.

Удалить шаги:

Если текущее удаляемое ключевое слово находится на нелистовом узле N, то удаляемое ключевое слово перезаписывается последующим минимальным ключевым словом (или предшествующим максимальным ключевым словом), а затем удаляемое ключевое слово удаляется в поддереве. где находится последующее ключевое слово. Последующие ключевые слова должны располагаться на листовых узлах, и этот процесс аналогичен тому, как бинарное дерево поиска удаляет узлы. После удаления этого ключевого слова-преемника перейдите к шагу 2. Если исходное ключевое слово, которое нужно удалить, находится на листе, удалите ключевое слово и перейдите к шагу 2.
Количество ключевых слов этого узла (при условии, что M) больше или равно math.Ceil(m/2)-1, завершить операцию удаления, иначе перейти к шагу 3.
На данный момент количество ключевых слов в узле M меньше, чем math.Ceil(m/2)-1.
- Если количество ключевых слов соседних одноуровневых узлов (как левых, так и правых) больше, чем math.Ceil(m/2)-1, то выберите соседнее ключевое слово из родительского узла и переместите его вниз к M, а затем выберите соседнее ключевое слово. от родственного узла.Ключевое слово перемещается вверх к родительскому узлу, и операция удаления завершается;
- Если количество ключей смежных узлов одного уровня не превышает math.Ceil(m/2)-1, переместите ключ соседнего ключа в родительском узле на M и объедините M и его узлы одного уровня, чтобы сформировать новый узел. Два дочерних указателя ключа в исходном родительском узле становятся дочерними указателями, указывающими на новый узел. Затем указатель текущего узла указывает на родительский узел, повторите шаг 2.

Возьмите дерево 2-3-4 выше в качестве примера.

Порядок равен 4, а диапазон ключевых слов узла должен быть [1, 3], то есть math.Ceil(m/2)-1 = 1

удалить ключевое слово 2 или 8, не влияет на узел

Удалить ключевое слово 4, количество ключевых слов листового узла X становится равным 0, что меньше нижней границы диапазона, а количество ключевых слов двух соседних братьев слева и справа не больше 1, а узлы должны быть объединены.
- Первый шаг — переместить 5 родительского узла вниз к X.
- Второй шаг, объедините X и правого брата 7, чтобы сформировать новый узел, содержащий 5, 7
- На третьем шаге левый и правый дочерние указатели исходных 5 в родительском узле становятся одним и указывают на этот новый узел.

Здесь вы также можете перейти на 3 вниз на первом этапе, а затем объединиться с левым братом в узлы 1 и 3 на втором этапе.

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

Теперь попробуйте удалить нелистовой узел 5, замените 5 последующим наименьшим ключом 7, затем удалите листовой узел, где находится 7.
- В это время будет вызвана цепная реакция.Листовой узел, где находится 7, теперь пуст, а ключевое слово родственного узла не больше 1, которое необходимо объединить.
- Переместите ключевое слово 7 из родительского узла в исходный лист и объедините его с новым узлом, содержащим 3 и 7. Предполагая, что новым узлом является N, дочерний указатель родительского узла становится единицей и указывает на N
- Ключевое слово родительского узла теперь пусто, а ключевое слово родственного узла (дяди N) не больше 1, и его также необходимо объединить.
- Корневой узел берет ключевое слово 9 и перемещает его вниз к родительскому узлу N, объединяет родительский узел и узел-дядя N и генерирует новый узел, содержащий 9 и 15. Указатель дочернего узла корневого узла уменьшается на единицу. и левое поддерево указывает на этот новый узел.

Здесь демонстрируется операция удаления, и содержимое B-дерева закончено.

Динамическое отображение B-дерева:Ууууу, в это время Джейд А. Квота из США/~Карри Лакса/виз…

B+ Дерево (B+ - Дерево)

В+ деревоэто вариант на основе B-дерева с лучшей производительностью поиска

Разница между деревом B+ того же порядка m и деревом B:

Все нелистовые узлы, каждый узел имеет не более m ключевых слов, не менее $\lceil\frac m2\rceil$ ключевые слова (на одно больше, чем предел B-дерева), где каждое ключевое слово соответствует поддереву
Все нелистовые узлы можно рассматривать как часть индекса, узел содержит только самое большое (или самое маленькое) ключевое слово в корневом узле своего поддерева и не содержит указатель данных ключевого слова (дерево B содержит этот указатель)
Все листовые узлы содержат информацию обо всех ключевых словах и указатели на записи, содержащие эти ключевые слова, а сами листовые узлы связаны в порядке возрастания в соответствии с размером ключевых слов (и вся информация о ключевых словах дерева B разбросана по каждому узлу).

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

Деревья B+ также могут быть определены в другой форме:

Промежуточные узлы имеют не более m-1 ключевых слов и не менее $\lceil\frac m2\rceil-1$ ключевые слова, такие же, как B-дерево; Однако ключ нелистового узла является наибольшим ключом левого поддерева (или наименьшим ключом правого поддерева), что отличается от предыдущей ситуации.

Например, представление этого определения тех же данных в виде дерева B+ выглядит следующим образом:

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

Преимущество

Дерево B+ больше подходит для индекса файла и индекса базы данных операционной системы в практическом применении, чем дерево B.

Иноды дерева B+ могут хранить больше ключевых слов и меньше дисковых операций ввода-вывода.

Ключевым словом в базе данных может быть только информация об индексе столбца данных (например, индекс, созданный с помощью столбца идентификатора), а запись данных, на которую указывает индекс (строка данных, соответствующая определенному идентификатору), называетсяспутниковые данные, рекомендуется прочитать сообщение в блогеПростейшая реализация базы данныхиСтруктура данных и принцип алгоритма индекса MySQL

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

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

Например, предположим, что блок диска на диске может содержать 16 байт, ключ занимает 2 байта, а указатель спутниковых данных занимает 2 байта. Для B-дерева 9-го порядка узел содержит не более 8 ключевых слов (8*4 байта), то есть внутреннему узлу для хранения требуется 2 дисковых блока. Для дерева B+ внутренние узлы не содержат указателей на спутниковые данные, поэтому внутреннему узлу нужен только 1 дисковый блок. Когда внутренний узел необходимо прочитать в память, у B-дерева есть на одно время поиска блока диска больше, чем у B+ дерева.

Эффективность запросов дерева B+ более стабильна

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

Дерево B+ более удобно для операций запроса диапазона

Если вы ищете один элемент, процесс поиска в дереве B+ аналогичен процессу поиска в дереве B, за исключением того, что каждый поиск ведется от корня к листу.

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

вставлять

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

Например, вставив элемент 105 в дерево B+, указанное выше, поскольку 105 больше, чем максимальный ключ текущего поддерева 101, необходимо изменить граничный ключ родительского узла и узла прародителя:

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

Например, количество ключевых слов листового узла, только что вставленных в 105, достигает 4, и его необходимо разбить.Разбиение здесь немного отличается от B-дерева. Дерево B делится на три части в соответствии со средним узлом, затем средний узел перемещается вверх, а дерево B+ делится на две части, а затем к родительскому узлу добавляется самое большое ключевое слово левой половины узла.

На этом этапе родительский узел также необходимо разделить.

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

Удалить

Удаление дерева B+ аналогично удалению дерева B. Найдите ключевое слово, которое нужно удалить.Если это самое большое ключевое слово текущего поддерева, после удаления ключевого слова измените ключевое слово, соответствующее узлу-предку; самое большое ключевое слово текущего слова поддерева, удалить его напрямую;

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

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

Мы продолжаем удалять 7. В настоящее время количество ключевых слов в листовом узле меньше 1 и его необходимо скорректировать, а в родственном узле есть избыточные ключевые слова.Вы можете переместить 5 в текущий узел и изменить граничные ключевые слова родительский узел и прародительский узел.

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

Динамическое отображение дерева B+:Ууууу, в это время Джейд А. Квота из США/~Карри Лакса/виз…

B* дерево (B* - Дерево)

Дерево B* является вариантом дерева B+.На основе дерева B+ (все конечные узлы содержат информацию обо всех ключевых словах и указатели на записи, содержащие эти ключевые слова) дерево B* имеет еще два свойства:

Промежуточные узлы также добавляют указатели на братьев и сестер, то есть каждый слой узлов можно перемещать по горизонтали.
Дерево B* определяет, что количество ключевых слов, не являющихся конечными узлами, не менее $\lceil\frac {2m}3\rceil$ , т.е. минимальное использование блока 2/3, а не 1/2 дерева B+

Данные на рисунке ниже такие же, как данные предыдущего дерева B+, но структура ветвей отличается (поскольку диапазон ключей промежуточного узла становится [3, 4], что отличается от предыдущего дерева B+ [2, 4]). , а второй уровень Узлы также связаны указателями

Преимущество

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

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

Дерево B* имеет указатели на одноуровневые узлы, а функция передачи ключевых слов на одноуровневые узлы делает дерево B* менее разборным и увеличивает использование пространства узла.

Поскольку релевантное содержимое найдено не было, здесь не будет объясняться вставка и удаление деревьев B*.

Суммировать

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

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

Конечно, у B-деревьев есть и недостатки:

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

Тогда максимальная длина значения ключа не может быть изменена, пока база данных не будет полностью перестроена. Это приводит к тому, что многие системы баз данных усекают имена до 70 символов.

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

Reference

википедия - красно-черное дерево
Что такое B-дерево
Метод программирования: интервью и уроки алгоритмов