Comment fonctionne l'indexation d'une base de données?

é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 au niveau agnostique de la base de données?

pour des informations sur les requêtes pour indexer un champ, cochez comment indexer une colonne de base de données .

1966
demandé sur TRiG 2008-08-04 14:07:12
la source

10 ответов

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 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 noeud (ou bloc), et les deux n'ont pas besoin d'être stockés de façon contiguë.

en raison de la é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 des accès par bloc N/2 (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), alors l'ensemble de l'espace tabl doit être recherché au bloc N accès.

alors qu'avec un champ trié, une Recherche Binaire peut être utilisé, qui a log2 N bloquer les accès. De plus, puisque les données sont triées dans un champ non-clé, le reste du tableau n'a pas besoin d'être recherché pour les valeurs dupliquées, une fois qu'une valeur plus élevée est trouvée. L'augmentation de la performance est donc importante.

qu'est-ce que l'indexation?

L'indexation est un moyen de trier un certain nombre d'enregistrements dans plusieurs champs. La création d'un index sur un champ dans une table crée une autre structure de données qui tient 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.

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 en 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, esquissons 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. Cette base de données contient cinq millions de lignes et est indexée. Les performances de plusieurs requêtes seront désormais analysées. Il s'agit d'une requête utilisant le id (un champ Clé trié) et un en utilisant le prénom (un champ non-trié non-clé).

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

étant donné notre base de données d'échantillon 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 en utilisant le moteur MyISAM qui utilise la taille de bloc par défaut B = 1,024 octets. Blocage facteur de la table 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 dans le champ id nécessiterait en moyenne un bloc d'accès N/2 = 500,000 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 block accès. Nous pouvons voir immédiatement que c'est un drastique amélioration.

maintenant le champ firstName n'est ni trié ni un champ clé, de sorte qu'une recherche binaire est impossible, ni les valeurs uniques, et donc la table nécessitera une recherche jusqu'à la fin pour un exact N = 1,000,000 block accès. C'est cette situation que l'indexation vise à corriger.

étant Donné que l'enregistrement d'index ne contient que le champ indexé et un pointeur vers l'enregistrement d'origine, il va de soi qu'il être plus petit que le disque multi-champs qu'il pointe. Ainsi l'index lui-même nécessite moins de blocs de disque que la table originale, qui nécessite donc moins d'accès de bloc pour itérer à travers. Le schéma d'un index dans le champ prénom 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 MySQL ont une longueur de 2, 3, 4 ou 5 octets selon la taille de la table.

exemple 2 - indexation

étant donné notre base de données d'échantillon 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 dossiers par bloc de disque. Le nombre total de blocs requis pour détenir l'indice est de N = (r/bfr) = 5000000/18 = 277,778 blocs.

maintenant une recherche en utilisant le firstName le champ peut utiliser l'index pour augmenter la performance. Cela permet une recherche binaire de l'indice avec une moyenne de log2 277778 = 18.08 = 19 accès bloc. Pour trouver l'adresse de l'enregistrement réel, qui nécessite un autre accès par bloc pour lire, ce qui porte le total à 19 + 1 = 20 accès par bloc, loin des 1.000.000 accès par bloc requis pour trouver une correspondance prénom dans le tableau non indexé.

Quand doit-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 par rapport à l'exemple ci-dessus, soit une augmentation d'environ 28%), et que trop d'index peuvent causer des problèmes découlant des limites de taille des systèmes de fichiers, il faut faire preuve de prudence pour sélectionner les bons champs à indexer.

comme les indices ne sont utilisés pour accélérer la recherche d'un champ correspondant dans les dossiers, il est raison que l'indexation des champs utilisés uniquement pour la sortie serait simplement un gaspillage d'espace disque et de temps de traitement lors d'une insertion ou une suppression, et devrait donc être évitée. De plus, étant donné la nature d'une recherche binaire, la cardinalité ou le caractère unique des données est important. L'indexation sur un champ avec une cardinalité de 2 diviserait les données en deux, alors qu'une cardinalité de 1 000 retournerait environ 1 000 enregistrements. Avec une si faible cardinalité l'efficacité est réduite à une sorte linéaire, et l'optimiseur de requêtes évitera d'utiliser l'index si la cardinalité est inférieure à 30% du nombre record, ce qui fait de l'index un gaspillage d'espace.

2951
répondu Xenph Yan 2018-03-10 13:40:54
la source

la première fois que j'ai lu ceci, cela m'a été très utile. Remercier.

