Я довольно хорошо знаком с B Tree, в основном мне нужно, чтобы базы данных хорошо питались электричеством, кондиционерами и жестким диском. Я ассоциируюсь с двойным (дублирующим [т.е., ey]?) Связанным списком.
Сегодня один из разработчиков за обедом упомянул R-дерево.
Я вскочил на Википедию и начал читать. Это звучало ужасно, как высокое дерево B. К сожалению, отсутствие глубоких математических знаний затрудняет понимание того, о чем говорят некоторые из моих коллег.
Я надеялся, что кто-нибудь сможет прояснить несколько различий между B-деревом и R-деревом. Вероятно, я все равно буду спрашивать ребят, но нет никакой гарантии, что они ответят на мой вопрос. Скорее всего, они начнут бродить о Боге знает что. , ,
Ответы:
R-дерево можно рассматривать как обобщение b-дерева. Когда b-дерево обеспечивает O (log n) доступ через «ограниченный диапазон» ключей, которые оно содержит, R Tree обеспечивает O (log n) доступ через «K-мерную область» ключей, которые оно содержит.
Если вы хотите сопоставить почтовые индексы с названиями округов, вы можете использовать B-Tree, так как вы можете спросить его: «Какие уезды имеют почтовые индексы между 60000 и 61000?» Тем не менее, B-дерево было бы плохо приспособлено для сопоставления координат GPS с названиями округов для запросов типа «Каковы все округа в пределах 100 миль от Чикаго?», Так как его ключи располагаются только в одном измерении. R-Tree разбивает свои ключи в соответствии с перекрывающимися ограничивающими прямоугольниками, и поэтому это естественный способ хранения ключей, когда вам нужно выполнить запрос по нескольким измерениям.
источник
Большинство древовидных структур можно свести к какой-либо форме связанного списка, если вы игнорируете, как строится список (в частности, как элементы добавляются и удаляются и как перебалансируются узлы, если это применимо). По сути, это алгоритм вставки / удаления / поиска, который отличает одну структуру данных от другой.
Узлы в R-дереве обычно содержат ограничивающий прямоугольник, который позволяет вам эффективно индексировать местоположения, как вам может понадобиться, если вы хотите искать записи «рядом» с определенным местоположением. Элементы в B-дереве имеют более простой порядок; Вы можете напрямую сравнить, является ли что-то больше или равно другому элементу. В R-дереве цель каждой записи - определить, какие элементы содержатся в ограничительной рамке.
B-дерево позволяет эффективно искать элементы, которые можно заказать во вторичной памяти (например, на жестком диске), а R-дерево позволяет эффективно искать элементы, которые находятся «в» или «около» определенной точки или ограничительной рамки, а также во вторичной памяти.
источник