2369 votes

Comment fonctionne la base de données d'indexation de travail?

Étant donné que l'indexation est donc important que votre jeu de données augmente en taille, quelqu'un peut m'expliquer comment l'indexation fonctionne à partir d'une base de données agnostique?

Pour plus d'informations sur les requêtes pour indexer un champ, découvrez http://stackoverflow.com/questions/1156/how-do-i-index-a-database-field

3472voto

Xenph Yan Points 20883

Pourquoi est-il nécessaire?

Lorsque les données sont stockées sur le disque en fonction des périphériques de stockage, il est stocké sous forme de blocs de données. Ces blocs sont accessibles dans leur intégralité, ce qui en fait atomique d'accès au disque de l'opération. 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 nœud suivant (ou bloc), et les deux n'ont pas besoin d'être stockés de manière contiguë.

En raison du fait qu'un certain nombre de documents ne peut être triée sur un terrain, nous pouvons affirmer que la recherche sur un champ qui n'est pas le tri exige une Recherche Linéaire qui exige N/2 bloquer les accès (en moyenne), où N est le nombre de blocs que le tableau s'étend sur. Si ce champ est un non-champ clé (c'est à dire ne pas contenir des entrées uniques), puis l'ensemble de l'espace de la table doit être recherché en N bloquer les accès.

Alors qu'avec un champ trié, une Recherche Binaire peut être utilisé, ce qui a log2 N bloquer les accès. Aussi, puisque les données sont triées donné un non-clé le terrain, le reste de la table n'a pas besoin d'être recherché pour des valeurs en double, une fois de plus la valeur est trouvée. Ainsi, l'augmentation de la performance est importante.

Qu'est-ce que l'indexation?

L'indexation est une façon de trier un certain nombre de dossiers sur plusieurs champs. Création d'un index sur un champ dans une table permet de créer une autre structure de données qui détient la valeur du champ, et le pointeur de l'enregistrement auquel il se rapporte. Cette structure d'index est ensuite trié, permettant Binaire des Recherches à effectuer sur celles-ci.

L'inconvénient de l'indexation, c'est que ces indices nécessite de l'espace supplémentaire sur le disque, puisque les index sont stockés dans une table en utilisant le moteur MyISAM, ce fichier permet de rejoindre rapidement les limites de taille du sous-jacent système de fichiers si de nombreux champs de la même table sont indexés.

Comment ça fonctionne?

Tout d'abord, nous allons décrire un exemple de base de données schéma de la table;

Nom du champ type de Données Taille sur le disque
l'identifiant (clé Primaire) Unsigned INT 4 octets
prenom Char(50) 50 octets
nom Char(50) 50 octets
emailAddress Char(100) 100 octets

Note: char a été utilisé à la place de varchar pour permettre pour une précision de taille sur le disque de la valeur. Cette base de données contient cinq millions de lignes, et est indexée. L'exécution de plusieurs requêtes vont maintenant être analysées. Ces sont une requête à l'aide de l' id (triés champ clé) et un en utilisant le prénom (non-clé des ménagères de champ).

Exemple 1

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

Un linéaire de recherche sur le champ id nécessiterait une moyenne de N/2 = 500,000 bloc accède à trouver une valeur étant donné que le champ id est un champ de clé. Mais depuis le champ id est également triés binaire de recherche peut être mené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 drastique.

Maintenant, le prénom de champ est ni triés, donc une recherche binaire est impossible, ni les valeurs uniques, et donc de la table nécessitera la recherche à la fin d' N = 1,000,000 bloquer les accès. C'est à cette situation que l'indexation a pour but de corriger.

Étant donné que l'enregistrement d'index ne contient que le champ indexé et un pointeur vers l'enregistrement d'origine, il est évident qu'il sera plus petit que le multi-field record qu'il indique. De sorte que l'indice lui-même nécessite moins de blocs de disque que la table d'origine, ce qui nécessite donc moins de bloquer l'accès à parcourir. Le schéma d'un index sur le prénom champ est décrit ci-dessous;

Nom du champ type de Données Taille sur le disque
prenom Char(50) 50 octets
(pointeur d'enregistrement) Spécial 4 octets

Remarque: les Pointeurs dans MySQL sont 2, 3, 4 ou 5 octets de longueur en fonction de la taille de la table.

Exemple 2

Compte tenu de notre exemple de base de données r = 5,000,000 des enregistrements avec un indice de longueur d'enregistrement R = 54 octets et à l'aide de 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 nécessaires pour tenir le tableau est N = (r/bfr) = 5000000/18 = 277,778 blocs.

Maintenant, une recherche en utilisant le prénom champ d'utiliser l'index pour améliorer 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 une plus bloquer l'accès à la lecture, portant le total à 19 + 1 = 20 bloquer les accès, bien loin de l'277,778 bloquer les accès requis par la non-indexé table.

Quand doit-il être utilisé?

Étant donné que la création d'un indice requiert un espace disque supplémentaire (277,778 blocs supplémentaires à partir de l'exemple ci-dessus), et que de trop nombreux indices peuvent provoquer des problèmes découlant de tous les systèmes de fichiers des limites de taille, une réflexion approfondie doit être utilisé pour sélectionner les champs à indexer.

Comme les indices ne sont utilisés pour accélérer la recherche d'un champ correspondant dans les dossiers, il va de soi 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. Aussi compte tenu de la nature d'une recherche binaire, la cardinalité ou de l'unicité des données est important. L'indexation sur un champ avec une cardinalité de 2 permettrait de diviser les données en deux, alors qu'une cardinalité de 1 000 reviendrait à environ 1 000 dossiers. Avec une si faible cardinalité de l'efficacité est réduite à un linéaire de tri, et l'optimiseur de requête d'éviter l'utilisation de l'indice si la cardinalité est à moins de 30% du nombre record, ce qui fait de l'index un gaspillage de l'espace.

235voto

Der U Points 715

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

Depuis lors, j'ai appris à mieux comprendre à propos de la baisse de la création d'index: si vous écrivez dans une table (UPDATE ou INSERT) avec un index, vous avez en fait deux de l'écriture des opérations dans le système de fichiers. L'un pour les données de la table et un autre pour les données de l'indice (et le recours de celui-ci (et si en cluster - le recours de la table de données)). Si des tables et des index sont situés sur le même disque dur, et cela coûte de plus en 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)

Toutefois, la définition de deux endroits différents sur deux disques durs de données de l'index et de la table de données peut réduire/éliminer le problème de l'augmentation des coûts de temps. Cela nécessite de définir d'autres groupes de fichiers avec selon les fichiers sur les disques durs et la définition de la table/index emplacement souhaité.

Un autre problème avec l'index est leur fragmentation plus de temps que les données sont insérées. REORGANIZE aide, vous devez écrire les routines de l'avoir fait.

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

e.g:- Si vous avez beaucoup de rivaliser avec l'écrit, mais seulement une soirée de lecture en dehors des heures ouvrables pour les rapports.

Aussi, une différenciation entre les clusters et les index non cluster est plutôt important.

Qui m'a aidé:- Que faites-Cluster et Non de l'index cluster signifie réellement?

222voto

dioshari Points 98

Bien que les autres réponses sont très bon, je dirais que: 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 b-arbre, mais il peut aussi être une table de hachage ou une autre structure de la logique.

Pour plus d'informations je vous recommande cette page: http://www.programmerinterview.com/index.php/database-sql/what-is-an-index/

27voto

dohaivu Points 1016

Voici un tutoriel très bien expliqué de l'index. Je recommande de le lire.
Utiliser l'Index, Luc

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X