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

Étant donné que l'indexation est si importante que votre ensemble de données augmente en taille, 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 d'indexation d'un champ, consultez Comment indexer une colonne de base de données .

Pourquoi est-il nécessaire?

Lorsque les données sont stockées sur des périphériques 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 d'accès au disque atomique. Les blocs de disques sont structurés de la même manière que les listes liées; les deux contiennent une section pour les données, un pointeur vers l'emplacement du nœud (ou bloc) suivant, et les deux n'ont pas besoin d'être stockés de manière contiguë.

Étant donné qu'un certain nombre d'enregistrements ne peuvent être triés que sur un champ, nous pouvons affirmer que la recherche sur un champ qui n'est pas trié nécessite une recherche linéaire qui nécessite N/2des accès aux blocs (en moyenne), où Nest le nombre de blocs qui la table s'étend. Si ce champ est un champ non clé (c'est-à-dire qu'il ne contient pas d'entrées uniques), l'espace de table entier doit être recherché aux Naccès par bloc.

Alors qu'avec un champ trié, une recherche binaire peut être utilisée, qui a log2 Ndes accès par blocs. De plus, étant donné que les données sont triées en fonction d'un champ non clé, le reste du tableau n'a pas besoin d'être recherché pour les valeurs en double, une fois qu'une valeur plus élevée est trouvée. Ainsi, l'augmentation des performances est 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 sur l'enregistrement auquel elle se rapporte. Cette structure d'index est ensuite triée, ce qui permet d'effectuer des recherches binaires dessus.

L'inconvénient de l'indexation est que ces index nécessitent de l'espace supplémentaire sur le disque car les index sont stockés ensemble dans une table à l'aide du 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 ça marche?

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

Nom du champ Type de données Taille sur le disque
id (clé primaire) INT non signé 4 octets
firstName Char (50) 50 octets
lastName Char (50) 50 octets
emailAddress Char (100) 100 octets

Remarque : char a été utilisé à la place de varchar pour permettre une taille précise sur la valeur du disque. Cet exemple de base de données contient cinq millions de lignes et n'est pas indexé. Les performances de plusieurs requêtes vont maintenant être analysées. Il s'agit d'une requête utilisant l' id (un champ clé trié) et une utilisant le prénom (un champ non trié non clé).

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

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

Une recherche linéaire sur le champ id nécessiterait une moyenne d' N/2 = 500,000accès aux blocs pour trouver une valeur, étant donné que le champ id est un champ clé. Mais comme le champ id est également trié, une recherche binaire peut être effectuée nécessitant une moyenne d' log2 1000000 = 19.93 = 20accès aux blocs. Instantanément, nous pouvons voir que c'est une amélioration drastique.

Maintenant, le champ firstName n'est ni trié ni un champ clé, donc une recherche binaire est impossible, et les valeurs ne sont pas uniques, et donc la table nécessitera une recherche jusqu'au bout pour un N = 1,000,000bloc exact accède. 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 sur l'enregistrement d'origine, il va de soi qu'il sera plus petit que l'enregistrement multi-champ vers lequel il pointe. Ainsi, l'index lui-même nécessite moins de blocs de disques que la table d'origine, ce qui nécessite donc moins d'accès aux blocs pour parcourir. Le schéma d'un index sur le champ firstName est décrit ci-dessous;

Nom du champ Type de données Taille sur le disque
firstName Char (50) 50 octets
(pointeur d'enregistrement) 4 octets spéciaux

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

Exemple 2 - indexation

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

Désormais, une recherche utilisant le champ firstName peut utiliser l'index pour augmenter les performances. Cela permet une recherche binaire de l'index avec une moyenne d' log2 277778 = 18.08 = 19accès aux blocs. Pour trouver l'adresse de l'enregistrement réel, ce qui nécessite un accès de bloc supplémentaire pour lire, ce qui porte le total 19 + 1 = 20des accès de bloc, loin des 1 000 000 d'accès de bloc requis pour trouver une correspondance firstName dans la table non indexée.

Quand faut-il l'utiliser?

Étant donné que la création d'un index nécessite un espace disque supplémentaire (277 778 blocs supplémentaires par rapport à l'exemple ci-dessus, 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, une réflexion approfondie doit être menée pour sélectionner le bon 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 simplement une perte d'espace disque et de temps de traitement lors d'une opération d'insertion ou de suppression, et donc devrait être évité. Compte tenu également de la nature d'une recherche binaire, la cardinalité ou l'unicité des données est importante. L'indexation sur un champ avec une cardinalité de 2 diviserait les données en deux, tandis qu'une cardinalité de 1 000 retournerait environ 1 000 enregistrements. Avec une cardinalité aussi faible, l'efficacité est réduite à un tri linéaire et l'optimiseur de requête évitera d'utiliser l'index si la cardinalité est inférieure à 30% du nombre d'enregistrements, ce qui fait de l'index une perte d'espace.

Exemple classique "Index dans les livres"

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

C'est 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 option que de parcourir l'intégralité 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 compte, il vous suffit de parcourir la page d'index, encore et encore, à chaque fois. Après avoir trouvé l'index correspondant, vous pouvez passer efficacement à ce chapitre en sautant le reste.

Mais alors, en plus des 1000 pages réelles, vous aurez besoin de ~ 10 pages supplémentaires pour afficher les index, donc totalement 1010 pages.

Ainsi, l'index est une section distincte qui stocke les valeurs de la colonne indexée + le pointeur vers la ligne indexée dans un ordre trié pour des recherches efficaces.

Les choses sont simples dans les écoles, non? : P

La première fois que j'ai lu cela, cela m'a été très utile. Je vous remercie.

Depuis lors, j'ai acquis un aperçu des inconvénients de la création d'index: si vous écrivez dans une table ( UPDATEou INSERT) avec un index, vous avez en fait deux opérations d'écriture dans le système de fichiers. Un pour les données de la table et un autre pour les données d'index (et leur utilisation (et - s'ils sont regroupés - l'utilisation des données de la table)). Si la table et l'index se trouvent sur le même disque dur, cela coûte plus de temps. Ainsi, une table sans index (un tas) permettrait des opérations d'écriture plus rapides. (si vous aviez deux index, vous vous retrouveriez avec trois opérations d'écriture, etc.)

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 réduire / éliminer le problème de l'augmentation du coût du temps. Cela nécessite la définition de groupes de fichiers supplémentaires avec les fichiers correspondants sur les disques durs souhaités et la définition de l'emplacement de la table / de l'index comme souhaité.

Un autre problème avec les index est leur fragmentation au fil du temps lorsque les données sont insérées. REORGANIZEaide, vous devez écrire des routines pour le faire.

Dans certains scénarios, un segment de mémoire est plus utile qu'une table avec des index,

Par exemple: - Si vous avez beaucoup d'écritures rivales, mais une seule lecture en soirée en dehors des heures ouvrables pour le signalement.

En outre, une différenciation entre les index cluster et non cluster est assez importante.

M'a aidé: - Que signifient réellement les index cluster et non cluster?

Un index n'est qu'une structure de données qui accélère la recherche d'une colonne spécifique dans une base de données. Cette structure est généralement un arbre b ou une table de hachage mais elle peut être toute autre structure logique.

Maintenant, disons que nous voulons exécuter une requête pour trouver tous les détails des employés nommés «Abc»?

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

Que se passerait-il sans index?

Le logiciel de base de données devrait littéralement regarder chaque ligne de la table Employee pour voir si le nom_employé de cette ligne est «Abc». Et, parce que nous voulons que chaque ligne avec le nom «Abc» à l'intérieur, nous ne pouvons pas arrêter de regarder une fois que nous trouvons une seule ligne avec le nom «Abc», car il pourrait y avoir d'autres lignes avec le nom Abc . Ainsi, chaque ligne jusqu'à la dernière ligne doit être recherchée - ce qui signifie que des milliers de lignes dans ce scénario devront être examinées par la base de données pour trouver les lignes avec le nom 'Abc'. C'est ce qu'on appelle une analyse complète 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 / lignes dans 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'index B-trees?

La raison pour laquelle les arbres B sont la structure de données la plus populaire pour les index est due au fait qu'ils sont efficaces en temps - car les recherches, les suppressions et les insertions peuvent toutes être effectuées en temps logarithmique. Et, une autre raison principale pour laquelle les arbres B sont plus couramment utilisés est que les données stockées à l'intérieur de l'arbre B peuvent être triées. Le SGBDR détermine généralement quelle structure de données est réellement utilisée pour un index. Mais, dans certains scénarios avec certains SGBDR, vous pouvez réellement spécifier la structure de données que vous souhaitez 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 peuvent récupérer des valeurs très rapidement si elles utilisent un index de hachage.

Par exemple, la requête dont nous avons discuté précédemment pourrait bénéficier d'un index de hachage créé sur la colonne Employee_Name. La façon dont un index de hachage fonctionnerait est que la valeur de la colonne sera la clé dans la table de hachage et la valeur réelle mappée à cette clé ne serait qu'un pointeur vers les données de ligne dans la table. Puisqu'un tableau 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 du tableau où Abc est stocké en mémoire. La recherche d'une valeur comme «Abc» dans un index de table de hachage et la récupération d'une référence à la ligne en mémoire sont évidemment beaucoup plus rapides que l'analyse de la table pour trouver toutes les lignes avec une valeur de «Abc» dans la colonne Employee_Name.

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 avec lesquelles les index de hachage ne peuvent même pas aider. Par exemple, supposons que vous vouliez découvrir tous les employés qui ont moins de 40 ans. Comment pouvez-vous faire cela avec un index de table de hachage? Eh bien, ce n'est pas possible car une table de hachage n'est utile que pour rechercher des paires de valeurs clés - ce qui signifie des requêtes qui vérifient l'égalité

Que contient exactement un index de base de données? Ainsi, vous savez maintenant qu'un index de base de données est créé sur une colonne d'une table et que l'index stocke les valeurs dans cette colonne spécifique. Mais, il est important de comprendre qu'un index de base de données ne stocke pas les valeurs dans les 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 ne stockions que toutes les autres colonnes dans l'index, ce serait comme créer une autre copie de la table entière - ce qui prendrait beaucoup trop d'espace et serait très inefficace.

Comment une base de données sait-elle quand utiliser un index? Lorsqu'une requête comme «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 que la colonne Employee_Name ait un index créé dessus, la base de données devra décider s'il est réellement judicieux d'utiliser l'index pour trouver les valeurs recherchées - car il existe certains scénarios où il est en fait moins efficace d'utiliser l'index de la base de données , et plus efficace simplement pour scanner la table entière.

Quel est le coût d'avoir un index de base de données?

Il prend de l'espace - et plus votre table est grande, plus votre index est grand. Un autre impact sur les performances des 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 jusqu'à la minute que ce qui se trouve dans la ou les colonnes de table couvertes par l'index.

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 également

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

Description simple!

L'index n'est rien d'autre qu'une structure de données qui stocke les valeurs d'une colonne spécifique dans une table. Un index est créé sur une colonne d'une table.

Exemple: Nous avons une table de base de données appelée Useravec trois colonnes - Name, Ageet Address. Supposons que la Usertable comporte des milliers de lignes.

Maintenant, disons que nous voulons exécuter une requête pour trouver tous les détails des utilisateurs nommés «John». Si nous exécutons la requête suivante:

SELECT * FROM User 
WHERE Name = 'John'

Le logiciel de base de données devrait littéralement regarder chaque ligne du Usertableau pour voir si la Nameligne est "John". Cela prendra beaucoup de temps.

C'est là que indexnous aide: l' index est utilisé pour accélérer les requêtes de recherche en réduisant essentiellement le nombre d'enregistrements / lignes dans une table qui doit être examinée .

Comment créer un index:

CREATE INDEX name_index
ON User (Name)

An se indexcompose de valeurs de colonne (par exemple: John) d'une table , et ces valeurs sont stockées dans une structure de données .

Alors maintenant, la base de données utilisera l'index pour trouver des employés nommés John, car l'index sera probablement trié alphabétiquement par nom d'utilisateur. Et, parce qu'il est trié, cela signifie que la recherche d'un nom est beaucoup plus rapide car tous les noms commençant par un «J» seront juste à côté les uns des autres dans l'index!

Juste une suggestion rapide. Comme l'indexation vous coûte des écritures et de l'espace de stockage supplémentaires, donc si votre application nécessite plus d'opérations d'insertion / mise à jour, vous voudrez peut-être utiliser des tables sans index, mais si cela nécessite plus d'opérations de récupération de données, vous devriez opter pour l'indexation table.

Pensez simplement à Database Index comme Index d'un livre.

Si vous avez un livre sur les chiens et que vous souhaitez trouver des informations sur, disons, les bergers allemands, vous pouvez bien sûr parcourir toutes les pages du livre et trouver ce que vous cherchez - mais cela prend bien sûr beaucoup de temps et non très vite.

Une autre option est que, vous pouvez simplement aller dans la section Index du livre, puis trouver ce que vous recherchez en utilisant le nom de l'entité que vous recherchez (dans ce cas, German Shepherds) et en regardant également le numéro de page à trouvez rapidement ce que vous cherchez.

Dans la base de données, le numéro de page est appelé pointeur qui dirige la base de données vers l'adresse sur le disque où se trouve l'entité. En utilisant la même analogie de German Shepherd, nous pourrions avoir quelque chose comme ceci ("German Shepherd", 0x77129) où 0x77129est l'adresse sur le disque où les données de ligne pour German Shepherd sont stockées.

En bref, un index est une structure de données qui stocke les valeurs d'une colonne spécifique dans une table afin d'accélérer la recherche de requête.