depuis lors, j'ai eu un aperçu des inconvénients de la création d'indices: 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. Une pour les données de table et une autre pour les données d'index (et le recours de lui (et-si groupé - Le recours de données de table)). Si le tableau 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 d'accélérer les opérations d'écriture. (si vous aviez deux indices vous vous retrouvez 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 de table peut diminuer / é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 désirés et la définition de table/index emplacement souhaité.

un autre problème avec les indices est leur fragmentation au fil du temps que les données sont insérées. REORGANIZE aide, vous devez écrire des routines pour le faire.

dans certains scénarios, un tas est plus utile qu'un tableau avec des indices,

E. g: - Si vous avez beaucoup de rivalling écrit mais seulement une nuit lire en dehors des heures de bureau pour le reportage.

aussi, une différenciation entre les indices groupés et non groupés est assez important.

M'a aidé: - que signifie réellement l'indice groupé et Non groupé?

184
répondu Der U 2017-05-23 14:47:36
la source

un index est juste une structure de données qui rend la recherche plus rapide pour 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 être n'importe quelle autre structure logique.

pour plus d'information, je recommande: Comment fonctionnent les index des bases de données? Et comment les index aident-ils?

143
répondu hcarreras 2018-01-22 15:10:49
la source

exemple Classique Index "dans les Livres"

considère un" livre " de 1000 pages, divisé par 100 sections, chaque section avec X pages.

Simple, hein?

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

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

mais ensuite, en plus de 1000 pages, vous aurez besoin d'un autre ~10 pages pour afficher la page d'index, donc totalement 1010 pages.

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

les choses sont simples à l'école, n'est-ce pas? : P

108
répondu Sankarganesh Eswaran 2018-03-10 14:14:17
la source

Maintenant, imaginons que nous voulons exécuter une requête pour trouver tous les détails de tous les employés qui sont appelés ‘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 ligne de la table des employés pour voir si le Nom_employé de cette ligne est "Abc". Et, parce que nous voulons chaque ligne avec le nom " Abc’ à l'intérieur, nous ne pouvons pas juste arrêter de chercher une fois que nous trouvons juste une rangée avec le nom " Abc’, parce qu'il pourrait y avoir d'autres rangées avec le nom Abc . Ainsi, chaque ligne jusqu'à la dernière ligne doit être recherché, ce qui signifie des milliers de lignes dans ce scénario devra être examinée par la base de données pour trouver les lignes avec le nom "Abc". C'est ce qu'on appelle un balayage de table complet

Comment un index de base de données peut aider à la performance

le point entier de avoir un index permet d'accélérer les requêtes de recherche en réduisant essentiellement le nombre d'enregistrements/lignes dans un tableau qui doivent être examinés. Un indice est une structure de données (le plus souvent un arbre B) qui stocke les valeurs pour une colonne spécifique dans un tableau.

Comment fonctionne l'index B-trees?

la raison pour laquelle les arbres B sont la structure de données la plus populaire pour les indices est due au fait qu'ils sont efficaces dans le temps-parce que les recherches, les suppressions et les insertions peuvent toutes être faites en temps logarithmique. Et, une autre raison majeure est que les arbres B sont plus couramment utilisés parce 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 quelle structure de données est réellement utilisée pour un indice. Mais, dans certains scénarios avec certains RDBM, vous pouvez en fait spécifier quelle structure de données vous voulez que votre base de données utilise lorsque vous créez l'index lui-même.

Comment fait un indice de table de hash travail?

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 de chercher simplement des valeurs. Ainsi, les requêtes qui comparent l'égalité à une chaîne de caractères 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 colonne sera la clé dans le table de hachage et la valeur réelle affecté à cette touche ne serait qu'un pointeur vers les données de ligne dans le tableau. 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 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 de revenir une référence à la ligne dans la mémoire est évidemment beaucoup plus rapide que le balayage de la table pour trouver toutes les lignes avec une valeur de "Abc" dans le Colonne Employee_Name.

les inconvénients d'un indice 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 voulez découvrir tous les employés qui ont moins de 40 ans. Comment as-tu pu faire ça avec un index de table de hachage? Eh bien, ce n'est pas possible parce qu'une table de hachage est seulement bon pour chercher des paires de valeurs clés-qui moyens des requêtes pour vérifier l'égalité

