Index (baze de date)

Această intrare sau secțiune despre subiectul bazelor de date nu menționează sursele necesare sau cei prezenți sunt insuficienți . Puteți îmbunătăți această intrare adăugând citări din surse de încredere în conformitate cu liniile directoare privind utilizarea surselor .

Un index (în câmpul bazei de date ) este o structură de date concepută pentru a îmbunătăți timpul de căutare a datelor ( interogare ).

Dacă un tabel nu are indici, fiecare căutare forțează sistemul să citească toate datele din el. Pe de altă parte, indexul vă permite să reduceți setul de date care trebuie citite pentru a finaliza căutarea.

De exemplu, dacă aveți un set de date dezordonat, puteți crea un „index” al acestuia în ordine alfabetică și puteți utiliza proprietățile ordinii alfabetice pentru a ajunge mai întâi la datele sau datele pe care le căutați. De exemplu, s-ar putea gândi să aplicăm o căutare binară la indexul ordonat pentru a găsi informațiile solicitate într-un timp mai scurt.

De asemenea, indexurile au efecte negative, deoarece fac operațiile de inserare și modificare (actualizare) mai lente și sporesc utilizarea memoriei de masă.

Înainte de a defini pe ce câmpuri să creați indexurile, este necesar să evaluați care sunt cele mai frecvente operațiuni de selecție. Alegerea indexurilor corecte într-o schemă poate îmbunătăți performanța operației de citire cu până la 80%. Instrumentele adecvate pentru descoperirea indexului sunt adesea disponibile ca instrumente DBMS. În special, având în vedere o interogare de selecție (destul de complexă), instrumentul de optimizare a indexului identifică orice index care trebuie creat și face o estimare procentuală a îmbunătățirii care ar putea fi obținută. Dimpotrivă, o alegere greșită poate provoca o degradare a performanței sistemului datorită cheltuielilor generale introduse pentru menținerea informațiilor corecte, de fapt, la fiecare inserare, actualizare și ștergere a înregistrărilor indexate, dbms trebuie să intervină și pe fișierul index ( s).

Un index poate fi gândit sub forma <Ki, Pi> unde Ki este valoarea atributului cheie și Pi este indicatorul către înregistrarea de date. În general, fișierul index este sortat în funcție de valorile câmpului Ki, astfel încât să poată fi efectuată o căutare binară .

Tipurile de index sunt după cum urmează:

• Indici primari: SGBD-urile tind să facă din greșeală indexurile definite pe atribute de valoare unice (adică pe o cheie) se încadrează în această categorie, în realitate indexurile primare, spre deosebire de cele secundare, conțin direct datele (sau sunt pe fișiere ordonate pe aceleași câmpuri pe care este definit indexul în sine). Acestea sunt numite primare, deoarece nu numai că garantează accesul pe baza cheii, ci și locațiile fizice necesare pentru stocarea datelor.
• Indici secundari: sunt indici care au scopul de a facilita accesul la date fără a conține datele în sine. Ele sunt în general definite pe atribute care pot avea valori repetate.
• Indexuri grupate: Acestea sunt indexurile definite pe atribut în funcție de ale căror valori este sortat fișierul de date
• Indici necluzionați: Acestea sunt indexurile definite pe atribut în funcție de ale căror valori nu este sortat fișierul de date
• Indici densi: Acestea sunt indicii al căror număr de perechi <Ki, Pi> este egal cu numărul de valori cheie ale înregistrărilor
• Indici rari: Acestea sunt indicii al căror număr de perechi <Ki, Pi> este mai mic decât numărul de valori cheie ale înregistrărilor

Există diferite tipuri de indici pe baza tipului de SGBD , a tipului de tabel utilizat, de exemplu: hash, btree , rtree , etc ...

Utilizare

Suport pentru căutare rapidă

Majoritatea programelor de baze de date includ tehnologie de indexare care permite căutarea temporală sub-liniară pentru a îmbunătăți performanța, deoarece căutarea liniară este ineficientă pentru bazele de date mari.

Să presupunem că o bază de date conține N elemente de date și că trebuie recuperată pe baza valorii unuia dintre câmpuri. O implementare simplă recuperează și examinează fiecare element pe baza testului. Dacă există un singur element de potrivire, se poate opri când găsește acel element, dar dacă există mai multe potriviri, trebuie să testeze totul. Aceasta înseamnă că numărul de operații în cazul mediu este O (N) sau timpul liniar. Deoarece bazele de date pot conține multe obiecte și întrucât căutarea este o operație obișnuită, este adesea de dorit să îmbunătățim performanța.

