On dit souvent que l'indexation est une technique incontournable pour traiter efficacement les requêtes au cas où votre base de données serait suffisamment volumineuse. Cet article est destiné à résumer ce qu'est l'index de base de données et à revisiter le hachage et le B+Tree.
L'index est une structure de données qui organise les enregistrements pour optimiser certains types d'opérations de récupération. Nous pouvons créer un index sur un champ de la table puis récupérer tous les enregistrements qui satisfont aux conditions de recherche sur search-key domaine. Sans index, notre requête finirait par balayer linéairement tout le contenu de la table pour n'extraire qu'un ou quelques enregistrements.
Dans cet article, j'aimerais résumer les performances et les cas d'utilisation de deux techniques d'indexation courantes :Hash index et arbre B+
Indice de hachage
Cette technique est largement utilisée pour créer des index dans la mémoire principale parce que sa récupération rapide par nature. Il a une complexité de fonctionnement moyenne en O(1) et une complexité de stockage en O(n).
Dans de nombreux livres, les gens utilisent le terme bucket pour désigner une unité de stockage qui stocke un ou plusieurs enregistrements
Il y a deux choses à discuter en matière de hachage :
- Fonction de hachage :mappe les clés de recherche (en tant qu'entrée) sur un entier représentant cette clé dans le compartiment.
- Schéma de hachage :comment gérer les collisions de clés après le hachage.
Certaines personnes demandent :pourquoi une collision ? Une fonction de hachage parfaite existe-t-elle ? En fait, disons que vos clés sont un ensemble infini, il est impossible de les mapper dans un ensemble d'entiers 32 bits sans avoir de collision. Il devrait y avoir un compromis entre le calcul et le taux de collision.
Il existe quelques schémas de hachage qui méritent d'être mentionnés :le sondage linéaire, le hachage chaîné et le hachage extensible. Les algorithmes de recherche/insertion/suppression varient selon le schéma de hachage, par exemple, le hachage en chaîne traite les collisions de clés en plaçant des éléments ayant la même valeur de hachage dans le même compartiment.
Avantages
- L'index de hachage convient à la recherche d'égalité ou de clé primaire. Les requêtes peuvent bénéficier de l'index de hachage pour obtenir un coût de recherche O(1) amorti. Par exemple :
SELECT name, id FROM student WHERE id = '1315';
Inconvénients
La table de hachage a certaines limitations :
- Les requêtes de plage ne sont pas efficaces. La table de hachage est basée sur une distribution uniforme. En d'autres termes, vous n'avez aucun contrôle sur l'endroit où une entrée d'index va être placée.
- Faible évolutivité :les performances de l'opération de recherche peuvent se dégrader en cas de nombreuses collisions et nécessitent de redimensionner la table de hachage, puis de rehacher les entrées d'index existantes.
Arbre B+
Il s'agit d'une structure de données arborescente auto-équilibrée qui maintient les données dans un ordre trié et permet une recherche rapide dans chaque nœud, généralement à l'aide d'une recherche binaire.
B+Tree est une implémentation d'index standard dans presque tous les systèmes de bases de données relationnelles.
B+Tree est essentiellement un arbre de recherche M-way qui a la structure suivante :
- parfaitement équilibré :les nœuds feuilles ont toujours la même hauteur.
- chaque nœud interne autre que la racine est au moins à moitié plein (M/2 − 1 <=num of keys <=M − 1).
- chaque nœud interne avec k clés a k+1 enfants non nuls.
Chaque nœud de l'arbre a un tableau de paires clé-valeur triées. La paire clé-valeur est construite à partir de (valeur de clé de recherche, pointeur) pour les nœuds racine et internes. Les valeurs des nœuds feuilles peuvent être de 2 possibilités :
- l'enregistrement réel
- le pointeur vers l'enregistrement réel
Rechercher une valeur v
- Commencer par le nœud racine
- Bien que le nœud ne soit pas un nœud feuille, nous faisons :
- Trouvez le plus petit Ki où Ki>=v
- Si Ki ==v :définit le nœud courant sur le nœud pointé par Pi+1
- Sinon, définissez le nœud actuel sur le nœud pointé par Pi
Clés en double
En général, la clé de recherche peut être dupliquée. Pour résoudre ce problème, la plupart des implémentations de bases de données proposent une clé de recherche composite. Par exemple, nous voulons créer un index sur student_name alors notre clé de recherche composite devrait être (nom_étudiant, Ap) où Ap est la clé primaire de la table.
Avantages
B+tree propose deux fonctionnalités principales :
- Minimiser les opérations d'E/S
- Hauteur réduite :B+Tree a un facteur de ramification assez important (valeur entre 50 et 2000 souvent utilisée) qui rend l'arbre gros et court. La figure ci-dessous illustre un arbre B + avec une hauteur de 2. Comme nous pouvons voir que les nœuds sont étalés, il faut moins de nœuds pour traverser jusqu'à une feuille. Le coût de la recherche d'une seule valeur est la hauteur de l'arbre + 1 pour l'accès aléatoire à la table.
- Évolutivité :
- Vous avez des performances prévisibles pour tous les cas, O(log(n)) en particulier. Pour les bases de données, c'est généralement plus important que d'avoir de meilleures performances de cas optimal ou moyen.
- L'arbre reste toujours équilibré par sa mise en œuvre. Un B+Tree à n clés a toujours une profondeur de O(log(n)). Ainsi, les performances ne se dégraderont pas si la base de données grossit. Une arborescence à quatre niveaux avec un facteur de ramification de 500 peut stocker jusqu'à 256 To à condition qu'une page ait une taille de 4 Ko.
- B+Tree est le plus adapté aux requêtes de plage, par exemple
"SELECT * FROM student WHERE age > 20 AND age < 22"
Conclusion
Bien que l'index de hachage fonctionne mieux en termes de requêtes de correspondance exacte, B+Tree est sans doute la structure d'index la plus largement utilisée dans RDBMS grâce à ses performances constantes en termes d'évolutivité globale et élevée.
| B+Arbre | Hachage | |
|---|---|---|
| Temps de recherche | O(log(n)) | O(log(1)) |
| Durée d'insertion | O(log(n)) | O(log(1)) |
| Heure de suppression | O(log(n)) | O(log(1)) |
Récemment, l'arborescence de fusion à structure log (LSM-tree) a suscité un intérêt considérable en tant que concurrent de l'arborescence B+, car sa structure de données pourrait permettre une meilleure efficacité d'utilisation de l'espace de stockage. Je vais l'étudier plus en détail et publier un article à ce sujet dans un proche avenir.
