Вопрос
Хорошо, на скриншоте, прикрепленном ниже, показано дерево R. Он имеет R1 и R2 в корне. слева от R1 находится r3,r3,r5. Это почему? Я думал, что элементы слева от корневого элемента должны быть меньше. Если бы корневым элементом в корне был R6, то имело бы смысл поставить R3,R4,R5 слева. Насколько мне известно, B+ и B-деревья следуют этому правилу.
Также на листовых узлах, почему после R12 и тому подобное есть пустое место? Я в замешательстве.
B-дерево и R-дерево основаны на совершенно разных концепциях. У них мало общего: похожие имена и высокая n-арность (чтобы их можно было хранить на дисках с плохим временем произвольного доступа).
B-дерево хранит одномерные значения, которые упорядочены естественным образом. R-дерево хранит многомерные значения, которые нельзя упорядочить естественным образом. (Как вы собираетесь упорядочивать пары координат x/y?).
B-дерево хранит сами элементы, а R-дерево хранит координаты искусственно построенных ограничивающих рамок. Ri на изображении выше - это просто случайные метки - вы можете заменить их любыми именами, которые вам нравятся.
Связи в B-дереве и R-дереве означают совершенно разные отношения.
Если какой-то узел B-дерева хранит n значений, то он имеет n+1 указателей, которые расположены (семантически) между соседними значениями. Если, например, какой-то указатель находится между значениями 25 и 70, то он ведет к поддереву, в котором разрешено хранить элементы с 26 по 69. Таким образом, можно сказать, что связи в B-дереве означают в -между отношениями.
Если какой-то узел R-дерева хранит n координат ограничивающих рамок, то он также имеет n указателей на нижний уровень, по одному на каждую ограничивающую рамку. Если некоторый указатель принадлежит Ri, то он ведет к поддереву, содержащему все внутренние ограничивающие рамки относительно Ri. Это своего рода "содержащее" отношение.
Чтобы понять дальнейшую разницу между деревьями B и R, вы можете построить R-дерево, которое хранит одномерные числа (прямоугольники вырождаются в отрезки) и сравнить его с B-деревом.
Итак, чтобы ответить на ваш первый вопрос: R1 не меньше, чем R3, R4 или R5. Это просто метки соответствующих прямоугольников. Вместо этого R3, R4 и R5 являются частью R1.
Что касается того, почему есть пустое место - это зависит от алгоритма, используемого для построения дерева. Разные алгоритмы и разные порядки вставки/удаления могут привести к разным деревьям, содержащим один и тот же набор элементов. (То же самое верно и для B-деревьев.)
Упорядочиваются только одномерные данные.
Идея балансировки и разделения R-дерева аналогична B-дереву; аналогично R-дерево обеспечивает минимальное заполнение страницы и т. д. Концепция страниц также аналогична.
Но в то время как B-дерево использует линейный порядок узлов, R-дерево использует иерархию ограничивающего объема, а не линейный порядок, поскольку многомерные данные не упорядочены. В R-дереве нет "левого" или "правого".
Перевод вопроса и ответов сообщества Stack Overflow, лицензия CC BY-SA. Оригинал на Stack Overflow.