Qu'est-ce qu'un index de base de données? Donc, maintenant vous savez qu'une base de données de l'index 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 L'Employee_Age et Les valeurs de la colonne Employee_Address ne sont pas stockées dans l'index. Si nous stockions 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 lancée, la base de données vérifiera s'il y a un index sur la colonne(s) interrogée. 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 logique d'utiliser l'index pour trouver les valeurs recherchées – parce qu'il y a certains scénarios où il est en fait moins efficace d'utiliser l'index de la base de données, et plus efficace juste pour balayer la table entière.

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

il prend espace – et plus votre table est grande, plus votre index est grand. Une autre performance avec 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 faites à votre index. Rappelez-vous qu'un index doit contenir les mêmes données jusqu'à la minute que ce qui est dans la colonne(s) de tableau que l'index couvre.

en règle générale, un index doit être créé sur une table si les données dans la colonne indexée sera être interrogé fréquemment.

voir aussi

  1. quelles colonnes font généralement de bons index?
  2. Comment puis-index de base de données de travail
104
répondu Somnath Muluk 2017-05-23 14:47:36
la source

Simple Description!!!!!!!!!!

L'indice n'est rien mais une structure de données qui stocke les valeurs d'une colonne spécifique dans une table. Création d'un index sur une colonne d'une table.

exemple, nous avons une table de base de données appelée User avec trois colonnes – Nom, Âge, et adresse. Supposons que la table D'Utilisateur a des milliers de lignes.

Maintenant, imaginons que nous voulons exécuter une requête pour trouver tous les détails de tous les utilisateurs qui sont nommé "John". Si nous exécutez la requête suivante.

SELECT * FROM User 
WHERE Name = 'John'

Le logiciel de base de données serait littéralement regarder chaque ligne dans la table User pour voir si le Nom de cette ligne est "John". Cela va prendre du temps.

C'est là que 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ée".

Comment créer un index

CREATE INDEX name_index
ON User (Name)

un indice 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.

" maintenant, la base de données va utiliser L'index pour trouver les employés nommés John parce que l'index sera probablement trié alphabétiquement par le nom des utilisateurs. 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 juste à côté les uns des autres dans le index!

53
répondu ProgrammerPanda 2018-01-04 13:29:34
la source

juste une suggestion.. Comme l'indexation vous coûte des Écritures supplémentaires et de l'espace de stockage, donc si votre application nécessite plus d'opération d'insertion / mise à jour, vous pourriez vouloir utiliser des tables sans index, mais si elle nécessite plus d'opérations de récupération de données, vous devriez aller pour la table indexée.

23
répondu leo 2015-01-14 09:44:51
la source

il suffit de penser à L'Index de base de données comme Index d'un livre. Si vous avez un livre sur les chiens et vous voulez trouver une information sur disons, bergers allemands, vous pouvez bien sûr feuilleter toutes les pages du livre et trouver ce que vous recherchez, mais ce est bien sûr long et pas très rapide. Une autre option est que, vous pouvez simplement aller à la section Index du livre et ensuite trouver ce que vous recherchez en utilisant le nom de l'entité que vous recherchez ( dans ce cas, Bergers allemands) et aussi en regardant le numéro de page pour trouver rapidement ce que vous recherchez. Dans la Base de données, le numéro de page est appelé un pointeur qui dirige la base de données à l'adresse sur le disque où elle se situe. En utilisant la même analogie de 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 pour berger allemand sont stockées.

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

18
répondu Alf Moh 2016-12-21 20:16:02
la source

index SQL est quelque chose liée à accélérer la recherche dans la base de données SQL. Index permet au programmeur de récupérer des données à partir 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 page par page. Ce que vous ferez dans cette situation est d'utiliser L'index de livre pour regarder le sujet spécifique et puis sauter directement à votre sujet. Index vous avez gagné beaucoup de temps pour chercher le sujet. Idem en SQL index, Index permet de rechercher des millions d'enregistrements très rapidement à partir de la base de données.

13
répondu Pooja Khatri 2018-02-15 13:17:05
la source

un index de base de données est une structure de données qui améliore la vitesse des opérations de récupération de données sur une table de base de données au coût des Écritures supplémentaires et de l'espace de stockage pour maintenir la structure de données index. Les index sont utilisés pour localiser rapidement les données sans avoir à rechercher chaque ligne dans une table de base de données chaque fois qu'une table de base de données est consultée. Les index peuvent être créés en utilisant une ou plusieurs colonnes d'une table de base de données, fournissant la base pour des recherches rapides aléatoires et l'accès efficace de commandé enregistrements.

2
répondu hechen0 2018-07-09 08:33:17
la source