Un index este orice structură de date care îmbunătățește performanța căutării. Există multe structuri de date diferite utilizate în acest scop. Există compromisuri complexe de proiectare care implică performanța căutării, dimensiunea indexului și performanța actualizării indexului. Multe modele de indexuri arată performanța de căutare logaritmică (O (log (N))), iar performanța plată (O (1)) poate fi obținută în unele aplicații.

Verificarea constrângerilor bazei de date

Indexurile sunt utilizate pentru a verifica constrângerile bazei de date, cum ar fi UNIC, EXCLUZIE, CHEIE PRIMARĂ și CHEIE STRĂINĂ. Un index poate fi declarat ca UNIC, ceea ce creează o constrângere implicită asupra tabelului de bază. Sistemele de baze de date creează de obicei implicit un index pe un set de coloane declarate PRIMARY KEY, iar unele sunt capabile să utilizeze un index deja existent pentru a verifica această constrângere. Multe sisteme de baze de date necesită indexarea atât a seturilor de coloane referențiate, cât și a celor referite într-o constrângere FOREIGN KEY, îmbunătățind astfel performanța inserțiilor, actualizărilor și ștergerilor din tabelele care participă la constrângere.

Unele sisteme de baze de date acceptă o constrângere EXCLUSION care asigură că, pentru o înregistrare nou inserată sau actualizată, un anumit predicat este invalid pentru orice altă înregistrare. Aceasta poate fi utilizată pentru a implementa o constrângere ONE (cu predicat de egalitate) sau constrângeri mai complexe, cum ar fi asigurarea faptului că nu sunt stocate în tabel intervale de timp suprapuse sau obiecte geometrice intersectate. Pentru a verifica această constrângere, aveți nevoie de un index care să susțină căutarea rapidă a înregistrărilor care satisfac predicatul ^[1] .

Arhitectura indexului și metodele de indexare

Dezagrupat („non-grupat”)

Datele sunt prezente în ordine arbitrară, dar ordinea logică este specificată de index. Rândurile de date pot fi distribuite în întregul tabel, indiferent de valoarea coloanei sau a expresiei indexate. Arborele index non-grupat conține cheile index în ordine sortată, cu nivelul frunzei indexului conținând indicatorul către înregistrare (numărul paginii și rândului din pagina de date din motoarele organizate după pagină; decalarea liniei în motoarele organizate după fișier ).

Într-un indice grupat

• Ordinea fizică a rândurilor nu este aceeași cu ordinea indexului.
• Coloanele indexate sunt de obicei coloane cheie non-primare utilizate în clauzele JOIN, WHERE și ORDER BY.

Într-un tabel de baze de date poate exista mai mult de un index negroupat.

Grupate („grupate”)

Clusterizarea modifică blocul de date într-o anumită ordine distinctă pentru a se potrivi cu indexul, rezultând stocarea datelor în rând în ordine. Prin urmare, numai un singur index grupat poate fi creat pe o anumită tabelă de baze de date. Indicii grupați pot crește dramatic viteza generală de recuperare, dar de obicei numai atunci când datele sunt accesate secvențial în aceeași ordine sau inversă ca indexul grupat sau când este selectată o gamă de articole.

Deoarece înregistrările fizice sunt în această ordine de sortare a discului, următorul element de rând din secvență este imediat înainte sau după ultima, deci sunt necesare mai puține citiri de blocuri ale datelor. Prin urmare, caracteristica principală a unui index grupat este ordonarea rândurilor de date fizice pe baza blocurilor de index care le indică. Unele baze de date separă datele și blocurile indexate în fișiere separate, altele plasează două blocuri de date complet diferite în aceleași fișiere fizice.

Grup („cluster”)

Când mai multe baze de date și mai multe tabele sunt unite, acesta se numește cluster (nu trebuie confundat cu indexul grupat descris mai sus) care se traduce prin „grup”. Înregistrările pentru tabelele care partajează valoarea unei chei de cluster trebuie stocate împreună în aceleași blocuri de date sau în vecinătate. Acest lucru poate îmbunătăți îmbinările acestor tabele pe cheia clusterului, deoarece înregistrările de potrivire sunt stocate împreună și este necesară mai puțină I / O pentru a le localiza ^[2] . Configurația clusterului definește aspectul datelor din tabelele care fac parte din cluster. Un cluster poate fi codat cu un index B-Tree sau un tabel hash. Blocul de date în care este stocată înregistrarea tabelului este definit de valoarea cheii cluster.

