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

Translate

Étant donné que l'indexation est si importante à mesure 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, consultezComment indexer une colonne de base de données.

This question and all comments follow the "Attribution Required."

Toutes les réponses

Translate

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 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 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 seul champ, nous pouvons affirmer que la recherche sur un champ non trié nécessite une recherche linéaire qui nécessiteN/2bloquer les accès (en moyenne), oùNest le nombre de blocs que couvre la table. Si ce champ est un champ non clé (c'est-à-dire qu'il ne contient pas d'entrées uniques), alors tout le tablespace doit être recherché àNbloquer les accès.

Alors qu'avec un champ trié, une recherche binaire peut être utilisée, qui alog2 Nbloquer les accès. De plus, comme les données sont triées à partir d'un champ non clé, le reste de la table 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 vers l'enregistrement auquel elle 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 un espace supplémentaire sur le disque puisque 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 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

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 leid(un champ clé trié) et un utilisant lePré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 der = 5,000,000enregistrements d'une taille fixe donnant une longueur d'enregistrement deR = 204octets et ils sont stockés dans une table à l'aide du moteur MyISAM qui utilise la taille de bloc par défautB = 1,024octets. Le facteur de blocage de la table seraitbfr = (B/R) = 1024/204 = 5enregistrements par bloc de disque. Le nombre total de blocs requis pour contenir la table estN = (r/bfr) = 5000000/5 = 1,000,000blocs.

Une recherche linéaire sur le champ id nécessiterait une moyenne deN/2 = 500,000bloquer 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 delog2 1000000 = 19.93 = 20bloquer les accès. Nous pouvons voir instantanément que c'est une amélioration drastique.

Maintenant lePrénomn'est ni trié ni champ clé, donc une recherche binaire est impossible, et les valeurs ne sont pas uniques, et donc la table nécessitera une recherche jusqu'à la fin pour un exactN = 1,000,000bloquer 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 itérer. Le schéma d'un index sur lePrénomle champ est décrit ci-dessous;

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

Remarque: 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 der = 5,000,000enregistrements avec une longueur d'enregistrement d'index deR = 54octets et en utilisant la taille de bloc par défautB = 1,024octets. Le facteur de blocage de l'indice seraitbfr = (B/R) = 1024/54 = 18enregistrements par bloc de disque. Le nombre total de blocs requis pour contenir l'index estN = (r/bfr) = 5000000/18 = 277,778blocs.

Maintenant, une recherche utilisant lePrénomfield peut utiliser l'index pour augmenter les performances. Cela permet une recherche binaire de l'index avec une moyenne delog2 277778 = 18.08 = 19bloquer les accès. Pour trouver l'adresse de l'enregistrement réel, qui nécessite un autre accès de blocage pour lire, ce qui porte le total à19 + 1 = 20bloquer les accès, bien loin des 1000000 accès de bloc nécessaires pour trouver unPrénommatch dans la table non indexée.

Quand doit-il être utilisé?

Étant donné que la création d'un index nécessite de l'espace disque supplémentaire (277778 blocs supplémentaires de l'exemple ci-dessus, une augmentation d'environ 28%), et qu'un trop grand nombre d'index peut causer des problèmes liés aux limites de taille des systèmes de fichiers, il faut réfléchir soigneusement champs à indexer.

Comme 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 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 nombre d'enregistrement, ce qui fait de l'index une perte d'espace.

La source
Translate

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

Depuis, j'ai eu un aperçu de l'inconvénient de la création d'index: si vous écrivez dans une table (UPDATEouINSERT) 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 recours (et - en cas de clustering - le recours aux données de la table)). Si la table et l'index sont situés 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, 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 du coût accru 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 / 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 tas est plus utile qu'une table avec des index,

Par exemple: - Si vous avez beaucoup d'écritures concurrentes, mais une seule lecture tous les soirs en dehors des heures d'ouverture pour les rapports.

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

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

La source
Translate

Un index est simplement 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 b-tree ou une table de hachage, mais elle peut être n'importe quelle autre structure logique.

La source
Translate

Exemple classique"Index dans les livres"

Prenons un "Livre" de 1000 pages, divisé par 100 sections, chaque section avec 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 le livre entier. soit: 1000 pages

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 sautant d'autres sections.

Mais alors, en plus de 1000 pages, vous aurez besoin d'environ 10 pages supplémentaires pour afficher la page d'index, donc 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

La source
Translate

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 index?

Le logiciel de base de données devrait littéralement regarder chaque ligne de la table Employee pour voir si le Employee_Name de cette ligne est «Abc». Et, parce que nous voulons chaque ligne avec le nom 'Abc' à l'intérieur, nous ne pouvons pas simplement 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 nomAbc. 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 unanalyse 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-Tree?

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 qui sont stockées à l'intérieur de l'arbre B peuvent être triées. Le SGBDR détermine généralement la structure de données réellement utilisée pour un index. Mais, dans certains scénarios avec certains SGBDR, vous pouvez en fait 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 de rechercher simplement 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é 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é serait simplement un pointeur vers les données de ligne dans la table. Puisqu'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 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 parcourir 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 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 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 ne stockions que toutes les autres colonnes de l'index, ce serait comme 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 comme «SELECT * FROM Employee WHERE Employee_Name = 'Abc'» est exécutée, la base de données vérifiera s'il existe un index sur la ou les colonnes interrogées. En supposant que la colonne Employee_Name comporte 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 où il est en fait 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'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 problème de performances 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 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
La source
Translate

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 Utilisateur avec trois colonnes - Nom, Âge et Adresse. Supposons que la table User comporte des milliers de lignes.

Maintenant, disons que nous voulons 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 regarder chaque ligne de la table User pour voir si le nom de cette ligne est «John». Cela prendra du temps.
C'est là que l'index nous aide "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é".
Comment créer un index

CREATE INDEX name_index
ON User (Name)

Un index se compose de valeurs de colonne (par exemple: John) 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 trouver des employés nommés John car l'index sera vraisemblablement trié par ordre alphabétique du nom des utilisateurs. 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é de l'autre dans l'index!

La source
Translate

Juste une petite suggestion. Comme l'indexation vous coûte des écritures et de l'espace de stockage supplémentaires, si votre application nécessite plus d'opérations d'insertion / mise à jour, vous pouvez 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'index table.

La source
Translate

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 voulez trouver des informations sur, disons, les bergers allemands, vous pouvez bien sûr feuilleter toutes les pages du livre et trouver ce que vous cherchez - mais cela prend bien sûr du temps et non très vite.

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 à trouvez rapidement ce que vous recherchez.

Dans Database, le numéro de page est appelé un 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 ça ("German Shepherd", 0x77129) où0x77129est l'adresse sur le disque où les données de ligne pour le 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.

La source