Question Comment fonctionne l'indexation de base de données?


Étant donné que l'indexation est si importante au fur et à mesure que la taille de votre ensemble de données augmente, quelqu'un peut-il expliquer comment fonctionne l'indexation au niveau de la base de données agnostique?

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


1873
2017-08-04 10:07


origine


Réponses:


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 la forme de blocs de données. Ces blocs sont accédés 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 lié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ë.

É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 nécessite N/2 bloquer les accès (en moyenne), où N est le nombre de blocs que la table couvre. Si ce champ est un champ non-clé (c'est-à-dire ne contient pas d'entrées uniques), alors tout l'espace-table doit être recherché N bloquer les accès.

Alors qu'avec un champ trié, une recherche binaire peut être utilisée, ce qui 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 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 de la performance 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 il se rapporte. Cette structure d'index est ensuite triée, ce qui permet d'effectuer des recherches binaires sur celle-ci.

L'inconvénient de l'indexation est que ces index nécessitent plus d'espace 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. .

Comment ça marche?

Tout d'abord, esquissons 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é INT 4 octets
Prénom 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. Cette base de données exemple contient cinq millions de lignes et n'est pas indexée. La performance de plusieurs requêtes va maintenant être analysée. Ce sont une requête utilisant le identifiant (un champ clé trié) et un en utilisant le Prénom (un champ non trié non-clé).

Exemple 1 - triés par rapport aux champs non triés

Compte tenu de notre base de données exemple de r = 5,000,000 enregistrements d'une taille fixe donnant une longueur record 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,024octets. Le facteur de blocage de la table serait bfr = (B/R) = 1024/204 = 5 enregistrements par bloc de disque. Le nombre total de blocs requis pour maintenir la table est N = (r/bfr) = 5000000/5 = 1,000,000 des blocs.

Une recherche linéaire sur le champ id nécessiterait une moyenne de N/2 = 500,000 bloquer les accès pour trouver une valeur, étant donné que le champ id est un champ clé. Mais puisque 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. Instantanément, nous pouvons voir que c'est une amélioration radicale.

Maintenant le Prénom champ n'est ni trié ni un champ clé, donc une recherche binaire est impossible, ni les valeurs sont uniques, et donc la table nécessitera une recherche à la fin pour une 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 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;

