Расщепление узла в б + дереве
Я пытаюсь выяснить, что именно происходит при переполнении узла. информация: в моем дереве b + есть 4 указателя на блок и 3 раздела данных. проблема: я понял, что когда происходит переполнение, мы разбиваем на 2 узла в моем случае, каждый из которых имеет 2 ключа, и вставляем родительскому узлу среднее значение, не стирая с сына (в отличие от дерева b).
Однако я попал в ситуацию:
|21|30|50|
|10|20|-| |21|22|25| |30|40|-| |50|60|80|
и я хочу вставить ключ 23 сначала я разделить |21|22|25| в: |21|22|-| и |23|25|-| Теперь мне нужно вставить ключ 23 в родительский |21|30|50| ведьма вызывает еще один раскол. |21|23|-| и |30|50|-| но где указатель до 30 указывает на? Возможно ли, что и этот указатель, и один после 23 указывают на |23|25|-|?
4 ответа
При вставке 23:
- как вы сказали, 21|22|-| и |23|25|-| созданы
- 2 узла требуют родителя
- родительский узел создается в корневом узле: |21|23|30|50|
- корень имеет слишком много элементов сейчас
- разделить корень на 2 узла |21|23|- и |30|50|-
- добавить нового родителя для 2 новых узлов (который является новым корнем дерева)
По сути, эта вставка увеличит глубину дерева на 1
Вот как указатели должны быть обработаны. это ваше дерево B+ перед вставкой. (для облегчения видения указатели используются некоторые отступы)
[21 30 50]
/ \ \ \
[10|20|-] => [21|22|25] => [30|40|-] => [50|60|80]
После вставки 23 у вас будет 2 узла. Важно знать, что разделение слева всегда должно быть одним и тем же экземпляром, а разделение справа должно быть новым узлом. это сделает обработку указателей несколько проще.
Так что расколы должны выглядеть следующим образом.
old fresh
[21|22|-] => [23|25|-]
поскольку левый узел - это тот же экземпляр, ключ 21 В корне есть правильный правильный указатель. Вот как выглядят узлы до расщепления корня и после расщепления листа. мы находимся в середине процесса.
[21 30 50]
/ \ \ \
[10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]
только новый предмет с ключом 23 следует добавить рядом с 21 в корне. так как корень не имеет места, он также будет разделен. средний ключ - 23 (первый элемент правого разделения).
[21 30] [ 50 ]
/ \ \ * \
[10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]
Поскольку корень разделен, мы должны добавить наш средний ключ к левому или правому разделению и найти новый средний ключ для продвижения. обратите внимание на нулевой указатель при разделении справа. поскольку этот узел свежий, он должен быть вскоре инициализирован!
(root был разделен от правильного, что означает, что в правом узле меньше элементов лежит на случайное количество элементов. Но в общем случае не имеет значения, какой способ разделения.)
наш средний ключ был 23. так что давайте добавим 23.
[21 23 30] [ 50 ]
/ \ \ \ * \
[10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]
Хорошо! Если бы здесь не было разделения, наша вставка была бы закончена к настоящему времени. но поскольку на этом уровне существует раскол, мы должны найти новый средний ключ для продвижения. Также не забудьте нулевой указатель для свежего узла.
(В случае разделения листов, вы должны хранить значения ключей на листьях и продвигать копию среднего ключа, но в случае разделения внутренних узлов вы можете безопасно перемещать и продвигать ключи вверх.)
здесь новый средний ключ 30. давайте вытолкнем его из левого узла.
30
\
[30|40|-]
(Важно, как выбрать средний ключ. Всегда узел, который получает средний ключ из нижних разбиений, должен отбрасывать один элемент для нового среднего ключа. Если этот узел является левым узлом, отбросить последний элемент из него, в противном случае отбросить первый элемент.)
[21 23] 30 [ 50 ]
/ \ \ \ * \
[10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]
Обратите внимание, что 30 не находится ни в одном из разделений. это наш средний ключ, с которым мы должны справиться. Всегда ставьте правый узел среднего ключа слева от свежего узла.
[21 23] 30 [50]
/ \ \ * / \
[10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]
Тогда правый указатель средней клавиши будет указывать на свежий узел в правом разделении. наконец, продвигается средний ключ, создается новый корень с левым левым и правым правым разделением и ключ от среднего ключа.
[ 30 ]
/ \
[21 23] [50]
/ \ \ / \
[10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]
Congrats! Вы сделали вставку. на бумаге это может выглядеть легко, но я должен признать, что это немного сложнее при кодировании.
Есть несколько способов представить эти key-node предметы в памяти. мой подход к каждому key-node пункт имеет правый указатель с ключом. поэтому каждый внутренний узел будет иметь массив key-node s. таким образом, ключи и указатели узлов всегда хранятся вместе. Самый левый дочерний элемент обрабатывается отдельным левым указателем, этот указатель сохраняется на каждом внутреннем узле и никогда не является нулевым (после завершения операций).
В дереве B+ листовые и нелистовые узлы имеют разные структуры. Благодаря этому различаются и их механизмы перелива. То, что вы говорите, верно для переполнения листовых узлов (это делается без стирания родительского ключа у сына). Но когда нелистовые узлы переполняются и разделяются, дочерний узел не сохраняет родительский ключ (родительский ключ стирается из дочернего).
Из того, что меня учили, вполне нормально, что последний узел имеет один узел меньше n/2. Итак, в вашем примере верхние узлы станут:
|23|
/ \
|21|22|-| |25|-|-|
Я думаю, что это имеет смысл. Если вы думаете об этом, у вас есть 5 оставленных узлов, поэтому вам нужно 5 указателей с верхнего уровня. Такое расположение является единственным способом, при котором вы можете иметь 5 указателей, все другие комбинации будут либо переполнять узел, либо создавать дополнительные указатели.
Если бы узлы были |21|22|-| и |23|25|-|, тогда корневым узлом будет |23|-|-|. Тогда не имеет смысла иметь 23 в правом узле, потому что все, что находится в правом узле, должно быть равно или больше 23 в любом случае!
Проблема, которую вы должны понять, происходит из-за плохой модели представления, которую вы используете. У вас должно быть одно значение данных, связанное с указателем, и инвариант, что значение данных является наименьшим значением в поддереве, на которое ссылается указатель.
Так вот как вы должны представлять узел b-дерева перед вставкой.
10|21|30|50| <--- root node
10|20| 21|22|25| 30|40| 50|60|80| <--- leaf nodes
В этом представлении указатель после значения 10 в корневом узле указывает на конечный узел с первым значением 10 и т. Д.
Когда вы вставляете 23, он вставляется в листовой узел с первым значением 21. Это приводит к следующему дереву и не требует разделения.
10|21|30|50| <--- root node
10|20| 21|22|23|25| 30|40| 50|60|80| <--- leaf nodes
При вставке 24, который производит эффект, который вы описали, вы получите следующее
10|30| <--- new root node
10|21|24| 30|50| <--- intermediate nodes
10|20| 21|22|23| 24|25| 30|40| 50|60|80| <--- leaf nodes
Как видите, двусмысленности больше нет. Конечный узел был разделен, а пара ключевых указателей 24| должен был быть вставлен в корневой узел. Так как это было полно, это должно было быть разделено. Теперь, когда есть 5 значений, вы получаете один узел с 3 значениями и один узел с 2. Вы можете свободно выбирать, получают ли три значения левый узел или правый узел. Важно то, что основной инвариант сохраняется. Каждое значение ключа в узле является наименьшим элементом в поддереве, на которое ссылается связанный с ним указатель. Необходимо было добавить новый корневой узел, и его указатель значения ключа теперь должен быть очевидным. Нет двусмысленности.
Это также делает очевидным, что многие стратегии оптимизации возможны. Вместо разделения корневого узла, мы могли бы переместить значение 21 в левый конечный узел, который не был заполнен. Тот, который имеет первое значение 10. Это устраняет необходимость разделения корневого узла и сохраняет высоту b-дерева неизменной и обеспечивает лучшее заполнение b-дерева. Таким образом, вы минимизируете пространство и время поиска. Но это означает, что можно эффективно проверить, возможна ли боковая балансировка. Изменение значения ключа в корневом узле все еще необходимо. и т.п.
Как видите, значение 10 в вашем b-дереве на самом деле не требуется ни в одном из конечных узлов, и оно часто не указывается в представлении b-дерева (т. Е. Википедии), но это может сбить с толку и, возможно, послужило причиной того, что вы это сделали.:)