Quelle est la difference entre btree et rtree indexing?

36

J'ai remarqué sur MySQLWorkbench que vous pouvez choisir comment stocker vos index avant de procéder à l'ingénierie de votre conception. Les types de stockage sont:

  1. BTREE
  2. RTREE
  3. HACHER

En recherchant cela, j'ai trouvé des informations qui me paraissaient assez importantes, alors je cherche des informations pratiques sur la différence entre celles-ci et / ou les raisons pour lesquelles vous devriez en choisir une sur une autre.

De plus, comme je n’avais jamais choisi de type de stockage auparavant, je suppose que MySQL choisit un type de stockage par défaut (BTREE?)


la source

Réponses:

51

BTree

BTree (en fait B * Tree) est une carte clé-valeur ordonnée efficace. Sens:

  • compte tenu de la clé, un indice BTree peut rapidement trouver un enregistrement,
  • un BTree peut être numérisé dans l'ordre.
  • il est également facile d'extraire toutes les clés (et tous les enregistrements) d'une plage.

par exemple "tous les événements entre 9h et 17h", "noms commençant par 'R"

RTree

RTree est un spatial indexqui signifie qu'il peut rapidement identifier les closevaleurs dans 2 dimensions ou plus. Il est utilisé dans les bases de données géographiques pour des requêtes telles que:

tous les points à moins de X mètres de (x, y)

Hacher

Le hachage est une carte clé-valeur non ordonnée. C'est encore plus efficace qu'un BTree: O(1)au lieu de O(log n).

Mais il n'a pas de concept d'ordre et ne peut donc pas être utilisé pour des opérations de tri ou pour extraire des plages.

En guise de remarque, à l'origine, MySQL n'autorisait que les index Hash sur les MEMORYtables; mais je ne sais pas si cela a changé au fil des ans.

Javier
la source
Est-ce que MySQL supporte Rtrees?
Pacerier
2
oui, ils s'appellent SPATIAL INDEX ( dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html )
Javier
Cool, merci =) Y a-t-il d'autres structures en plus de ces 3 ou des structures prévues dans un proche avenir?
Pacerier
Les tables de mémoire supportent aussi les index btree
Amareswar
@Amareswar, c'est vrai. Peut-être que ma réponse peut être lue dans les deux sens, mais ce que je voulais dire, c'est que les index HASH n'étaient autorisés que sur les tables MEMORY, pas sur les tables «normales».
Javier