предисловие
Запущена новая серия «Глядя на картинки, чтобы легко понять структуры данных и алгоритмы», в основном с использованием изображений для описания общих структур данных и алгоритмов, которые легко читать и понимать. В эту серию входят десятки куч, очередей, списков, деревьев, графов, сортировки и так далее.
B-дерево
B-дерево — это сбалансированное дерево поиска, которое обычно понимается как сбалансированное дерево поиска с несколькими путями, также известное как B-дерево и B_tree. Это самобалансирующаяся древовидная структура данных, которая может искать, вставлять и удалять сохраненные данные с временной сложностью O(log n). B-деревья обычно используются в системах хранения, таких как базы данных или файловые системы.
Особенности B-дерева
- B-дерево может определять значение m как заданный диапазон, то есть m-образное (порядковое) B-дерево.
- Каждый узел имеет не более m потомков.
- Каждый узел имеет как минимум ceil(m/2) дочерних узлов, за исключением корневого и листового узлов.
- Для корневого узла количество поддеревьев находится в диапазоне [2,m], а количество значений в узле находится в диапазоне [1,m-1].
- Для некорневых узлов количество значений в узле находится в диапазоне [ceil(m/2)-1,m-1].
- Корневой узел (нелистовой узел) имеет как минимум двух дочерних элементов.
- Нелистовой узел с k дочерними элементами содержит k-1 значений.
- Все листовые узлы находятся на одном уровне.
- Значения внутри узла располагаются в порядке возрастания.
- Несколько значений родительского узла делятся на несколько поддеревьев в качестве значений разделения, левое поддерево меньше соответствующего значения разделения, а соответствующее значение разделения меньше правого поддерева.
Ниже приведено B-дерево четвертого порядка,
вставлять
Предположим теперь, чтобы построить B-дерево четвертого порядка, начните вставлять «A» непосредственно в качестве корневого узла,
Вставить «В», крупнее «А», поставить справа,
Вставьте «С», чтобы до конца,
Продолжайте вставлять "D", и непосредственно добавленный результат показан на рисунке ниже. В это время емкость хранилища узла превышена. Для B-дерева четвертого порядка каждый узел может хранить до 3 значений , В это время необходимо выполнить операцию разделения.
Операция разделения состоит в том, чтобы сначала выбрать медианное значение узла, которое нужно разделить, которое здесь равно «B», а затем поместить медианное значение «B» в родительский узел, поскольку здесь нет родительского узла, а затем напрямую создать узел. новый родительский узел для хранения «B»», причем те значения, которые изначально были меньше «B», брались за левое поддерево, а те, что изначально больше «B», брались за правое поддерево.
Продолжайте вставлять «E», «E» больше, чем «B», перейдите к правому дочернему узлу,
Сравните с «C» и «D» соответственно, если они больше их, поставьте их крайним справа,
Вставьте «F», «F» больше, чем «B», перейдите к правому поддереву,
«F» сравнивается с «C», «D» и «E» соответственно, и если он больше их, он помещается крайним справа, и в это время запускается операция разделения.
Выберите срединное значение "D" узла, который нужно разделить, а затем поместите срединное значение "D" в родительский узел. "B" в родительском узле меньше, чем "D", поэтому он помещается справа из "B", а исходное значение меньше, чем "D". Эти значения используются в качестве левого поддерева, а те значения, которые изначально были больше "D", используются в качестве правого поддерева.
Продолжайте вставлять «М», результат:
Вставьте «L», больше, чем «B» и «D», в правое поддерево,
«L» больше, чем «E», а «F» меньше, чем «M», поэтому он помещается в третью позицию, и в это время запускается операция разделения.
Выберите медиану "F" узла, который нужно разделить, а затем поместите медиану "F" в родительский узел. "B" и "D" в родительском узле меньше, чем "F", поэтому они размещены на крайний правый, в то время как исходное значение меньше, чем "F". Эти значения F берутся как левое поддерево, а те, которые изначально больше "F", берутся как правое поддерево.
Вставьте «К», результат:
Вставьте «J», больше, чем «B», «D» и «F», перейдите к правому поддереву,
«J» меньше, чем «K», «L» и «M», поэтому он помещается в первую позицию, и в это время запускается операция разделения.
Выберите медиану "K" узла, который нужно разделить, а затем поместите медиану "K" в родительский узел. "B", "D" и "F" в родительском узле все меньше, чем "K", поэтому они помещаются в крайнее правое положение, и те значения, которые изначально меньше «K», принимаются за левое поддерево, а те, которые изначально больше «K», принимаются за правое поддерево. В это время родительский узел также запускает операцию разделения,
Выберите медианное значение "D" узла, который необходимо разделить, а затем поместите медианное значение "D" в родительский узел. Поскольку родительского узла нет, создайте новый родительский узел непосредственно для хранения "D", а исходный значение меньше "D" Эти значения берутся как левое поддерево, а те, что изначально больше "D", берутся как правое поддерево.
Вставьте «I», больше «D», перейдите к правому поддереву,
Правое поддерево не является листовым узлом, поэтому продолжайте движение вниз. В это время «I» больше, чем «F», и меньше, чем «K», поэтому перейдите ко второй ветви,
«I» меньше, чем «J», поэтому ставьте его слева,
Аналогично вставляем "H", результат такой,
Вставьте «G», перейдите в левое поддерево,
ветвь к середине,
запустить операцию разделения,
Выберите медиану «H» узла, который нужно разделить, а затем поместите медиану «H» в родительский узел, «H» больше, чем «F» в родительском узле, и меньше, чем «K», поэтому он помещается посередине, а исходное меньше "тех значений H" берутся за левое поддерево, а исходное больше "H" - за правое поддерево.
Таким образом, ядром операции вставки является операция разделения. Ситуация без разделения относительно проста, просто вставьте его напрямую, если мощность узла превышена после вставки, эта емкость может быть настроена заранее, и требуется операция разделения.Следует отметить, что разделение может привести к родительский узел, чтобы продолжить разделение.
найти
Поиск в B-дереве относительно прост, процесс поиска чем-то похож на бинарное дерево поиска: поиск начинается с корневого узла, находит соответствующую ветвь по значению сравнения и продолжает поиск в поддереве.
Например, чтобы найти «I», «I» больше, чем «D», перейдите к правому поддереву,
«I» сравнивается с внутренним значением узла, которое больше «F», «H» и меньше «K», и переходит в третью ветвь,
Сравните значения внутри узлов одно за другим, чтобы найти «Я».
------------- Рекомендуем прочитать ------------
Зачем писать «Анализ проектирования ядра Tomcat»
Резюме моей статьи за 2017 год — машинное обучение
Резюме моих статей за 2017 год — Java и промежуточное ПО
Резюме моих статей 2017 года — глубокое обучение
Краткое изложение моих статей за 2017 год — исходный код JDK
Резюме моих статей 2017 года — обработка естественного языка
Резюме моих статей 2017 года — Java Concurrency
Поговори со мной, задай мне вопросы:
Добро пожаловать, чтобы следовать: