Index (base de données) 1107147 31859702 2008-07-24T20:16:35Z Yopai 104934 Création de l'article à partir de zéro {{Ébauche|informatique}} En [[informatique]], et en particulier dans le contexte des [[Base de données|bases de données]], un '''index''' est un élément de redondance que l'on va spécifier pour permettre au [[Système de gestion de base de données]] d'optimiser certaines requêtes. Tout comme l’'''index''' d’un livre va permettre de trouver directement la page traitant d'un sujet donné, l’'''index''' placé sur une [[table (base de données)|table]] va permettre au SGBD d'accéder très rapidement aux enregistrements, selon la valeur d'un ou plusieurs [[Champ_(BDD)|champs]]. ==Types d'index== * L'index le plus couramment implémenté est l'[[Arbre B|Index BTree]]. En stockant les différentes valeurs du champ dans un arbre, le SGBD pourra hiérarchiser les enregistrements d'après un champ dont la plage de valeurs est infinie (ou presque). * Un autre type d'index est l'[[Index Bitmap]]. Il consiste en une simple table indiquant, pour chaque valeur possible du champ, la liste des enregistrements ayant cette valeur pour ce champ. :Cependant, pour être efficace, il nécessite que le SGBD puisse accéder directement à une valeur donnée. Il n'est donc applicable que sur les colonnes pour lesquelles le nombre de valeurs est limitée et ordonné. * On trouve également des index par [[table de hashage]]. L'inconvénient majeur d'un tel index est de ne permettre que les sélections par égalité, puisqu'il ne conserve pas la notion d'ordre. Si ''n'' est le nombre d'enregistrements d'une table, l'utilisation d'une table de hashage équilibrée peut permettre de réduire le nombre d'enregistrements à parcourir à ''vn'', la racine carrée de ''n'' (la table étant alors composée de ''vn'' valeurs de hash accédant chacune à ''vn'' enregistrements). :La même remarque sur l'efficacité existe que pour l'index bitmap : le SGBD doit pouvoir accéder directement à une valeur de hash donnée, sans avoir à parcourir la liste des valeurs de hash possibles. ==Rôle de l'index== Lors de la phase d'[[optimisation]] de la requête, le SGBD va déterminer le ou les '''index''' à utiliser afin d'en accélérer l'exécution. ===Sélection (clause WHERE)=== SELECT * FROM ''table'' WHERE ''champ'' < 10 Sans index, la seule manière que le SGBD possède pour accéder aux données est de parcourir la totalité de la table et de vérifier la condition pour chaque enregistrement. Un index placé sur ''champ'' pourra être parcouru par le SGBD sur les valeurs inférieures à 10 (excepté dans une table de hashage, les valeurs sont ordonnées) ===Jointures=== SELECT * FROM ''table1'', ''table2'' WHERE ''table1''.''champ'' = ''table2''.''champ'' Sans index, le SGBD est obligé de parcourir les deux tables pour faire la jointure (en pratique, il va charger quasiment les 2 tables en mémoire). Avec un index sur ''table1''.''champ'', le SGBD peut parcourir ''table2'' et, pour chaque enregistrement, chercher les enregistrements de ''table1'' qui correspondent. ===Aggrégation=== La structure de l'index permet également de faciliter les tris et aggrégations. SELECT * FROM ''table'' ORDER BY ''champ'' Si ''table'' est indexée sur ''champ'', il sera plus facile pour SGBD de récupérer chaque enregistrement en suivant l'index, que de parcourir la table et la trier en mémoire (à chaque exécution de la requête) SELECT MIN(champ) FROM ''table'' ORDER BY ''champ'' Si ''table'' est indexée sur ''champ'', la valeur cherchée est la première entrée de l'index. ==Construction de l'index== Un index peut : * porter sur la valeur d'un champ, ou bien sur une fonction [[Déterminisme|déterministe]] (dont la valeur de sortie ne dépend que de ses paramètres) sur la valeur d'un ou plusieurs champs. * posséder une ou plusieurs [[dimensions]] (on parle alors d'index '''multi-colonnes'''). ===Exemple=== Imaginons une table Déclaration possédant les champs suivants N° sécu // N° de sécurité sociale. Annee_naissance // Année de naissance du contribuable Revenu // Revenu Frais Reel // montant des frais réels Pour l'exemple : * le premier chiffre du n° de sécu désigne le sexe de l'individu * Le revenu imposable est calculé : ** soit en soustrayant les Frais réels au Revenu (si ceux-ci sont renseignés) ** soit en effectuant un abattement forfaitaire de 10% sur le Revenu On pourra par exemple créer (le langage utilisé est totalement fictif) : * un index sur ( N° sécu ) :'''Exemple de requête utilisant l'index : Contribuable ayant N° sécu = 123456''' * un index sur ( Annee_naissance, Revenu ) :'''Exemple de requête utilisant l'index : Contribuables nés avant 1980, avec un Revenu entre 20 000 et 30 000''' :'''Exemple de requête utilisant l'index : Revenu maximal selon l'année de naissance''' * un index sur ( GAUCHE(N° sécu, 1) ) * un index bi-colonnes ( GAUCHE(N° sécu, 1), SI(Frais_Reel > 0 ALORS Revenu - Frais_Reel SINON Revenu*0.9) ) '':qui permettra par exemple de renvoyer directement (sans avoir à faire de parcours, autre que celui de l'index) les femmes ayant un revenu imposable compris entre 10000 et 40000. ''Ceci n'est qu'un exemple pour illustrer les possibilités d'index; en pratique, sur cet exemple : * on préfèrera stocker le sexe plutôt que de décomposer le champ (notion d'[[atomicité]]) * on utilisera une [[vue]] pour obtenir la valeur d'un champ calculé, et on indexera la vue (pour les SGBD qui le permettent)'' ==Impacts sur les performances en modification== Lors de l'insertion ou de la mise à jour d'un enregistrement de la base, il y a une légère dégradation des performances : le SGBD doit en effet mettre à jour les index pour qu'ils continuent à refléter l'état des enregistrements. Pour cette raison, on s'attachera, lors de la [[conception]] d'une base de données, à définir uniquement les index qui seront utilisés par le système. Ceux-ci ne seront d'ailleurs bien repérés que par une analyse du système (et notamment des mécanismes d'interrogation de la base) en vue de son optimisation. ==Autres formes d'indexation== D'autres types de structure offrent des fonctionnalités d'indexation : * Tables [[cluster|clusterisées]] * [[Vue materialisée]] ==Remarque sur les index multi-colonnes== Dans le cas d'un index multi-colonnes, le SGBD peut "décider" de l'utiliser partiellement, dans l'ordre des colonnes de l'index. En d'autres termes, un index sur des colonnes (c1,c2,c3,c4) peut être utilisé comme un index (c1,c2,c3), (c1,c2) ou (c1). ==Liens externes== * [http://dev.mysql.com/doc/refman/5.0/fr/mysql-indexes.html Comment MySQL utilise les index] == Voir aussi == === Article connexe === *[[Index.dat]] (des [[fichier]]s qui permettent aux [[logiciel]]s de [[Microsoft]] d'accéder rapidement à des informations enregistrées précédemment) {{Portail informatique}} [[Catégorie:Base de données]] [[cs:Index (databáze)]] [[de:Datenbankindex]] [[en:Index (database)]] [[eo:Indekso (datumbazo)]] [[es:Índice (base de datos)]] [[he:אינדקס (מחשב)]] [[it:Indice (database)]] [[ko:인덱스 (데이터베이스)]] [[nl:Index (database)]] [[pl:Indeksowanie]] [[pt:Índice (banco de dados)]] [[ru:Индекс (базы данных)]] [[uk:Індекс бази даних]] [[zh:数据库索引]]