Ordinea coloanelor

Ordinea în care definiția indexului definește coloanele este importantă. Puteți prelua un set de identificatori de rând folosind doar prima coloană indexată. Cu toate acestea, nu este posibil sau eficient (pe majoritatea bazelor de date) să extrageți setul de identificatori de rând utilizând doar a doua sau cea de sus coloană indexată.

De exemplu, într-o agendă telefonică organizată mai întâi după oraș, apoi după nume și apoi după nume, într-un anumit oraș, puteți extrage cu ușurință lista tuturor numerelor de telefon. Cu toate acestea, ar fi foarte plictisitor să găsiți toate numerele de telefon pentru un anumit nume de familie. Ar trebui să căutați în secțiunea fiecărui oraș intrări cu acel nume de familie. Unele baze de date pot face acest lucru, altele pur și simplu nu vor folosi indexul.

În exemplul agendei telefonice cu un index compus creat pe coloane ( city, last_name, first_name ), dacă căutați oferind valori exacte pentru toate cele trei câmpuri, timpul de căutare este minim, dar dacă furnizați valorile Numai pentru city și first_name , căutarea folosește doar câmpul city pentru a prelua toate înregistrările potrivite. Apoi, o căutare secvențială verifică potrivirea cu first_name . Deci, pentru a îmbunătăți performanța, trebuie să vă asigurați că indexul este creat în ordinea coloanelor de căutare.

Aplicații și limitări

Indicii sunt utili pentru multe aplicații, dar au unele limitări. Luați în considerare următoarea declarație SQL: SELECT first_name FROM people WHERE last_name = 'Smith'; . Pentru a procesa această afirmație fără un index, software-ul bazei de date trebuie să examineze coloana last_name de pe fiecare rând al tabelului (aceasta este cunoscută sub numele de scanare completă a tabelului). Cu un index, baza de date urmează pur și simplu structura de date a indexului (de obicei un arbore B) până când se găsește intrarea Smith; acest lucru este mult mai puțin costisitor din punct de vedere al calculului decât o scanare completă a tabelului.

Luați în considerare această SELECT email_address FROM customers WHERE email_address LIKE '%@wikipedia.org'; SQL: SELECT email_address FROM customers WHERE email_address LIKE '%@wikipedia.org'; . Această interogare va produce o adresă de e-mail pentru fiecare client a cărui adresă de e-mail se termină cu „@ wikipedia.org”, dar chiar dacă coloana adresă_e-mail a fost indexată, baza de date trebuie să efectueze o scanare completă a indexului. Acest lucru se datorează faptului că indexul este construit pe presupunerea că cuvintele merg de la stânga la dreapta. Cu un wildcard la începutul termenului de căutare, software-ul bazei de date nu poate utiliza structura de date a indexului subiacent (cu alte cuvinte, clauza WHERE nu poate fi selectată ). Această problemă poate fi rezolvată prin adăugarea unui alt index creat pe reverse(email_address) și o interogare SQL ca aceasta: SELECT email_address FROM customers WHERE reverse(email_address) LIKE reverse('%@wikipedia.org'); . Aceasta plasează caracterul wildcard în extrema dreaptă a interogării (acum gro.aidepikiw@%), pe care indexul invers (adresa_e-mail) îl poate satisface.

Când sunt folosite caractere wildcard pe ambele părți ale cuvântului de căutare, cum ar fi % wikipedia.org% , indexul disponibil în acest câmp nu este utilizat. Mai degrabă, se efectuează doar o căutare secvențială, care necesită timp O (N).

Tipuri de indici

Indice bitmap

Un index bitmap este un tip special de indexare care stochează majoritatea datelor sale sub formă de matrice de biți (bitmap-uri) și răspunde la majoritatea interogărilor efectuând operații logice bit-bit pe aceste bitmap-uri. Cei mai utilizați indici, cum ar fi copacii B +, sunt mai eficienți dacă valorile pe care le indexează nu se repetă sau se repetă de un număr limitat de ori. În schimb, indicele bitmap este conceput pentru cazurile în care valorile unei variabile se repetă foarte frecvent. De exemplu, câmpul de gen dintr-o bază de date pentru clienți conține de obicei cel mult trei valori distincte: masculin, feminin sau necunoscut (neînregistrat). Pentru astfel de variabile, indicele bitmap poate avea un avantaj semnificativ de performanță față de copacii utilizați în mod obișnuit.