Nom du champ Type de données Taille sur le disque
Prénom Char (50) 50 octets
(pointeur d'enregistrement) Spécial 4 octets

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 base de données exemple 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'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 des blocs.

Maintenant, une recherche en utilisant le Prénom 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, qui nécessite un autre accès au bloc pour lire, ce qui porte le total à 19 + 1 = 20 bloquer les accès, loin des 1 000 000 accès aux blocs nécessaires pour trouver un Prénom correspondre dans la table non indexée.

Quand devrait-il être utilisé?

Étant donné que la création d'un index nécessite de l'espace disque supplémentaire (277 778 blocs supplémentaires de l'exemple ci-dessus, une augmentation de ~ 28%) et qu'un trop grand nombre d'index peut entraîner des problèmes de taille de système de fichiers. champs à indexer.

Puisque les index sont seulement utilisés pour accélérer la recherche d'un champ correspondant dans les enregistrements, il va de soi que les champs d'indexation utilisés uniquement pour la sortie seraient simplement une perte d'espace disque et de temps de traitement lors d'une opération d'insertion ou de suppression. 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 basse, 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 en fait un gaspillage d'espace.


2848
2017-08-04 10:41



La première fois que j'ai lu ceci c'était très utile pour moi. Je vous remercie.

Depuis lors, j'ai acquis un aperçu de l'inconvénient de la création d'index: si vous écrivez dans une table (UPDATE ou 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 de l'index (et le recours à celui-ci (et - si clusterisé - 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 finiriez avec trois opérations d'écriture, et ainsi de suite)

Toutefois, 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 des 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. REORGANIZE aide, vous devez écrire des routines pour l'avoir fait.

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

Par exemple: - Si vous avez beaucoup d'écritures rivales, mais seulement une lecture nocturne en dehors des heures d'ouverture pour les rapports.

En outre, une différenciation entre les index clusterisés et non clusterisés est plutôt importante.

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


175
2018-04-30 14:31



Un index est simplement une structure de données qui accélère la recherche pour une colonne spécifique d'une base de données. Cette structure est généralement une b-tree ou une table de hachage mais elle peut être n'importe quelle autre structure logique.

Pour plus d'informations, je recommande: Comment fonctionnent les index de base de données? Et, comment les index aident-ils?


130
2018-02-20 14:40



Maintenant, disons que nous voulons lancer une requête pour trouver tous les détails des employés qui s'appellent 'Abc'?

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

Que se passerait-il sans un index?

Le logiciel de base de données devrait littéralement regarder chaque rangée dans la table d'employé pour voir si le nom d'employé pour cette rangée 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 juste une 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 un balayage complet de la table

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

Le but 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 doit être examinée. 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 dans le temps - parce que 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 dans 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 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 parce que les tables de hachage sont extrêmement efficaces quand 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 colonne sera la clé dans la table de hachage et la valeur réelle mappée à cette clé serait juste un pointeur vers les données de ligne dans la table. Puisqu'une table de hachage est fondamentalement un tableau associatif, une entrée typique ressemblerait à quelque chose comme "Abc => 0x28939", où 0x28939 est une référence à la rangée de table où Abc est stocké dans la 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 l'analyse de la table pour trouver toutes les lignes avec la valeur "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 que les index de hachage ne peuvent même pas aider. Par exemple, supposons que vous vouliez connaître tous les employés qui ont 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 n'est utile que pour rechercher des paires de valeurs clés - ce qui signifie que les requêtes vérifient l'égalité

Qu'est-ce qu'il y a exactement dans un index de base de données? Donc, maintenant vous savez qu'un index de base de données est créé sur une colonne dans 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 de colonne Employee_Age et Employee_Address ne sont pas stockées dans l'index. Si nous stockions simplement toutes les autres colonnes de l'index, ce serait comme créer une autre copie de la table entière - ce qui prendrait trop de place et serait très inefficace.

Comment une base de données sait-elle quand utiliser un index? Lorsqu'une requête du type "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 (les) colonne (s) interrogée (s). En supposant que la colonne Employee_Name a 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 y a des scénarios où il est effectivement moins efficace d'utiliser l'index de base de données , et plus efficace juste pour scanner 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. Une autre amélioration des 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 doivent être effectuées sur votre index. Rappelez-vous qu'un index doit contenir les mêmes données à la minute que tout ce qu'il y a dans la ou les colonnes de table couvertes par l'index.

En règle générale, un index ne doit être créé que sur une table 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

93
2017-08-13 18:36



Exemple classique "Index dans les livres"

Considérons un "Livre" de 1000 pages, divisé par 100 sections, chaque section avec X pages.

Simple, hein?

Maintenant, sans une page d'index, pour trouver une section particulière qui commence par la lettre "S", vous n'avez pas d'autre choix que de parcourir tout le livre. i.e: 1000 pages

Mais avec une page d'index au début, vous êtes là. Et plus, pour lire une section particulière qui compte, il suffit de regarder la page d'index, encore et encore, à chaque fois. Après avoir trouvé l'index correspondant, vous pouvez passer directement à la section en sautant d'autres sections.

Mais alors, en plus de 1000 pages, vous aurez besoin d'une autre ~ 10 pages pour afficher la page d'index, donc totalement 1010 pages.

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

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


82
2018-04-23 14:43



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 a des milliers de lignes.

Maintenant, disons que nous voulons lancer une requête pour trouver tous les détails des utilisateurs qui s'appellent '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 rangée dans la table d'utilisateur pour voir si le nom pour cette rangée est «John». Cela prendra beaucoup de temps.
C'est là que l'index nous aide à "indexer est utilisé pour accélérer les requêtes de recherche en réduisant essentiellement le nombre d'enregistrements / lignes dans un tableau 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) provenant d'une table et ces valeurs sont stockées dans une structure de données.
La base de données va maintenant utiliser l'index pour trouver les employés nommés John parce que l'index sera probablement trié par ordre alphabétique selon le nom de l'utilisateur. Et, parce qu'il est trié, cela signifie que la recherche d'un nom est beaucoup plus rapide parce que tous les noms commençant par un "J" seront placés l'un à côté de l'autre dans l'index!


46
2017-08-02 01:30



Juste une suggestion rapide .. Comme l'indexation vous coûte des écritures et un 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 table.


21
2018-01-14 06:44



Pensez simplement à Database Index en tant qu'index d'un livre.  Si vous avez un livre sur les chiens et que vous voulez trouver des informations sur les bergers allemands, vous pouvez bien sûr feuilleter toutes les pages du livre et trouver ce que vous cherchez mais cela prend du temps et n'est pas très vite. Une autre option est que, vous pouvez simplement aller à la section Index du livre et ensuite trouver ce que vous cherchez en utilisant le nom de l'entité que vous recherchez (en l'occurrence, les bergers allemands) 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é 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 de Shepherd 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 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ête.


16
2017-12-21 17:16



L'index SQL est quelque chose lié à l'accélération de la recherche dans la base de données SQL. L'index permet au programmeur d'extraire les données de la base de données très rapidement. Supposons que vous soyez un étudiant ou un lecteur de livres. Votre livre contient 50 000 pages. Premier jour, vous lisez un sujet "ABC" le lendemain, vous voulez lire un autre sujet "xyz". vous ne passerez jamais manuellement par page. Ce que vous ferez dans cette situation est d'utiliser l'index de livre pour regarder le sujet spécifique et ensuite sauter directement à votre sujet. L'index a sauvé beaucoup de temps pour rechercher le sujet. Idem dans l'index SQL, Index permet de rechercher des millions d'enregistrements très rapidement à partir de la base de données.


10
2018-02-15 10:17