Avantages des arbres R par rapport aux géohashes

18

Les géohash sont largement utilisés dans des produits tels que: Lucene, mongodb, etc. et sont devenus l'une des technologies les plus importantes de nos jours.

Les Geohashes ont-ils remplacé les bons vieux R-arbres ou les R-arbres ont-ils des avantages par rapport aux Geohashes?

Jannat Arora
la source

Réponses:

11

Les géohash sont un moyen très simple et efficace d'indexer des entités spatiales, en particulier des entités ponctuelles. Les entités linéaires et polygonales sont un peu plus difficiles à indexer, mais cela peut être fait. Geohash est une grille statique de taille fixe hiérarchique, superposée sur la surface de la terre. Les cellules de la grille du même niveau hiérarchique ne se chevauchent pas. R-Tree est une grille dynamique dont l'emplacement et la taille des cellules changent en fonction des fonctionnalités qu'ils indexent. Les index R-Tree comportent des cadres et des cellules de délimitation qui changent chaque fois que vous insérez et mettez à jour des données. Geohash est principalement utilisé pour l'indexation des entités ponctuelles et les cellules ne changent pas à chaque insertion et mise à jour des données. Les cellules Geohash n'adoptent pas les fonctionnalités comme avec R-tree.

Certains des avantages de geohash (par rapport à r-tree) pourraient être:

  • mise en œuvre facile
  • aucune dégradation des performances avec un nombre croissant de fonctionnalités
  • recherches de proximité (partiellement vrai)

Certains des inconvénients du geohash (par rapport à r-tree) pourraient être:

  • précision arbitraire de la grille
  • plus difficile à indexer (et à interroger) les entités linéaires et polygonales
  • la taille de l'index peut être grande avec certaines méthodes d'indexation de lignes et de polygones
  • selon les spécifications, il ne peut être utilisé qu'avec le système de coordonnées longitude / latitude, bien que la même méthode puisse être appliquée à d'autres systèmes de coordonnées

Les produits (bases de données) que vous avez mentionnés utilisent geohash car geohash est principalement utilisé pour l'indexation de points et de nombreuses applications ont besoin d'une telle fonctionnalité. Les lignes et les polygones ne sont pas souvent utilisés (sauf pour les applications SIG bien sûr), alors pourquoi s'en soucier. Une autre raison est bien sûr la facilité de mise en œuvre. Geohash convertit les coordonnées bidimensionnelles en valeur unidimensionnelle. C'est ce qu'on appelle la réduction dimensionnelle. La valeur unidimensionnelle est facile à indexer par l'arbre b standard qui est principalement utilisé dans ces produits.

Je dois mentionner qu'il existe des algorithmes similaires à geohash mais la plupart d'entre eux sont propriétaires et nécessitent une licence. Geohash est dans le domaine public. Cela pourrait également être la raison d'une utilisation aussi importante ces dernières années.

Il y a probablement d'autres avantages et inconvénients, mais ce sont les premiers qui me viennent à l'esprit. J'espère que mon explication aide un peu.

Mario Miler
la source
je n'ai pas compris pourquoi les géohashes donnent une précision arbitraire de la grille. Pouvez-vous s'il vous plaît expliquer avec un exemple. Je vous en serai reconnaissant.
Jannat Arora
1
Geohash convertit les coordonnées de longitude et de latitude en chaîne unidimensionnelle. La longueur de cette chaîne est directement liée à la précision convertie des coordonnées. Veuillez consulter ce unterbahn.com/2009/11/… . Vous pouvez voir comment la longueur d'une chaîne geohash est liée à la précision. Fondamentalement, le géohach convertit le point en une zone de polygone (une grille de géohach). La taille de cette zone de polygone dépend de la longueur de la chaîne de geohash et de la latitude dans laquelle vous calculez le geohash.
Mario Miler