Indicele dens

Un index dens în bazele de date este un fișier cu perechi de chei și pointeri pentru fiecare înregistrare din fișierul de date. Fiecare cheie din acest fișier este asociată cu un anumit indicator la o înregistrare din fișierul de date sortate. În indexurile grupate cu chei duplicate, indexul dens indică prima înregistrare cu acea cheie ^[3] .

Indicele împrăștiat

Un index rar în bazele de date este un fișier cu perechi de chei și pointeri pentru fiecare bloc din fișierul de date. Fiecare cheie din acest fișier este asociată cu un anumit indicator al blocului din fișierul de date sortate. În indexurile grupate cu chei duplicate, indexul rar indică cea mai mică cheie de căutare din fiecare bloc.

Indice invers

Un index de cheie inversă inversează valoarea cheii înainte de a o insera în index. De exemplu, valoarea 24538 devine 83542 în index. Inversarea valorii cheii este utilă în special pentru indexarea datelor, cum ar fi numerele de secvență, unde valorile noi ale cheii cresc monoton.

Index principal

Indexul principal conține câmpurile cheie ale tabelului și un pointer către câmpurile non-cheie ale tabelului. Indexul principal este creat automat atunci când tabelul este creat în baza de date.

Indicele secundar

Este folosit pentru indexarea câmpurilor care nu sunt nici câmpuri de sortare, nici câmpuri cheie (nu există nicio garanție că fișierul este organizat pe câmpul cheie sau câmpul cheie primar). O intrare index pentru fiecare tuplu din fișierul de date (index dens) conține valoarea atributului indexat și a indicatorului către bloc sau înregistrare.

Implementări index

Indexurile pot fi implementate folosind o varietate de structuri de date. Indicii populari includ copaci echilibrați, copaci B + și hashuri ^[4] .

În Microsoft SQL Server, nodul frunză index index grupat corespunde datelor reale, nu pur și simplu un indicator către datele care se află în altă parte, așa cum se întâmplă cu un index grupat ^[5] . Fiecare relație poate avea un singur index grupat și mulți indici grupați ^[6] .

Controlul concurenței indexului

De obicei, un index este accesat în același timp de mai multe tranzacții și procese și, prin urmare, este necesar controlul concurenței. În timp ce indicii pot utiliza, în principiu, metode comune de verificare a concurenței bazei de date, există metode specializate de verificare a concurenței pentru indici, care sunt aplicate alături de metode comune pentru o îmbunătățire substanțială a performanței.

Indicele de acoperire

În majoritatea cazurilor, un index este utilizat pentru a localiza rapid înregistrările de date din care sunt citite datele necesare. Cu alte cuvinte, indexul este utilizat numai pentru a localiza înregistrările de date în tabel și nu pentru a returna datele.

Un indice de acoperire este un caz special în care indexul în sine conține câmpurile de date necesare și poate răspunde la datele solicitate.

Luați în considerare următorul tabel (alte câmpuri omise):

Pentru a găsi numele pentru ID 13, este util un index pe (ID), dar înregistrarea trebuie totuși citită pentru a obține numele. Cu toate acestea, un index pe (ID, Nume) conține câmpul de date necesar și elimină necesitatea de a căuta înregistrarea.

Rapoartele de acoperire sunt fiecare pentru un anumit tabel. Interogările care ÎNREGISTRĂ / accesează mai multe tabele pot lua în considerare acoperirea indexului pentru mai multe dintre aceste tabele.

Un indice de acoperire poate accelera foarte mult recuperarea datelor, dar ar putea fi mare datorită tastelor suplimentare, care încetinesc introducerea și actualizarea datelor. Pentru a reduce această dimensiune a indexului, unele sisteme vă permit să includeți câmpuri non-cheie în index. Câmpurile non-cheie nu fac parte din sortarea indexului, ci sunt incluse numai la nivelul frunzei, permițând un index de acoperire cu o dimensiune a indexului mai mică.

Standardizare

Niciun standard nu definește modul de creare a indexurilor, deoarece standardul ISO SQL nu acoperă aspectele fizice. Indexurile sunt una dintre părțile fizice ale proiectării bazei de date, printre altele ca stocare (spații tabelare sau grupuri de fișiere). Furnizorii RDBMS oferă toți o sintaxă CREATE INDEX cu unele opțiuni specifice, în funcție de capacitățile software-ului lor.

Notă

Portal IT : accesați intrările Wikipedia care se ocupă cu IT