Преимущества R-деревьев по сравнению с геохешами

18

Геошаши широко используются в таких продуктах, как: Lucene, mongodb и т. Д., И стали одной из важнейших технологий современности.

Заменили ли геохеши старые добрые R-деревья или у R-деревьев есть какие-то преимущества по сравнению с геохашами?

Джаннат Арора
источник

Ответы:

11

Geohash - это очень простой и эффективный способ индексации пространственных объектов, особенно точечных объектов. Линейные и многоугольные объекты немного сложнее проиндексировать, но это можно сделать. Geohash - это статическая иерархическая сетка фиксированного размера, наложенная поверх поверхности земли. Ячейки сетки одного и того же иерархического уровня не перекрываются. R-Tree - это динамическая сетка, расположение и размер ячейки которой меняются в зависимости от индексируемых объектов. Индексы R-Tree имеют ограничивающие рамки и ячейки, которые меняются каждый раз при вставке и обновлении данных. Geohash в основном используется для индексирования точечных объектов, и ячейки не меняются при каждой вставке и обновлении данных. Ячейки Geohash не адаптируются к таким функциям, как R-дерево.

Некоторые из преимуществ geohash (по сравнению с r-tree) могут быть:

  • легкая реализация
  • нет снижения производительности с ростом числа функций
  • поиски близости (частично верно)

Некоторые из недостатков geohash (по сравнению с r-tree) могут быть:

  • произвольная точность сетки
  • сложнее индексировать (и запрашивать) линейные и полигональные объекты
  • размер индекса может быть большим с некоторыми методами индексации линий и полигонов
  • согласно спецификациям, он может использоваться только с системой координат долгота / широта, хотя тот же метод может быть применен и к другим системам координат

Те продукты (базы данных), которые вы упомянули, используют geohash, потому что geohash в основном используется для индексации точек, и существует множество приложений, которые нуждаются в такой возможности. Линии и полигоны используются не так часто (за исключением, конечно, приложений ГИС), так что зачем им это? Другая причина, конечно же, простота реализации. Geohash преобразует двумерную координату в одномерное значение. Это называется уменьшением размеров. Одномерное значение легко индексируется стандартным b-деревом, которое в основном используется в этих продуктах.

Я должен отметить, что существуют алгоритмы, аналогичные geohash, но большинство из них являются проприетарными и требуют лицензирования. Geohash находится в свободном доступе. Это может быть также причиной такого широкого использования в последние годы.

Вероятно, есть и другие преимущества и недостатки, но это первое, что приходит мне в голову. Я надеюсь, что мое объяснение немного поможет.

Марио Милер
источник
я не понял, почему геохэш дает произвольную точность сетки. Можете ли вы объяснить с примером. Я буду благодарен вам за то же самое.
Джаннат Арора
1
Geohash преобразует долготу и широту в одномерную строку. Длина этой строки напрямую связана с преобразованной точностью координаты. Пожалуйста, посмотрите на этот unterbahn.com/2009/11/… . Вы можете видеть, как длина строки геохеша связана с точностью. По сути, геохэш преобразует точку в область многоугольника (одна сетка геохэш). Размер этой области многоугольника зависит от длины строки геохеша и от того, какую широту вы рассчитываете геохэш.
Марио Милер