Choisir l’implémentation de ses index : « B-TREE » ou « HASH », quelles différences ?

19 mai 2008 par arnaud

Préambule technique à une série de futurs articles, je ne vous en dis pas plus, l’épisode du jour a pour point de départ un moteur de stockage MySQL avec à la clé la possibilité, ou pas, de définir l’implémentation de ses index : B-TREE ou HASH.

Ce choix n’est en effet pas toujours disponible, c’est même plutôt rare puisque seul le moteur de stockage MEMORY vous permet depuis la version 4.1 de MySQL, d’effectuer ce choix. Nous ne parlerons pas ici du MySQL Cluster et de son moteur NDB qui sera abordé spécifiquement dans un autre épisode.

Pourquoi alors se soucier de ce type d’implémentation si seul le moteur MEMORY offre la possibilité de choisir ?
- MyISAM et InnoDB pourraient à l’avenir proposer ce choix.
- Afin de comprendre plus finement comment fonctionnent les index que vous utilisez tous les jours, se pencher sur la façon dont ils sont implémentés permet de mieux appréhender certains résultats.

L’index B-TREE

Star incontestée de l’implémentation de nos index sous MySQL, l’index B-TREE est partout. Et pour cause : c’est la seule implémentation disponible sous MyISAM et InnoDB, vos index sont donc systématiquement stockés sous forme de B-TREE si vos tables sont issues d’un de ces moteurs de stockage.

« Soient L et U deux entiers naturels non nuls tels que L ≤ U. On définit alors un L-U arbre B [...]« , … C’est exact, il y’a plusieurs façons d’expliquer le fonctionnement d’un index B-TREE, les formules mathématiques en sont une et wikipédia s’en chargeant très bien, je ne vais donc pas recopier les formules mathématiques ici mais vous proposer plutôt un schéma :

B-tree

Ce schéma est en fait issu d’une animation (essayez-là), cette applet java permet d’appréhender de façon presque ludique le fonctionnement du B-TREE. Amusez-vous à insérer des données et à prédire leur destination finale. Une fois que vous vous sentez à l’aise en insertion, testez le mode suppression et dites bonjour à la récursivité…

En deux mots, un B-TREE est un arbre équilibré (cette notion se perçoit bien visuellement), dont les données sont triées. A la base se trouve une racine de laquelle partent des noeuds qui se divisent ou fusionnent selon les données insérées. Chaque noeud a plusieurs clés ou valeurs, ce qui permet de diminuer la complexité de l’arbre et réduit la nécessité d’équilibrage (répartition des données).

Si les index B-TREE sont choisis par défaut pour les deux moteurs les plus utilisés, MyISAM et InnoDB, ça n’est pas par hasard. Polyvalents, les index B-TREE permettent d’effectuer un vaste choix de comparaisons. Tous les opérateurs suivants sont autorisés : =, >, >=, <, <=, la commande SQL « BETWEEN » se rajoutant à cette liste.

Les valeurs extrèmes des noeuds peuvent être considérées comme des bornes qui déterminent l’emplacement potentiel d’une clé recherchée ou à insérer.

Le HASH index

Contrairement aux moteurs MyISAM et InnoDB, le moteur MEMORY utilise par défaut une implémentation de type HASH. Cela ne veut pas dire que vous ne pouvez pas créer de B-TREE pour autant pour une colonne en particulier :

mysql> create table essai (id1 int, id2 int, unique using hash (id1), unique using btree (id2)) engine = memory;
Query OK, 0 rows affected (0.05 sec)

mysql> show create table essai;
----------------------------------+
| Table | Create Table
----------------------------------+
| essai | CREATE TABLE `essai` (
`id1` int(11) default NULL,
`id2` int(11) default NULL,
UNIQUE KEY `id1` USING HASH (`id1`),
UNIQUE KEY `id2` USING BTREE (`id2`)
) ENGINE=MEMORY DEFAULT CHARSET=latin1

Quel est le principe de fonctionnement d’un index de type HASH ? Encore une fois, un schéma permet de se fixer les idées :

hash index

Issu de l’article consacré aux tables de hachage sur wikipedia, il permet de bien comprendre ce qui se passe.

On observe sur ce schéma que lors d’une recherche une fonction de hachage est appliquée sur la clé, ici « John Smith ». Une fois hachée, cette chaîne de caractères devient un index qui pointe vers la donnée recherchée (le numéro de téléphone).
A noter : les données ne sont pas ordonnées.

Conséquence de ce mécanisme, les index HASH permettent uniquement les comparaisons d’égalité effectuées via les opérateurs « = » ou « <=> ». Rappelons que « <=> » permet de considérer la valeur NULL comme une valeur « normale », exemple :

mysql> select NULL = NULL;
+-------------+
| NULL = NULL |
+-------------+
| NULL |
+-------------+
1 row in set (0.00 sec)

mysql> select NULL <=> NULL;
+---------------+
| NULL <=> NULL |
+---------------+
| 1 |
+---------------+

Bref, les index HASH ne permettent pas de répondre à tous les types de requête.

Démonstration en utilisant la base bien connue « world » disponible au téléchargement sur le site de MySQL.
Issue de cette base, la table « country » contient 239 pays dont la clé primaire est un code de trois caractères, ‘FRA’ pour la France par exemple. On cherche à déterminer quels sont les pays dont le code abrégé est supérieur à la chaîne de caractère ‘TOTO’ .

Par défaut cette table est en MyISAM. Nous sommes donc en présence d’une implémentation B-TREE pour l’index. On effectue un EXPLAIN sur une requête très simple :

mysql> explain select * from country where code > ‘TOTO’\G
*************************** 1. row ******

