В B-деревьях, какой элемент продвигается при расщеплении узла - PullRequest
Новая
       6

В B-деревьях, какой элемент продвигается при расщеплении узла

3 голосов
/ 04 апреля 2010

Допустим, существует B-дерево порядка 8. Это означает, что оно может иметь 8 указателей и 7 элементов. Скажем, буквы от A до G хранятся в этом B-дереве. Так что это B-дерево - это всего лишь один узел, содержащий 7 элементов.

Затем вы пытаетесь вставить J в дерево. Там нет места, поэтому вы должны разделить узел и создать новый корневой узел. Какой элемент повышен до корневого узла?

1 Ответ

1 голос
/ 04 апреля 2010

Когда вы хотите вставить новый элемент в полный узел (с ключами 2*t - 1)

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