Почему R -tree неупорядочен? Тем не менее, говорят, что он соблюдает правила B-дерева

Question

ОК, на скриншоте, приведенном ниже, находится дерево R. Он имеет R1 и R2 в корне. слева от R1 есть r3, r3, r5. Почему это? Я думал, что элементы слева от корневого элемента должны быть меньше. Если корневым элементом в корне было R6, то было бы целесообразно положить R3, R4, R5 слева. Насколько я знаю, B + и B-деревья следуют этому правилу.

Также на узлах листа, почему существует пустое пространство после R12 и подобных? Я смущен.

Answer 1

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

1. B-tree хранит одномерные значения, которые естественно заказываются. R-дерево хранит многомерные значения, которые нельзя упорядочить естественным образом. (Как вы собираетесь заказать пар x/y координаты?).

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

3. Соединения в B-дереве и R-дереве означают совершенно разные отношения.

   Если некоторые В-дерево узел хранит п значения, то она имеет п +1 указателей, которые расположены (семантический) между соседних значениями. Если, например, некоторый указатель находится между значениями 25 и 70, то он приводит к поддереву, которому разрешено хранить элементы от 26 до 69. Таким образом, можно сказать, что соединения в B-дереве означают между ними отношений.

   Если некоторые R-дерево узел хранит п ограничивающих прямоугольников координаты, то он также имеет п указателей на более низкий уровень, по одному в каждую ограничивающей рамку. Если какой-либо указатель принадлежит R _i, то он приводит к поддереву, которое содержит все внутренние ограничивающие поля относительно R _i. Это своего рода «содержащее» отношение.

Чтобы понять дальнейшее различие между B и R деревьев, вы можете построить R-дерево, которое хранит одиночные размерные числа (прямоугольники выродилась сегментов линии) и сравнить ее с B-дерева.

Итак, чтобы ответить на ваш первый вопрос: R1 не меньше R3, R4 или R5. Это только метки соответствующих прямоугольников. Вместо этого R3, R4 и R5 являются частью R1.

Из-за чего существует пустое пространство - это зависит от алгоритма, используемого для построения дерева. Различные алгоритмы и разные порядки вложений/делеций могут заканчиваться разными деревьями, содержащими один и тот же набор элементов. (То же самое верно для B-деревьев.)

Answer 2

Заказываются только одномерные данные.

Идея балансировка и расщепления из R-дерева похоже на B-дерево; R-дерево аналогичным образом обеспечивает минимальное заполнение страницы и т. д. - тоже похоже на концепцию страниц.

Но в то время как B-дерево использует порядковый номер линейных узлов, R-дерево использует иерархию ограничивающих томов, а не линейный порядок, поскольку многомерные данные не упорядочены. В R-дереве нет «левого» или «правого».