id: 1
select_type: SIMPLE
table: country
type: range
possible_keys: PRIMARY
key: PRIMARY
key_len: 3
ref: NULL
rows: 27
Extra: Using where
1 row in set (0.00 sec)

(A noter : le « \G » permet un affichage vertical à partir du client mysql.)

On voit ici que la clé primaire est bien utilisée pour répondre à cette requête (key : PRIMARY).

Modifions le moteur de stockage pour du MEMORY et réappliquons la même requête :

mysql> alter table country engine = MEMORY;
Query OK, 239 rows affected (0.06 sec)
Records: 239 Duplicates: 0 Warnings: 0

mysql> explain select * from country where code > ‘TOTO’\G
*************************** 1. row ************

id: 1
select_type: SIMPLE
table: country
type: ALL
possible_keys: PRIMARY
key: NULL
key_len: NULL
ref: NULL
rows: 239
Extra: Using where
1 row in set (0.00 sec)

On voit ici que la recherche n’a pas pu s’effectuer via la clé primaire implémentée en HASH. La clé primaire est bien détectée comme candidate potentielle (possible_keys : PRIMARY) mais elle n’est finalement pas retenue (key : NULL) et c’est finalement un parcours total de la table qui sera effectué (type : ALL).

Les données n’étant pas ordonnées, l’indexation du champ « Code » n’a malgré tout pas permis de déterminer qu’elles étaient les valeurs des codes suivants ou précédents.

Bien évidemment sur un tel exemple à la volumétrie aussi faible, l’impact sur les performances est insignifiant. Néanmoins ceci permet de comprendre que la transformation d’une table MyISAM à une table MEMORY par un simple ALTER TABLE ne permet pas forcément d’obtenir le même plan d’exécution sur les deux moteurs et ceci pour une définition de table identique.
Il faut donc surveiller le plan d’exécution avant et après la transformation, ainsi que mesurer les performances obtenues (benchmarks) afin de mesurer l’impact du passage d’un moteur à l’autre. Accéder à des données en mémoire est bien sûr plus rapide qu’aller les chercher sur disque mais peut-être avez-vous réellement besoin qu’un index particulier soit pris en compte, à vous de le vérifier.

A noter enfin qu’il est possible avec le moteur MEMORY de définir pour une colonne donnée un HASH index non unique, c’est une implémentation des HASH index un peu particulière choisie par MySQL. La documentation conseille d’ailleurs à ce sujet d’utiliser l’implémentation B-TREE pour les champs dont les données sont trop redondantes. En effet, des ralentissements proportionnels à cette redondance sont à prévoir lors des UPDATE et DELETE. Un billet de Peter Zaitsev relate parfaitement ce phénomène.

InnoDB et l’ADAPTIVE HASH INDEX

Particularité d’InnoDB, ce moteur est capable de « transformer » les index B-TREE en équivalent HASH si l’optimiseur détecte qu’un gain est possible, d’où le nom de cette technique : ADAPTIVE HASH INDEX, (attention la traduction française utilise « base en mémoire », il s’agit d’une « table »).
Dans un tel cas, les index restent implémentés en B-TREE, cependant InnoDB peut créer à la volée des versions HASH de ces derniers. La commande SHOW INNODB STATUS est alors toute indiquée pour observer les performances relatives aux deux implémentations.

A retenir :

- Parmi MyISAM, InnoDB et MEMORY, seul le moteur de stockage MEMORY vous permet de choisir l’implémentation (B-TREE ou HASH) de vos index.
- Ce choix a une incidence sur le plan d’exécution de vos requêtes.
- Les index de type HASH sont très performants mais restreints aux opérateurs « = » et « <=> ».
- Les index de type B-TREE sont les plus utilisés et plus polyvalents (« = », « > », « >= », « < », « <= »).

Mots-clefs : ,

5 commentaires sur “Choisir l’implémentation de ses index : « B-TREE » ou « HASH », quelles différences ?”

  1. [...] les quelques conseils de ce billet tout en relisant pourquoi pas l’article concernant l’implémentation des index (BTREE ou HASH) selon le type de votre moteur de stockage (MyISAM, InnoDB ou MEMORY). Il reste certaines de vos [...]

  2. StephaneC dit :

    Très bonne explication !!
    Il est également possible d’émuler avec des tables MyISAM ou InnoDB des index de type hash…il faudrait un peu plus de place pour décrire une technique utilisable !
    Il y a certaines précautions à prendre, en particulier pour maintenir les index à jour, et on peut considérer que c’est du bricolage, mais ça peut être une solution intéressante quand on cherche à indexer des chaînes de caractères qui ont tendance à être longues (et bien sûr qu’on utilise des égalités ou inégalités avec le champ indexé !)

  3. Arnaud dit :

    Voilà pourquoi pas une idée pour un prochain billet ;)
    Aux risques déjà évoqués je rajouterais qu’il faut veiller à conserver une bonne sélectivité de l’index.

    Pour les plus curieux (et impatients) d’entre vous, sachez que cette technique est évoquée dans le très bon MySQL High Performance 2nd Edition : http://www.dbnewz.com/2008/09/10/lincontournable-ouvrage-de-la-rentree-mysql-high-performance-2nd-edition/

  4. Sharlott dit :

    Merci beaucoup pour cette explication qui m’a enfin fait comprendre le fonctionnement du B-Arbre… et oui, je suis allergique aux formules mathématiques!

  5. Olivier dit :

    Est-ce que la cardinalité d’un index a une influence significative sur la taille d’un BTREE ?
    J’ai l’impression qu’un index a faible cardinalité aura tendance à faire un « gros » btree, sans pouvoir l’expliquer.

Laisser une réponse