В чем разница между KD-деревом и R-деревом?

R-деревья и kd-деревья основаны на схожих идеях (разделение пространства на основе областей, выровненных по осям), но ключевые отличия заключаются в следующем:

• Узлы в kd-деревьях представляют собой разделяющие плоскости, тогда как узлы в R-деревьях представляют собой ограничивающие рамки.
• kd-деревья разбивают все пространство на области, тогда как R-деревья разбивают только подмножество пространства, содержащее точки интереса.
• kd-деревья представляют собой непересекающиеся разделы (точки принадлежат только одному региону), тогда как регионы в R-дереве могут перекрываться.

(Существует множество подобных древовидных структур для разбиения пространства: деревья квадрантов, BSP-деревья, R*-деревья и т.д. и т.п.)

На самом деле они совсем другие. Они служат одинаковой цели (региональные запросы к пространственным данным), и оба они являются деревьями (и оба принадлежат к семейству индексов иерархии ограничивающих томов), но это почти все, что у них общего.

• R-деревья сбалансированы, а k-d-деревья — нет (если только они не загружаются массово). Вот почему R-деревья предпочтительнее для изменения данных, поскольку k-d-деревья могут нуждаться в перестроении для повторной оптимизации.
• R-Tree ориентированы на диски. На самом деле они организуют данные в областях, которые напрямую соотносятся с представлением на диске. Это делает их более полезными в реальных базах данных и при работе с нехваткой памяти. k-d-деревья ориентированы на память, и их нетривиально помещать в дисковые страницы.
• kd-деревья элегантны при массовой загрузке (престижность SingleNegationElimination за указание на это), в то время как R-деревья лучше подходят для изменения данных (хотя они выигрывают от массовой загрузки при использовании со статическими данными). .
• R-деревья не охватывают все пространство данных. Пустые области могут быть обнаружены. k-d-деревья всегда покрывают все пространство.
• k-d-деревья бинарно разбивают пространство данных, R-деревья разбивают данные на прямоугольники. Бинарные расщепления явно не пересекаются; в то время как прямоугольники R-дерева могут перекрываться (что на самом деле иногда хорошо, хотя и пытаются минимизировать перекрытие)
• k-d-деревья намного проще реализовать в памяти, что на самом деле является их ключевым преимуществом.
• R-деревья могут хранить прямоугольники и многоугольники, k-d-деревья хранят только точечные векторы (поскольку для многоугольников требуется перекрытие).
• R-деревья поставляются с различными стратегиями оптимизации, различными разбиениями, массовыми загрузчиками, стратегиями вставки и повторной вставки и т. д.
• k-d-деревья используют одномерное расстояние до разделяющей гиперплоскости в качестве границы; R-деревья используют d-мерное минимальное расстояние до ограничивающего гиперпрямоугольника для ограничения (они также могут использовать максимальное расстояние для некоторых запросов на подсчет, чтобы отфильтровать истинные положительные результаты).
• k-d-деревья поддерживают квадратное евклидово расстояние и нормы Минковского, в то время как R-деревья, как было показано, также поддерживают геодезическое расстояние (для поиска близких точек в геоданных).

Основное различие между двумя, не упомянутыми в этом ответе, заключается в том, что KD-деревья эффективны только в ситуациях массовой загрузки. После построения изменить или перебалансировать KD-дерево нетривиально. R-деревья от этого не страдают.