Что такое разветвление в R-Tree?
У меня есть сомнения по поводу структуры данных R-Tree. Что такое разветвление в R-Tree. Это максимальное количество записей?
Как мы можем определить минимальное и максимальное количество записей в R-Tree? Скажем, если у меня есть 10000 баллов и мой размер страницы я 8kb.
Спасибо
2 ответа
Разветвление в любом дереве - это число указателей на дочерние узлы в узле.
У разных деревьев разное разветвление.
Бинарное дерево имеет разветвление 2.
У B-дерева есть разветвление B со всеми узлами, кроме листьев, имеющих от B/2 до B дочерних элементов. Внешняя (на диске) реализация часто ослабляет ограничение минимального количества дочерних элементов для сохранения некоторых обновлений.
В базах данных часто используются B-деревья или их вариант, называемый B+-деревьями, так что каждый узел имеет размер 1 страницы, а разветвление определяется количеством ключей сортировки и указателей, которые помещаются в это пространство.
R-дерево - это дерево поиска, где индексы являются многомерными интервалами. Они могут перекрываться. Это может иметь какой-либо разветвления. Обычно это число от 2 до количества измерений (4 для 2-мерных, 8 для 3-мерных и т. Д.). Но он также может иметь более высокую степень разветвления, и его организация, подобная B-дереву, безусловно возможна
Как мы можем определить минимальное и максимальное количество записей в R-Tree? Допустим, если у меня есть 10000 баллов и размер моей страницы составляет 8 КБ.
Размер узла дерева не обязательно должен соответствовать размеру страницы. Если это так (обычно используется для внешних, т.е. на диске, реализаций), вам все равно нужно знать, насколько велик ключ сортировки и насколько велик указатель. R-дереву нужно 2 значения координат, минимальное и максимальное, для каждого измерения. Таким образом, двумерное R-дерево с координатами двойной точности (общий случай, возникающий в приложениях отображения) будет иметь четыре 64-битных значения, описывающих прямоугольник, и дочерний указатель, для которого внешняя реализация, вероятно, также хочет использовать 64-битные значения. Это 20 B на ребенка, и вы можете сжать 409 из них на странице 8 КиБ. Количество баллов не имеет значения. Размерность и точность системы координат делает.
В памяти деревья с низким разветвлением более эффективны, потому что, хотя они глубже, им нужно меньше сравнений на поиск. Однако на диске (в базах данных) медленная операция чтения и, поскольку это может быть сделано только в блоках, быстрее сократить количество узлов, так как каждый узел заполняет весь блок и имеет соответственно более высокий разветвление.
"Разветвление" относится к числу указателей на узел, которое имеет R-Tree.