Comment fonctionne l’indexation d’une base de données ?[fermé]
https://stackoverflow.com/questions/1108
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Étant donné que l'indexation est d'autant plus importante que 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 pour indexer un champ, consultez Comment indexer une colonne de base de données.
La solution
Pourquoi est-ce 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 disque sont structurés à peu près de la même manière que les listes chaînées ;les deux contiennent une section pour les données, un pointeur vers l'emplacement du prochain nœud (ou bloc), et les deux n'ont pas besoin d'être stockés de manière contiguë.
Etant donné qu'un certain nombre d'enregistrements ne peuvent être triés que sur un seul champ, on peut affirmer que la recherche sur un champ qui n'est pas trié nécessite une Recherche Linéaire qui nécessite N/2 bloquer les accès (en moyenne), où N est le nombre de blocs que s'étend la table.Si ce champ est un champ non clé (c'est-à-direne contient pas d'entrées uniques), alors l'ensemble du tablespace doit être recherché à N bloquer les accès.
Alors qu'avec un champ trié, une recherche binaire peut être utilisée, qui a log2 N bloquer les accès.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.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 elle se rapporte.Cette structure d'index est ensuite triée, permettant 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 dans 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 ;
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: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 le identifiant (un champ clé trié) et un utilisant le prénom (un champ non trié non clé).
Exemple 1 - champs triés ou non triés
Compte tenu de notre exemple de base de données de r = 5,000,000 enregistrements d'une taille fixe donnant une longueur d'enregistrement de R = 204 octets et ils sont stockés dans une table à l'aide du moteur MyISAM qui utilise la taille de bloc par défaut B = 1,024 octets.Le facteur bloquant du tableau serait bfr = (B/R) = 1024/204 = 5 enregistrements par bloc de disque.Le nombre total de blocs requis pour tenir la table est 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 bloquer les accès 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 de log2 1000000 = 19.93 = 20 bloquer les accès.Nous pouvons immédiatement constater qu’il s’agit d’une amélioration drastique.
Maintenant le prénom Le champ n'est ni trié ni un champ clé, donc une recherche binaire est impossible, et les valeurs ne sont pas non plus uniques, et donc la table nécessitera une recherche jusqu'à la fin pour un champ exact. N = 1,000,000 bloquer les accès.C’est cette situation que l’indexation vise à corriger.
Étant donné qu'un enregistrement d'index contient uniquement le champ indexé et un pointeur vers l'enregistrement d'origine, il va de soi qu'il sera plus petit que l'enregistrement multi-champs vers lequel il pointe.Ainsi, l'index lui-même nécessite moins de blocs de disque 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 prénom le champ est décrit 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 selon la taille de la table.
Exemple 2 - indexage
Compte tenu de notre exemple de base de données 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 bloquant de l'indice serait bfr = (B/R) = 1024/54 = 18 enregistrements par bloc de disque.Le nombre total de blocs requis pour contenir l'index est N = (r/bfr) = 5000000/18 = 277,778 blocs.
Maintenant une recherche en utilisant le prénom le champ peut utiliser l’index pour augmenter les performances.Cela permet une recherche binaire de l'index avec une moyenne de log2 277778 = 18.08 = 19 bloquer les accès.Pour trouver l'adresse de l'enregistrement réel, ce qui nécessite un accès de bloc supplémentaire pour la lecture, ce qui porte le total à 19 + 1 = 20 bloquer les accès, on est bien loin des 1 000 000 de blocages d'accès nécessaires pour trouver un prénom correspondance dans la table non indexée.
Quand faut-il l’utiliser ?
Étant donné que la création d'un index nécessite de l'espace disque supplémentaire (277 778 blocs supplémentaires par rapport à l'exemple ci-dessus, soit une augmentation d'environ 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 index. champs à indexer.
Puisque 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, alors qu'une cardinalité de 1 000 renverrait 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 numéro d'enregistrement, ce qui fait de l'index une perte d'espace.
Autres conseils
La première fois que j'ai lu ceci, cela m'a été très utile.Merci.
Depuis, j’ai acquis une idée des inconvénients de la création d’index :si vous écrivez dans un tableau (UPDATE ou INSERT) avec un seul index, vous disposez en fait de 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 tri (et - en cas de clustering - le tri des données de la table)).Si la table et l'index se trouvent 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 vous retrouveriez avec 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 réduire/éliminer le problème de l'augmentation du temps passé.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/index comme souhaité.
Un autre problème avec les index est leur fragmentation au fil du temps, à mesure que les données sont inséré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 de nombreuses écritures concurrentes mais une seule lecture nocturne en dehors des heures de bureau pour le reporting.
En outre, une différenciation entre les index clusterisés et non clusterisés est assez importante.
M'a aidé:- Que signifient réellement les index clusterisés et non clusterisés ?
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 il peut s'agir de n'importe quelle autre structure logique.
Exemple classique "Index dans les livres"
Considérons un « Livre » de 1000 pages, divisé en 100 sections, chaque section comportant X pages.
Simple, hein ?
Désormais, sans page d'index, pour trouver une section particulière commençant par la lettre « S », vous n'avez pas d'autre choix que de parcourir l'intégralité du livre.c'est à dire:1000pages
Mais avec une page d'index au début, vous y êtes.De plus, pour lire une section particulière 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 accéder efficacement à la section en ignorant les autres sections.
Mais alors, en plus de 1000 pages, vous aurez besoin d'environ 10 pages supplémentaires pour afficher la page d'index, soit au total 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, n'est-ce pas ?:P
Maintenant, disons que nous souhaitons 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 examiner chaque ligne de la table Employee pour voir si le Employee_Name de cette ligne est « Abc ».Et comme nous voulons que chaque ligne porte le nom « Abc », nous ne pouvons pas arrêter de chercher une fois que nous avons trouvé une seule ligne portant le nom « Abc », car il pourrait y avoir d’autres lignes portant 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 portant le nom « Abc ».C'est ce qu'on appelle un analyse complète du tableau
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 d'une table qui doivent être examinées.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 termes de temps – car les recherches, les suppressions et les insertions peuvent toutes être effectuées en temps logarithmique.Et une autre raison majeure 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 parlé plus tôt 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é de la table de hachage et que la valeur réelle mappée à cette clé ne sera qu'un pointeur vers les données de ligne de la table.Puisqu'une table de hachage est essentiellement un tableau associatif, une entrée typique ressemblerait à "Abc => 0x28939", où 0x28939 est une référence à la ligne du tableau 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 d'analyser 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 pour lesquelles les index de hachage ne peuvent même pas aider.Par exemple, supposons que vous souhaitiez connaître tous les employés de moins de 40 ans.Comment pourriez-vous faire cela avec un index de table de hachage ?Eh bien, ce n'est pas possible car une table de hachage ne sert qu'à rechercher des paires clé-valeur, 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 stockions simplement 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 que la colonne Employee_Name dispose d'un index créé, 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 dans lesquels il est en réalité moins efficace d'utiliser l'index de la base de données. , et plus efficace simplement pour analyser la table entière.
Quel est le coût d’avoir un index de base de données ?
Cela prend de la place – 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 à la minute près que tout ce qui se trouve dans la ou les colonnes du tableau 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 seront fréquemment interrogées.
Voir également
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.
Par exemple, nous avons une table de base de données appelée Utilisateur avec trois colonnes : Nom, Âge et Adresse.Supposons que la table User comporte des milliers de lignes.
Supposons maintenant que nous souhaitions exécuter une requête pour trouver tous les détails de tous les 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 examiner chaque ligne de la table User pour voir si le nom de cette ligne est « John ».Cela prendra beaucoup de temps.
C'est là que l'index nous 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 doivent être examinées".
Comment créer un index
CREATE INDEX name_index
ON User (Name)
Un index est constitué de valeurs de colonnes (par exemple :John) à partir d'une table et que ces valeurs sont stockées dans une structure de données.
Alors maintenant, la base de données utilisera l'index pour rechercher les employés nommés John, car l'index sera probablement trié par ordre alphabétique du nom de l'utilisateur.Et comme 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 les uns à côté des autres dans l'index !
Juste une petite suggestion..Comme l'indexation vous coûte des écritures et un espace de stockage supplémentaires, donc si votre application nécessite plus d'opérations d'insertion/mise à jour, vous souhaiterez 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 une table indexée.
Pensez simplement à l’index de base de données comme à l’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 pas très. rapide.Une autre option est que vous pouvez simplement accéder à la section Index du livre, puis trouver ce que vous recherchez en utilisant le nom de l'entité que vous recherchez (dans ce cas, les bergers allemands) et en regardant également le numéro de page pour 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 avec le berger allemand, nous pourrions avoir quelque chose comme ceci (« Berger allemand », 0x77129) où 0x77129 est l'adresse sur le disque où les données de ligne du berger allemand 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êtes.
