J'ai une application qui ne sélectionnera que l'égalité, et je suppose que je devrais utiliser un index de hachage sur un index btree. À ma grande consternation, les indices de hachage ne sont pas pris en charge sur MyISAM ou InnoDB. Quoi de neuf avec ça?
35
Réponses:
De nombreuses bases de données ne prennent pas en charge les index à base de hachage du tout .
Pour qu’une table de hachage soit efficace, vous devez connaître le nombre de lignes susceptibles d’être présentes. Sinon, la table de hachage de base sera beaucoup trop volumineuse (nombreuses entrées vides, perte d’espace et risque potentiel d’E / S de disque) ou trop petite. L’indirection est souvent utilisée (éventuellement plusieurs niveaux d’indirection, ou pire si l’implémentation de hachage est à un niveau, vous pourriez éventuellement effectuer une recherche linéaire sur un nombre suffisant d’enregistrements). À ce stade, les choses ne sont probablement pas plus efficaces que l’arborescence. index de toute façon.
Donc, pour être généralement utile (c’est-à-dire généralement meilleur que l’alternative), l’indice doit être reconstitué de temps à autre à mesure que les données augmentent (et diminuent), ce qui pourrait ajouter une surcharge importante par intermittence. Cela convient généralement avec les tables basées sur la mémoire car la reconstruction sera probablement assez rapide (car les données seront toujours dans la RAM et ne seront probablement pas massives dans tous les cas), mais reconstruire un index volumineux sur le disque est une tâche ardue. opération très lourde (et IIRC mySQL ne supporte pas les reconstructions d'index en direct, donc maintient un verrou de table pendant l'opération).
Par conséquent, les index de hachage sont utilisés dans les tables de mémoire car ils sont généralement plus performants, mais les tables basées sur disque ne les prennent pas en charge car ils pourraient nuire aux performances et ne pas constituer un bonus. Bien sûr, certaines bases de données prennent en charge la fonctionnalité, mais elles ne sont probablement pas implémentées dans les tables ISAM / InnoDB, car les responsables ne considèrent pas cette fonctionnalité digne d'être ajoutée (car le code supplémentaire à écrire et à maintenir ne vaut pas l’avantage dans les quelques circonstances où il fait une différence significative). Peut-être que si vous êtes tout à fait en désaccord, vous pourriez leur parler et exposer de bons arguments en faveur de la mise en œuvre de la fonctionnalité.
Si vous indexez des chaînes volumineuses, alors implémentez votre propre index de pseudo-hachage (en stockant un hachage de la valeur ainsi que la valeur réelle, et l'indexation avec une colonne) peut fonctionner, mais cela est nettement plus efficace pour les grandes chaînes (où le calcul de la valeur de hachage et la recherche de l'index d'arborescence à l'aide de cette valeur sont toujours susceptibles d'être plus rapides que la recherche dans un index d'arborescence en utilisant les valeurs les plus élevées à des fins de comparaison, et la mémoire supplémentaire utilisée ne sera pas significative). ceci en production.
la source
Sur une note connexe, vous pourriez trouver intéressante la discussion sur les types d’index de la documentation PostgreSQL. Il n'est plus présent dans les versions récentes de la documentation (à cause des optimisations ultérieures, je suppose), mais le résultat peut être similaire pour MySQL (et la raison pour laquelle les index de hachage ne sont utilisés que pour les tables de segment de mémoire):
http://www.postgresql.org/docs/8.1/static/indexes-types.html
Là encore, il s'agit d'une version (obsolète) de PostgreSQL, mais cela devrait indiquer que le type d'index "naturel" ne donnera pas nécessairement des performances optimales.
la source
Voici quelque chose d'intéressant:
Selon le livre MySQL 5.0 Certification Study Guide , page 433, Section 29.5.1
Le moteur MEMORY utilise l'algorithme HASH par défaut.
Pour rire, j'ai essayé de créer une table InnoDB et une table MyISAM avec une clé primaire avec HASH dans MySQL 5.5.12
MySQL ne s'est pas plaint.
MISE À JOUR
Mauvaises nouvelles !!! J'ai utilisé SHOW INDEXES FROM. Il dit que l'indice est BTREE.
La page MySQL de la syntaxe CREATE INDEX indique que seuls les moteurs de stockage MEMORY et NDB peuvent prendre en charge HASH INDEX.
Certaines personnes ont suggéré de suivre l’idée des pages 102 à 105 de l’ouvrage " MySQL hautes performances: optimisations, sauvegardes, réplication, etc." etc." pour émuler l’algorithme de hachage.
La page 105 présente cet algorithme rapide que je préfère:
Créez une colonne pour cela dans n'importe quelle table et indexez cette valeur.
Essaie !!!
la source
BTree n’est pas beaucoup plus lent que Hash pour la recherche sur une seule ligne. Puisque BTree fournit des requêtes de gamme très efficaces, pourquoi s’embêter avec autre chose que BTree.
MySQL fait un très bon travail de mise en cache des blocs BTree, aussi une requête basée sur BTree doit-elle rarement faire des E / S, qui est le plus gros consommateur de temps de toute requête.
la source