Index (bază de date)

În informatică , în bazele de date , un index este o structură de date utilizată și întreținută de sistemul de gestionare a bazelor de date (SGBD) pentru a-i permite să găsească rapid date. Utilizarea unui index simplifică și grăbește operațiunile de căutare, sortare, alăturare sau agregare efectuate de SGBD.

Indicele plasat pe un tabel va permite SGBD pentru a avea acces la înregistrările foarte repede, în funcție de valoarea unuia sau mai multor domenii .

Principiu

Un index este o structură întreținută automat care facilitează localizarea înregistrărilor într-un fișier. Utilizarea indexurilor se bazează pe următoarea observație: pentru a găsi o carte într-o bibliotecă, în loc să examinați fiecare carte una câte una (care corespunde unei căutări secvențiale ), este mai rapid să consultați catalogul unde sunt clasificate pe subiecte, autor și titlu. Fiecare intrare dintr-un index are o valoare recuperată din date și un indicator către locația sa originală. O înregistrare poate fi astfel găsită cu ușurință prin căutarea locației sale în index.

Un index poate fi comandat, tăiat, dens sau rar:

Un index ordonat conține o listă de valori extrase dintr-un tabel și sortate.
Într-un index hash, valorile sunt transformate printr-o funcție hash .
Într-un index dens, se face referință la toate înregistrările dintr-un tabel.
Într-un index împrăștiat, se face referire doar la o parte din înregistrări.

Indexul principal al unui tabel este primul care este utilizat pentru localizarea înregistrărilor. Un tabel poate conține, de asemenea, indici secundari pe lângă indicele primar. Fiecare tabel poate avea unul sau mai mulți indici. Un index poate proveni dintr-un singur câmp sau poate combina mai multe câmpuri.

Tehnic

Indexurile sunt utilizate de SGBD pentru multe operații. Indexurile facilitează sortarea, găsirea, gruparea și alăturarea. Cea mai comună structură a indicelui este B-arborele . Există alte structuri, dar sunt rareori folosite - ISAM , tabele hash sau bitmap-uri.

structura arborelui: un trunchi de care sunt atașate ramuri cu ramificații și frunze la capăt. Toate căutările se fac începând de la portbagaj. Căutând printre ramuri cea care conține valoarea de găsit, până când ați ajuns la o frunză.

Pentru a accelera operațiunile, arborii indexului sunt înregistrați într-un bloc cu un număr foarte mare de ramificații: Hard disk-uri, pe care sunt înregistrați indexuri, citesc date în blocuri de mai mulți kilobyți și timpul necesar citirii unui bloc este de obicei mult mai mic decât timpul necesar pentru localizarea acestuia. Cu această construcție, căutarea unui record într-un lot de câteva milioane necesită apoi doar 2 sau 3 operațiuni.

Indexurile pot fi adăugate printr-o comandă SQL . Existența indexurilor este crucială pentru a accelera operațiunile de manipulare a datelor. Principalul motiv al dezamăgirii este utilizarea inadecvată a indicilor. Sistemul de gestionare a bazelor de date (abr. DBMS) nu va găsi indexurile necesare pentru a efectua eficient operațiunile solicitate. Motivele utilizării necorespunzătoare sunt că documentația SGBD privind utilizarea indexurilor este adesea vagă și succintă și subliniază dezavantajele lor, mai degrabă decât avantajele lor.

Indicii sunt utilizați în special de optimizatorul de interogare :

Optimizatorul este componenta SGBD care găsește cel mai economic mod de a rula o interogare. Optimizatorul examinează diferitele scenarii posibile și estimează numărul de operațiuni necesare pentru fiecare scenariu, apoi alege scenariul care necesită cel mai puțin. Numărul de operații necesare depinde de prezența indexurilor, precum și de numărul de rânduri din tabel și de distribuția valorilor.

Tipuri de indici

Cea mai comună structură pentru index este arborele B ( arborele b ). Prin stocarea diferitelor valori ale câmpului într-un arbore echilibrat , SGBD va putea acorda prioritate înregistrărilor în funcție de un câmp al cărui interval de valori este infinit (sau aproape).
Un alt tip de index este indexul bitmap . Acesta constă dintr-un tabel simplu care indică, pentru fiecare valoare posibilă a câmpului, lista înregistrărilor care au această valoare pentru acest câmp.

Cu toate acestea, pentru a fi eficient, este nevoie ca SGBD să poată accesa direct o anumită valoare. Prin urmare, se aplică numai coloanelor pentru care numărul de valori este limitat și ordonat.

Există, de asemenea, indexuri după tabelul hash . Dezavantajul major al unui astfel de indice este acela că permite selecții doar prin egalitate, deoarece nu păstrează noțiunea de ordine. Dacă n este numărul de înregistrări dintr-un tabel, utilizarea unui tabel de hash echilibrat poate reduce numărul de înregistrări în care să navigați , rădăcina pătrată a lui n (atunci tabelul este alcătuit din valorile hash-ului care accesează fiecare înregistrare). Aceeași remarcă privind eficiența există și pentru indexul bitmap: SGBD trebuie să poată accesa direct o anumită valoare hash, fără a fi nevoie să treacă prin lista valorilor hash posibile. ${\ displaystyle {\ sqrt {n}}}$ ${\ displaystyle {\ sqrt {n}}}$ ${\ displaystyle {\ sqrt {n}}}$

Impactul asupra performanței modificării

Atunci când introduceți sau actualizați o înregistrare a bazei de date, există o ușoară degradare a performanței: SGBD trebuie într-adevăr să actualizeze indexurile, astfel încât acestea să reflecte în continuare starea înregistrărilor. Din acest motiv, ne vom strădui, atunci când proiectăm o bază de date, să definim doar indexurile care vor fi utilizate de sistem. În plus, acestea vor fi bine identificate numai printr-o analiză a sistemului (și în special a mecanismelor de interogare a bazei de date) în vederea optimizării acestuia.

Alte forme de indexare

Alte tipuri de structuri oferă funcționalități de indexare:

Clustered tabele
Vizualizare materializată

Notă privind indexurile cu mai multe coloane

În cazul unui index cu mai multe coloane, SGBD poate „decide” să îl folosească parțial, în ordinea coloanelor indexului. Cu alte cuvinte, un index pe coloane (c1, c2, c3, c4) poate fi folosit ca index (c1, c2, c3), (c1, c2) sau (c1).

Note și referințe

(ro) Carlos Coronel, Steven Morris și Peter Rob, Sisteme de baze de date: Proiectare, implementare și gestionare , Cengage Learning - 2012, ( ISBN 9781111969608 )
(en) SK Singh, Sisteme de baze de date: concepte, proiectare și aplicații , Pearson Education India - 2009, ( ISBN 9788177585674 )
(en) Gavin Powell, Beginning Database Design , John Wiley & Sons - 2006, ( ISBN 9780764574900 )
(ro) Tapio Lahdenmaki și Mike Leach, Relational Database Index Design and the Optimizers , John Wiley & Sons - 2005, ( ISBN 9780471721369 )
(în) Ken England, Gavin JT Powell, Microsoft SQL Server 2005 Performance Optimization and Tuning Handbook , Digital Press - 2011 ( ISBN 9780080554082 )

linkuri externe

(ro) Cum folosește indexurile MySQL