Comment fonctionne l'indexation des bases de données ?

Question

Étant donné que l'indexation est si importante lorsque la taille de votre ensemble de données augmente, quelqu'un peut-il expliquer comment l'indexation fonctionne à un niveau indépendant de la base de données ?

Pour plus d'informations sur les requêtes permettant d'indexer un champ, consultez la rubrique Comment indexer une colonne de base de données .

Answer 1

Pourquoi est-il nécessaire ?

Lorsque les données sont stockées sur des dispositifs de stockage sur disque, elles sont stockées sous forme de blocs de données. Ces blocs sont accessibles dans leur intégralité, ce qui en fait l'opération atomique d'accès au disque. Les blocs de disque sont structurés de la même manière que les listes chaînées ; tous deux contiennent une section pour les données, un pointeur vers l'emplacement du nœud (ou bloc) suivant, et tous deux ne doivent pas être stockés de manière contiguë.

Étant donné qu'un certain nombre d'enregistrements ne peuvent être triés que sur un seul champ, nous pouvons affirmer que la recherche sur un champ qui n'est pas trié nécessite une recherche linéaire qui requiert (N+1)/2 accès aux blocs (en moyenne), où N est le nombre de blocs que la table couvre. Si ce champ n'est pas un champ clé (c'est-à-dire qu'il ne contient pas d'entrées uniques), il faut rechercher dans tout le tablespace à N les accès aux blocs.

Alors qu'avec un champ trié, une recherche binaire peut être utilisée, qui a log2 N les accès aux blocs. De plus, comme les données sont triées en fonction d'un champ non clé, il n'est pas nécessaire de rechercher les valeurs en double dans le reste de la table, une fois qu'une valeur supérieure a été trouvée. L'augmentation des performances est donc substantielle.

Qu'est-ce que l'indexation ?

L'indexation est un moyen de trier un certain nombre d'enregistrements sur plusieurs champs. La création d'un index sur un champ dans une table crée une autre structure de données qui contient la valeur du champ et un pointeur vers l'enregistrement auquel il se rapporte. Cette structure d'index est ensuite triée, ce qui permet d'y effectuer des recherches binaires.

L'inconvénient de l'indexation est que ces index nécessitent de l'espace supplémentaire sur le disque puisque les index sont stockés ensemble dans une table utilisant le moteur MyISAM, ce fichier peut rapidement atteindre les limites de taille du système de fichiers sous-jacent si de nombreux champs de la même table sont indexés.

Comment cela fonctionne-t-il ?

Tout d'abord, présentons un exemple de schéma de table de base de données ;

Field name       Data type      Size on disk
id (Primary key) Unsigned INT   4 bytes
firstName        Char(50)       50 bytes
lastName         Char(50)       50 bytes
emailAddress     Char(100)      100 bytes

Note Le format char a été utilisé à la place du format varchar afin d'obtenir une taille précise sur le disque. Cette base de données échantillon contient cinq millions de lignes et n'est pas indexée. Les performances de plusieurs requêtes vont maintenant être analysées. Il s'agit d'une requête utilisant la méthode id (un champ clé trié) et un autre utilisant le champ premierNom (un champ non trié sans clé).

Exemple 1 - champs triés et non triés

Compte tenu de notre base de données d'échantillons de r = 5,000,000 enregistrements d'une taille fixe, ce qui donne une longueur d'enregistrement de R = 204 octets et ils sont stockés dans une table en utilisant le moteur MyISAM qui utilise la taille de bloc par défaut. B = 1,024 octets. Le facteur de blocage de la table serait bfr = (B/R) = 1024/204 = 5 enregistrements par bloc de disque. Le nombre total de blocs nécessaires pour contenir la table est de N = (r/bfr) = 5000000/5 = 1,000,000 blocs.

Une recherche linéaire sur le champ id nécessiterait en moyenne N/2 = 500,000 accède au bloc pour trouver une valeur, étant donné que le champ id est un champ clé. Mais comme le champ id est également trié, on peut effectuer une recherche binaire nécessitant en moyenne log2 1000000 = 19.93 = 20 bloquer les accès. Nous pouvons immédiatement constater qu'il s'agit d'une amélioration radicale.

Maintenant, le premierNom n'est ni trié ni un champ clé, de sorte qu'une recherche binaire est impossible. Les valeurs ne sont pas non plus uniques, et la table devra donc être recherchée jusqu'à la fin pour obtenir une valeur exacte. N = 1,000,000 bloquer les accès. C'est cette situation que l'indexation vise à corriger.

Étant donné qu'un enregistrement d'index ne contient que le champ indexé et un pointeur vers l'enregistrement original, il va de soi qu'il sera plus petit que l'enregistrement multi-champs vers lequel il pointe. L'index lui-même nécessite donc moins de blocs de disque que la table d'origine, qui nécessite donc moins d'accès aux blocs pour être parcourue. Le schéma d'un index sur la table premierNom est présenté ci-dessous ;

Field name       Data type      Size on disk
firstName        Char(50)       50 bytes
(record pointer) Special        4 bytes

Note : Les pointeurs dans MySQL ont une longueur de 2, 3, 4 ou 5 octets en fonction de la taille de la table.

Exemple 2 - indexation

Compte tenu de notre base de données d'échantillons de r = 5,000,000 enregistrements avec une longueur d'enregistrement d'index de R = 54 octets et en utilisant la taille de bloc par défaut B = 1,024 octets. Le facteur de blocage de l'index serait bfr = (B/R) = 1024/54 = 18 enregistrements par bloc de disque. Le nombre total de blocs nécessaires pour contenir l'index est de N = (r/bfr) = 5000000/18 = 277,778 blocs.

Maintenant, une recherche utilisant le premierNom peuvent utiliser l'index pour améliorer les performances. Ceci permet une recherche binaire de l'index avec une moyenne de log2 277778 = 18.08 = 19 accès aux blocs. Pour trouver l'adresse de l'enregistrement réel, qui nécessite un autre accès au bloc pour être lu, ce qui porte le total à 19 + 1 = 20 accès aux blocs, ce qui est bien loin des 1 000 000 d'accès aux blocs nécessaires pour trouver une premierNom dans la table non indexée.

Quand doit-on l'utiliser ?

Étant donné que la création d'un index nécessite de l'espace disque supplémentaire (277 778 blocs de plus dans l'exemple ci-dessus, soit une augmentation de ~28%), et qu'un trop grand nombre d'index peut entraîner des problèmes liés aux limites de taille des systèmes de fichiers, il faut bien réfléchir pour sélectionner les bons champs à indexer.

Étant donné que les index ne sont utilisés que pour accélérer la recherche d'un champ correspondant dans les enregistrements, il va de soi que l'indexation des champs utilisés uniquement pour la sortie serait un simple gaspillage d'espace disque et de temps de traitement lors d'une opération d'insertion ou de suppression, et devrait donc être évitée. De plus, étant donné la nature d'une recherche binaire, la cardinalité ou l'unicité des données est importante. L'indexation d'un champ dont la cardinalité est de 2 divise les données en deux, alors qu'une cardinalité de 1 000 renvoie environ 1 000 enregistrements. Avec une cardinalité aussi faible, l'efficacité est réduite à un tri linéaire, et l'optimiseur de requêtes évitera d'utiliser l'index si la cardinalité est inférieure à 30 % du nombre d'enregistrements, ce qui fait de l'index un gaspillage d'espace.

Answer 2

Exemple classique "Index des livres"

Considérons un "livre" de 1000 pages, divisé en 10 chapitres, chaque section comptant 100 pages.

Simple, hein ?

Maintenant, imaginez que vous voulez trouver un chapitre particulier qui contient un mot " Alchimiste ". Sans page d'index, vous n'avez pas d'autre choix que de parcourir l'ensemble du livre/des chapitres, soit 1000 pages.

Cette analogie est connue sous le nom de "Full Table Scan" dans le monde des bases de données.

Mais avec une page d'index, vous savez où aller ! De plus, pour rechercher un chapitre particulier qui vous intéresse, il vous suffit de consulter la page d'index, encore et encore, à chaque fois. Après avoir trouvé l'index correspondant, vous pouvez efficacement passer à ce chapitre en sautant le reste.

Mais alors, en plus des 1000 pages actuelles, vous aurez besoin de ~10 pages supplémentaires pour montrer les indices, donc 1010 pages au total.

Ainsi, l'index est une section séparée qui stocke les valeurs de l'indice indexée + le pointeur vers la ligne indexée dans un ordre trié pour une efficacité de efficace.

Les choses sont simples dans les écoles, n'est-ce pas ? :P

Answer 3

Un index est simplement une structure de données qui permet d'accélérer la recherche d'une colonne spécifique dans une base de données. Cette structure est généralement un b-tree ou une table de hachage, mais il peut s'agir de toute autre structure logique.

Answer 4

La première fois que j'ai lu ce texte, il m'a été très utile. Merci.

Depuis, j'ai compris les inconvénients de la création d'index : si vous écrivez dans une table ( UPDATE o INSERT ) avec un index, vous avez en fait deux opérations d'écriture dans le système de fichiers. L'une pour les données de la table et l'autre pour les données de l'index (et le recours à celui-ci (et - s'il est en cluster - le recours aux données de la table)). Si la table et l'index sont situés sur le même disque dur, cela prend plus de temps. Ainsi, une table sans index (un tas), permettrait des opérations d'écriture plus rapides. (si vous aviez deux index, vous auriez trois opérations d'écriture, et ainsi de suite).

Cependant, la définition de deux emplacements différents sur deux disques durs différents pour les données d'index et les données de table peut diminuer/éliminer le problème de l'augmentation du coût du temps. Il faut pour cela définir des groupes de fichiers supplémentaires avec les fichiers correspondants sur les disques durs souhaités et définir l'emplacement de la table et de l'index comme on le souhaite.

Un autre problème des index est leur fragmentation dans le temps, au fur et à mesure de l'insertion des données. REORGANIZE aide, vous devez écrire des routines pour que cela soit fait.

Dans certains scénarios, un tas est plus utile qu'une table avec des index,

Par exemple, si vous avez beaucoup d'écritures concurrentes mais seulement une lecture nocturne en dehors des heures de travail pour le reporting.

Il est également important de faire la distinction entre les index en grappe et les index non en grappe.

Cela m'a aidé:- Que signifient les termes "Clustered" et "Non clustered" ?

Answer 5

Maintenant, disons que nous voulons exécuter une requête pour trouver tous les détails de tous les employés qui sont nommés 'Abc' ?

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

Que se passerait-il sans indice ?

Le logiciel de base de données devrait littéralement examiner chaque ligne de la table des employés pour voir si le nom d'employé de cette ligne est "Abc". Et, parce que nous voulons que chaque ligne contienne le nom "Abc", nous ne pouvons pas arrêter de chercher une fois que nous avons trouvé une seule ligne avec le nom "Abc", car il pourrait y avoir d'autres lignes avec le nom "Abc". Abc . Il faut donc rechercher chaque ligne jusqu'à la dernière, ce qui signifie que, dans ce scénario, des milliers de lignes devront être examinées par la base de données pour trouver les lignes portant le nom "Abc". C'est ce que l'on appelle un balayage complet de la table

Comment un index de base de données peut améliorer les performances

L'intérêt d'avoir un index est d'accélérer les requêtes de recherche en réduisant essentiellement le nombre d'enregistrements/rangs d'une table qui doivent être examinés. Un index est une structure de données (le plus souvent un arbre B) qui stocke les valeurs d'une colonne spécifique dans une table.

Comment fonctionne l'indice B-trees ?

La raison pour laquelle les arbres B sont la structure de données la plus populaire pour les index est qu'ils sont efficaces en termes de temps, car les consultations, les suppressions et les insertions peuvent toutes être effectuées en temps logarithmique. Une autre raison majeure pour laquelle les arbres B sont plus couramment utilisés est que les données qui sont stockées dans l'arbre B peuvent être triées. Le SGBDR détermine généralement quelle structure de données est utilisée pour un index. Mais, dans certains scénarios avec certains SGBDR, vous pouvez spécifier la structure de données que vous voulez que votre base de données utilise lorsque vous créez l'index lui-même.

Comment fonctionne un index de table de hachage ?

La raison pour laquelle les index de hachage sont utilisés est que les tables de hachage sont extrêmement efficaces lorsqu'il s'agit simplement de rechercher des valeurs. Ainsi, les requêtes qui comparent l'égalité à une chaîne de caractères peuvent récupérer les valeurs très rapidement si elles utilisent un index de hachage.

Par exemple, la requête dont nous avons parlé précédemment pourrait bénéficier d'un index de hachage créé sur la colonne Employee_Name. Un index de hachage fonctionne de la manière suivante : la valeur de la colonne sera la clé de la table de hachage et la valeur réelle associée à cette clé sera simplement un pointeur vers les données de la ligne dans la table. Comme une table de hachage est essentiellement un tableau associatif, une entrée typique ressemblerait à quelque chose comme "Abc => 0x28939″, où 0x28939 est une référence à la ligne de la table où Abc est stocké en mémoire. Rechercher une valeur comme "Abc" dans un index de table de hachage et récupérer une référence à la ligne en mémoire est évidemment beaucoup plus rapide que de scanner la table pour trouver toutes les lignes avec une valeur de "Abc" dans la colonne Nom_de_l'employé.

Les inconvénients d'un index de hachage

Les tables de hachage ne sont pas des structures de données triées, et il existe de nombreux types de requêtes pour lesquelles les index de hachage ne sont même pas utiles. Par exemple, supposons que vous vouliez trouver tous les employés qui ont moins de 40 ans. Comment pouvez-vous faire cela avec un index de table de hachage ? Ce n'est pas possible, car une table de hachage ne sert qu'à rechercher des paires clé-valeur, c'est-à-dire des requêtes qui vérifient l'égalité.

Que contient exactement un index de base de données ? Vous savez donc maintenant qu'un index de base de données est créé sur une colonne d'une table et que l'index stocke les valeurs de cette colonne spécifique. Mais il est important de comprendre qu'un index de base de données ne stocke pas les valeurs des autres colonnes de la même table. Par exemple, si nous créons un index sur la colonne Employee_Name, cela signifie que les valeurs des colonnes Employee_Age et Employee_Address ne sont pas également stockées dans l'index. Si nous stockions toutes les autres colonnes dans l'index, cela reviendrait à créer une autre copie de la table entière, ce qui prendrait beaucoup trop de place et serait très inefficace.

Comment une base de données sait-elle quand utiliser un index ? Lorsqu'une requête telle que "SELECT * FROM Employee WHERE Employee_Name = 'Abc'" est exécutée, la base de données vérifie s'il existe un index sur la ou les colonnes interrogées. En supposant qu'un index soit créé pour la colonne Nom_Employé, la base de données devra décider s'il est réellement utile d'utiliser l'index pour trouver les valeurs recherchées. En effet, dans certains cas, il est moins efficace d'utiliser l'index de la base de données et plus efficace d'analyser la table entière.

Quel est le coût de l'indexation d'une base de données ?

Il prend de la place - et plus votre table est grande, plus votre index est grand. Un autre problème de performance avec les index est le fait que chaque fois que vous ajoutez, supprimez ou mettez à jour des lignes dans la table correspondante, les mêmes opérations devront être effectuées sur votre index. N'oubliez pas qu'un index doit contenir les mêmes données actualisées que celles contenues dans la ou les colonnes de la table qu'il couvre.

En règle générale, un index ne doit être créé sur une table que si les données de la colonne indexée sont fréquemment interrogées.

Voir aussi

1. Quelles colonnes font généralement de bons index ?
2. Comment fonctionnent les index de base de données