Не имея ссылки на видео, похоже, что они используют нестандартное определение термина order , что является причиной путаницы.
Стандартное определение порядка для дерева будет максимальным коэффициентом ветвления, то есть максимальным числом дочерних элементов, которое может иметь узел. Таким образом, в этом определении речь идет не о минимуме , а о максимуме , и речь идет не о количестве ключей , а о количестве children .
Определение видео будет означать, что максимальное количество ключей всегда будет четным числом, хотя в действительности такого требования не существует. У деревьев B + вполне может быть максимальный коэффициент ветвления, который является четным, что делает максимальное количество ключей нечетным.
Используя стандартное определение термина order , мы специально имеем для деревьев B + эти ограничения:
- Его внутренние узлы имеют не более m дочерних элементов. Это означает, что они имеют не более m - 1 ключей.
- Его внутренние узлы имеют по крайней мере m / 2 (округлено вверх) дочерних элементов, за исключением root:
- Если root не является листом, у него может быть всего 2 дочерних элемента.
- В его листьях содержатся фактические значения данных.
Вот пример дерева B + с порядком 4 (стандартное определение), которое соответствует дереву B +, где количество ключей должно быть от 1 до 3, что не соответствует определению видео:
Как видите, у узла может быть максимум 4 дочерних элемента и максимум 3 ключа. В вашем определении, где 2m представляет максимальное количество ключей, порядок на самом деле составляет 2m + 1 . Таким образом, вы запрашиваете примеры деревьев B + порядка 3 и 5, используя стандартное определение order .
Вот пример порядка 3 - самый низкий возможный порядок для деревьев B + - это означает, что количество ключей должно быть 1 или 2 в каждом узле:
