Bună, Habr! Vă prezint atenției o traducere a articolului
„Cum funcționează o bază de date relațională”.

Când vine vorba de baze de date relaționale, nu pot să nu cred că lipsește ceva. Sunt folosite peste tot. Există multe baze de date diferite disponibile, de la mic și util SQLite până la puternicul Teradata. Dar există doar câteva articole care explică cum funcționează baza de date. Puteți căuta singur folosind „cum doesarerelationaldatabasework” pentru a vedea cât de puține rezultate sunt. Mai mult, aceste articole sunt scurte. Dacă sunteți în căutarea celor mai noi tehnologii buzzy (BigData, NoSQL sau JavaScript), veți găsi mai multe articole aprofundate care explică modul în care funcționează.

Sunt bazele de date relaționale prea vechi și prea plictisitoare pentru a fi explicate în afara cursurilor universitare, lucrărilor de cercetare și cărților?

Ca dezvoltator, urăsc să folosesc ceva ce nu înțeleg. Și dacă bazele de date au fost folosite de mai bine de 40 de ani, trebuie să existe un motiv. De-a lungul anilor, am petrecut sute de ore pentru a înțelege cu adevărat aceste cutii negre ciudate pe care le folosesc în fiecare zi. Baze de date relaționale foarte interesant pentru că ei bazată pe concepte utile și reutilizabile. Dacă sunteți interesat să înțelegeți o bază de date, dar nu ați avut niciodată timpul sau înclinația să vă aprofundați în acest subiect amplu, ar trebui să vă bucurați de acest articol.

Deși titlul acestui articol este explicit, scopul acestui articol nu este de a înțelege cum să folosiți baza de date. Prin urmare, ar trebui să știți deja cum să scrieți o cerere simplă de conectare și interogări de bază BRUT; altfel s-ar putea să nu înțelegi acest articol. Este singurul lucru pe care trebuie să-l știi, restul îți voi explica.

Voi începe cu câteva elemente de bază ale informaticii, cum ar fi complexitatea în timp a algoritmilor (BigO). Știu că unii dintre voi urăsc acest concept, dar fără el nu veți putea înțelege complexitățile din baza de date. Deoarece acesta este un subiect uriaș, Mă voi concentra asupra ceea ce cred eu este important: cum procesează baza de date SQL Anchetă. Am să vă prezint doar concepte de bază ale bazelor de dateastfel încât la sfârșitul articolului să aveți o idee despre ce se întâmplă sub capotă.

Deoarece acesta este un articol lung și tehnic care implică o mulțime de algoritmi și structuri de date, luați-vă timp pentru a-l citi. Unele concepte pot fi greu de înțeles; le poți sări peste ele și totuși ai ideea generală.

Pentru cei mai cunoscători dintre voi, acest articol este împărțit în 3 părți:

• Prezentare generală a componentelor bazei de date de nivel scăzut și de nivel înalt
• Prezentare generală a procesului de optimizare a interogărilor
• Prezentare generală a gestionării tranzacțiilor și a pool-ului de buffer

Înapoi la elementele de bază

Cu ani în urmă (într-o galaxie departe, departe...), dezvoltatorii trebuiau să știe exact numărul de operațiuni pe care le codificau. Își cunoșteau algoritmii și structurile de date pe de rost, deoarece nu își puteau permite să irosească CPU și memoria computerelor lor lente.

În această parte, vă voi aminti câteva dintre aceste concepte, deoarece sunt esențiale pentru înțelegerea bazei de date. Voi introduce și conceptul indexul bazei de date.

O(1) vs O(n2)

În zilele noastre, multor dezvoltatori nu le pasă de complexitatea timpului a algoritmilor... și au dreptate!

Dar când ai de-a face cu o mulțime de date (nu vorbesc cu mii) sau dacă te chinui în milisecunde, devine esențial să înțelegi acest concept. Și după cum vă puteți imagina, bazele de date trebuie să facă față ambelor situații! Nu te voi face să petreci mai mult timp decât este necesar pentru a înțelege ideea. Acest lucru ne va ajuta să înțelegem conceptul de optimizare bazată pe costuri mai târziu (costa bazat optimizare).

Concept

Complexitatea temporală a algoritmului folosit pentru a vedea cât timp va dura un algoritm pentru a se finaliza pentru o anumită cantitate de date. Pentru a descrie această complexitate, folosim notația matematică mare O. Această notație este folosită cu o funcție care descrie de câte operații are nevoie un algoritm pentru un număr dat de intrări.

De exemplu, când spun „acest algoritm are complexitatea O(some_function())”, înseamnă că algoritmul necesită operațiuni some_function(a_certain_amount_of_data) pentru a procesa o anumită cantitate de date.

În acest caz, Nu cantitatea de date contează**, in caz contrar ** cum crește numărul de operațiuni odată cu creșterea volumului de date. Complexitatea timpului nu oferă un număr exact de operațiuni, dar este o modalitate bună de a estima timpul de execuție.

În acest grafic puteți vedea numărul de operații față de cantitatea de date de intrare pentru diferite tipuri de complexități de timp ale algoritmului. Am folosit o scară logaritmică pentru a le afișa. Cu alte cuvinte, cantitatea de date crește rapid de la 1 la 1 miliard. Putem vedea că:

• O(1) sau complexitatea constantă rămâne constantă (altfel nu s-ar numi complexitate constantă).
• O(log(n)) rămâne scăzut chiar și cu miliarde de date.
• Cea mai mare dificultate - O(n2), unde numărul de operațiuni crește rapid.
• Celelalte două complicații cresc la fel de repede.

exemple

Cu o cantitate mică de date, diferența dintre O(1) și O(n2) este neglijabilă. De exemplu, să presupunem că aveți un algoritm care trebuie să proceseze 2000 de elemente.

• Algoritmul O(1) vă va costa 1 operație
• Algoritmul O(log(n)) vă va costa 7 operații
• Algoritmul O(n) vă va costa 2 de operații
• Algoritmul O(n*log(n)) vă va costa 14 de operații
• Algoritmul O(n2) vă va costa 4 de operații

Diferența dintre O(1) și O(n2) pare mare (4 milioane de operații) dar vei pierde maxim 2 ms, doar timpul să clipești din ochi. Într-adevăr, procesoarele moderne pot procesa sute de milioane de operații pe secundă. Acesta este motivul pentru care performanța și optimizarea nu sunt o problemă în multe proiecte IT.

După cum am spus, este încă important să cunoaștem acest concept atunci când lucrați cu cantități uriașe de date. Dacă de data aceasta algoritmul trebuie să proceseze 1 de elemente (ceea ce nu este atât de mult pentru o bază de date):

• Algoritmul O(1) vă va costa 1 operație
• Algoritmul O(log(n)) vă va costa 14 operații
• Algoritmul O(n) vă va costa 1 de operații
• Algoritmul O(n*log(n)) vă va costa 14 de operații
• Algoritmul O(n2) vă va costa 1 de operații

Nu am făcut calculul, dar aș spune că cu algoritmul O(n2) ai timp să bei o cafea (chiar și două!). Dacă mai adaugi 0 la volumul de date, vei avea timp să tragi un pui de somn.

Să mergem mai adânc

Pentru informarea dumneavoastră:

• O căutare bună a tabelului hash găsește un element în O(1).
• Căutarea unui arbore bine echilibrat produce rezultate în O(log(n)).
• Căutarea într-o matrice produce rezultate în O(n).
• Cei mai buni algoritmi de sortare au complexitatea O(n*log(n)).
• Un algoritm de sortare prost are complexitatea O(n2).

Notă: În următoarele părți vom vedea acești algoritmi și structuri de date.

Există mai multe tipuri de complexitate temporală a algoritmului:

• scenariu de caz mediu
• cel mai bun scenariu
• și cel mai rău scenariu

Complexitatea timpului este adesea cel mai rău caz.

Vorbeam doar despre complexitatea temporală a algoritmului, dar complexitatea se aplică și la:

• consumul de memorie al algoritmului
• algoritm de consum I/O disc

Desigur, există complicații mai grave decât n2, de exemplu:

• n4: asta este groaznic! Unii dintre algoritmii menționați au această complexitate.
• 3n: asta e si mai rau! Unul dintre algoritmii pe care îi vom vedea la mijlocul acestui articol are această complexitate (și este de fapt folosit în multe baze de date).
• factorial n: nu veți obține niciodată rezultatele chiar și cu o cantitate mică de date.
• nn: Dacă întâmpinați această complexitate, ar trebui să vă întrebați dacă acesta este într-adevăr domeniul dvs. de activitate...

Notă: nu ți-am dat definiția reală a denumirii O mare, ci doar o idee. Puteți citi acest articol la adresa Wikipedia pentru definiția reală (asimptotică).

MergeSort

Ce faci când trebuie să sortezi o colecție? Ce? Apelați funcția sort()... Ok, răspuns bun... Dar pentru o bază de date, trebuie să înțelegeți cum funcționează această funcție sort().

Există mai mulți algoritmi de sortare buni, așa că mă voi concentra pe cei mai importanți: sortare îmbinare. Este posibil să nu înțelegeți de ce sortarea datelor este utilă în acest moment, dar ar trebui să urmați partea de optimizare a interogărilor. Mai mult, înțelegerea sortării de îmbinare ne va ajuta să înțelegem ulterior operația comună de unire a bazei de date numită îmbina alătura (asociație de fuziune).

Combina

La fel ca mulți algoritmi utili, sortarea prin îmbinare se bazează pe un truc: combinarea a 2 tablouri sortate de dimensiunea N/2 într-un tablou sortat cu N elemente costă doar N operațiuni. Această operație se numește fuziune.

Să vedem ce înseamnă asta cu un exemplu simplu:

Această figură arată că pentru a construi matricea finală sortată cu 8 elemente, trebuie doar să iterați o dată peste cele 2 matrice cu 4 elemente. Deoarece ambele tablouri cu 4 elemente sunt deja sortate:

• 1) comparați ambele elemente curente în două matrice (la început curent = primul)
• 2) apoi luați cel mai mic pentru al pune într-o matrice de 8 elemente
• 3) și treceți la următorul element din matrice unde ați luat cel mai mic element
• și repetați 1,2,3 până ajungeți la ultimul element al uneia dintre matrice.
• Apoi luați elementele rămase ale celeilalte matrice pentru a le pune într-o matrice de 8 elemente.

Acest lucru funcționează deoarece ambele matrice cu 4 elemente sunt sortate și, prin urmare, nu trebuie să „reveniți” în acele matrice.

Acum că înțelegem trucul, iată pseudocodul meu pentru îmbinare:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

Sortare prin îmbinare împarte o problemă în probleme mai mici și apoi găsește rezultatele problemelor mai mici pentru a obține rezultatul problemei inițiale (notă: acest tip de algoritm se numește împărțire și cuceri). Dacă nu înțelegeți acest algoritm, nu vă faceți griji; Nu am inteles prima data cand l-am vazut. Dacă vă poate ajuta, văd acest algoritm ca un algoritm în două faze:

• Faza de divizare, în care matricea este împărțită în matrice mai mici
• Faza de sortare este cea în care matricele mici sunt combinate (folosind uniunea) pentru a forma o matrice mai mare.

Faza de divizare

În etapa de divizare, matricea este împărțită în rețele unitare în 3 pași. Numărul formal de pași este log(N) (deoarece N=8, log(N) = 3).

De unde știu asta?

Sunt un geniu! Într-un cuvânt - matematică. Ideea este că fiecare pas împarte dimensiunea matricei originale cu 2. Numărul de pași este de câte ori poți împărți matricea originală în două. Aceasta este definiția exactă a unui logaritm (baza 2).

Faza de sortare

În faza de sortare, începeți cu matrice unitare (cu un singur element). În timpul fiecărui pas aplicați mai multe operațiuni de îmbinare, iar costul total este N = 8 operațiuni:

• În prima etapă ai 4 fuziuni care costă câte 2 operațiuni
• În al doilea pas aveți 2 fuziuni care costă câte 4 operațiuni fiecare
• În al treilea pas aveți 1 fuziune care costă 8 operațiuni

Deoarece există log(N) pași, costul total N * operațiuni log(N)..

Avantajele sortării prin îmbinare

De ce este acest algoritm atât de puternic?

Pentru că:

• Îl puteți modifica pentru a reduce amprenta memoriei, astfel încât să nu creați matrice noi, ci să modificați direct matricea de intrare.

Notă: acest tip de algoritm este numit in-loc (sortare fără memorie suplimentară).

• Îl puteți modifica pentru a utiliza spațiu pe disc și o cantitate mică de memorie în același timp, fără a suporta o suprasarcină semnificativă la I/O pe disc. Ideea este să încărcați în memorie doar acele părți care sunt în prezent procesate. Acest lucru este important atunci când trebuie să sortați un tabel de mai mulți gigaocteți cu doar un buffer de memorie de 100 de megaocteți.

Notă: acest tip de algoritm este numit sortare externă.

• Îl puteți schimba pentru a rula pe mai multe procese/thread-uri/servere.

De exemplu, sortarea de îmbinare distribuită este una dintre componentele cheie Hadoop (care este o structură în big data).

• Acest algoritm poate transforma plumbul în aur (într-adevăr!).

Acest algoritm de sortare este folosit în majoritatea (dacă nu în toate) bazele de date, dar nu este singurul. Dacă vrei să afli mai multe, poți citi asta muncă de cercetare, care discută avantajele și dezavantajele algoritmilor obișnuiți de sortare a bazelor de date.

Array, Tree și Hash Table

Acum că înțelegem ideea de complexitate și sortare a timpului, ar trebui să vă spun despre 3 structuri de date. Acest lucru este important pentru că ei stau la baza bazelor de date moderne. Voi introduce și conceptul indexul bazei de date.

mulțime

O matrice bidimensională este cea mai simplă structură de date. Un tabel poate fi considerat ca o matrice. De exemplu:

Această matrice bidimensională este un tabel cu rânduri și coloane:

• Fiecare linie reprezintă o entitate
• Coloanele stochează proprietăți care descriu entitatea.
• Fiecare coloană stochează date de un anumit tip (întreg, șir, dată...).

Acest lucru este convenabil pentru stocarea și vizualizarea datelor, cu toate acestea, atunci când trebuie să găsiți o anumită valoare, aceasta nu este potrivită.

De exemplu, dacă doriți să găsiți toți bărbații care lucrează în Regatul Unit, ar trebui să vă uitați la fiecare rând pentru a determina dacă acel rând aparține Regatului Unit. Vă va costa N tranzacțiiUnde N - numărul de linii, ceea ce nu este rău, dar ar putea exista o cale mai rapidă? Acum este timpul să facem cunoștință cu copacii.

Notă: Cele mai multe baze de date moderne oferă matrice extinse pentru stocarea eficientă a tabelelor: tabele organizate în heap și tabele organizate cu index. Dar acest lucru nu schimbă problema găsirii rapide a unei anumite condiții într-un grup de coloane.

Arborele și indexul bazei de date

Un arbore binar de căutare este un arbore binar cu o proprietate specială, cheia de la fiecare nod trebuie să fie:

• mai mare decât toate cheile stocate în subarborele din stânga
• mai puțin decât toate cheile stocate în subarborele din dreapta

Să vedem ce înseamnă asta vizual

Idee

Acest arbore are N = 15 elemente. Să presupunem că caut 208:

• Încep de la rădăcina a cărei cheie este 136. De la 136<208, mă uit la subarborele din dreapta al nodului 136.
• 398>208, prin urmare, mă uit la subarborele din stânga al nodului 398
• 250>208, prin urmare, mă uit la subarborele din stânga al nodului 250
• 200<208, prin urmare mă uit la subarborele drept al nodului 200. Dar 200 nu are subarborele drept, valoare nu există (pentru că dacă există, va fi în subarborele din dreapta 200).

Acum să presupunem că caut 40

• Încep de la rădăcina a cărei cheie este 136. Deoarece 136 > 40, mă uit la subarborele din stânga al nodului 136.
• 80 > 40, prin urmare mă uit la subarborele din stânga al nodului 80
• 40= 40, nodul există. Obțin ID-ul rândului din interiorul nodului (nu este afișat în imagine) și caut în tabel ID-ul rândului dat.
• Cunoașterea ID-ului rândului îmi permite să știu exact unde sunt datele din tabel, astfel încât să le pot recupera instantaneu.

În cele din urmă, ambele căutări mă vor costa numărul de niveluri din interiorul arborelui. Dacă citiți cu atenție partea despre sortare de îmbinare, ar trebui să vedeți că există niveluri log(N). Se dovedește, jurnalul costurilor de căutare (N), nu-i rău!

Să revenim la problema noastră

Dar acest lucru este foarte abstract, așa că să revenim la problema noastră. În loc de un simplu întreg, imaginați-vă un șir care reprezintă țara cuiva din tabelul anterior. Să presupunem că aveți un arbore care conține câmpul „țară” (coloana 3) din tabel:

• Dacă vrei să știi cine lucrează în Marea Britanie
• te uiți la copac pentru a obține nodul care reprezintă Marea Britanie
• în interiorul „UKnode” veți găsi locația înregistrărilor lucrătorilor din Regatul Unit.

Această căutare va costa log(N) operațiuni în loc de N operațiuni dacă utilizați direct matricea. Ceea ce tocmai ai prezentat a fost indexul bazei de date.

Puteți construi un arbore index pentru orice grup de câmpuri (șir, număr, 2 linii, număr și șir, dată...) atâta timp cât aveți o funcție de comparare a cheilor (adică grupuri de câmpuri), astfel încât să puteți seta ordine printre chei (ceea ce este cazul oricăror tipuri de bază din baza de date).

B+TreeIndex

În timp ce acest arbore funcționează bine pentru a obține o anumită valoare, există o mare problemă atunci când aveți nevoie obține mai multe elemente între două valori. Acest lucru va costa O(N) deoarece va trebui să vă uitați la fiecare nod din arbore și să verificați dacă este între aceste două valori (de exemplu, cu o parcurgere ordonată a arborelui). Mai mult, această operațiune nu este prietenoasă cu I/O pe disc, deoarece trebuie să citiți întregul arbore. Trebuie să găsim o modalitate de a executa eficient cerere de interval. Pentru a rezolva această problemă, bazele de date moderne folosesc o versiune modificată a arborelui anterior numită B+Tree. Într-un arbore B+Tree:

• doar nodurile cele mai de jos (frunze) stocați informații (locația rândurilor în tabelul aferent)
• restul nodurilor sunt aici pentru rutare la nodul corect în timpul căutării.

După cum puteți vedea, există mai multe noduri aici (de două ori). Într-adevăr, aveți noduri suplimentare, „noduri de decizie”, care vă vor ajuta să găsiți nodul corect (care stochează locația rândurilor în tabelul asociat). Dar complexitatea căutării este încă O(log(N)) (mai există un singur nivel). Marea diferență este că nodurile de la nivelul inferior sunt conectate la succesorii lor.

Cu acest B+Tree, dacă căutați valori între 40 și 100:

• Trebuie doar să căutați 40 (sau cea mai apropiată valoare după 40 dacă 40 nu există) așa cum ați făcut cu arborele anterior.
• Apoi strângeți 40 de moștenitori folosind legături directe ale moștenitorilor până când ajungeți la 100.

Să presupunem că găsiți M succesori și arborele are N noduri. Găsirea unui anumit nod costă log(N) ca arborele anterior. Dar odată ce obțineți acest nod, veți obține succesori M în operațiunile M cu referințe la succesorii lor. Această căutare costă doar M+log(N) operații comparativ cu N operații din arborele anterior. Mai mult, nu trebuie să citiți arborele complet (doar M+log(N) noduri), ceea ce înseamnă mai puțină utilizare a discului. Dacă M este mic (de exemplu, 200 de rânduri) și N este mare (1 de rânduri), va fi o diferență MARE.

Dar există noi probleme aici (din nou!). Dacă adăugați sau ștergeți un rând în baza de date (și, prin urmare, în indexul B+Tree asociat):

• trebuie să mențineți ordinea între nodurile din interiorul unui B+Tree, altfel nu veți putea găsi nodurile în interiorul unui arbore nesortat.
• trebuie să păstrați numărul minim posibil de niveluri în B+Tree, altfel complexitatea timpului O(log(N)) devine O(N).

Cu alte cuvinte, B+Tree trebuie să fie auto-ordonat și echilibrat. Din fericire, acest lucru este posibil cu operațiuni inteligente de ștergere și inserare. Dar acest lucru are un cost: inserările și ștergerile într-un arbore B+ costă O(log(N)). De aceea unii dintre voi ați auzit asta folosirea prea multor indici nu este o idee bună. Într-adevăr, încetiniți inserarea/actualizarea/ștergerea rapidă a unui rând dintr-un tabeldeoarece baza de date trebuie să actualizeze indicii tabelului folosind o operație costisitoare O(log(N)) pentru fiecare index. Mai mult, adăugarea de indici înseamnă mai multă sarcină de lucru pentru manager de tranzacții (va fi descris la sfârșitul articolului).

Pentru mai multe detalii, puteți vedea articolul Wikipedia pe B+Copac. Dacă doriți un exemplu de implementare a B+Tree într-o bază de date, aruncați o privire acest articol и acest articol de la un dezvoltator de top MySQL. Ambii se concentrează pe modul în care InnoDB (motorul MySQL) gestionează indecșii.

Notă: Un cititor mi-a spus că, din cauza optimizărilor de nivel scăzut, arborele B+ ar trebui să fie complet echilibrat.

Hashtable

Ultima noastră structură de date importantă este tabelul hash. Acest lucru este foarte util atunci când doriți să căutați rapid valori. Mai mult, înțelegerea unui tabel hash ne va ajuta să înțelegem mai târziu o operație comună de alăturare a bazei de date numită hash join ( hash join). Această structură de date este folosită și de baza de date pentru a stoca unele lucruri interne (de ex. masa de blocare sau bazin tampon, vom vedea ambele concepte mai târziu).

Un tabel hash este o structură de date care găsește rapid un element după cheia sa. Pentru a construi un tabel hash, trebuie să definiți:

• cheie pentru elementele tale
• funcția hash pentru chei. Hash-urile cheii calculate oferă locația elementelor (numite segmente ).
• funcția de comparare a tastelor. Odată ce ați găsit segmentul corect, trebuie să găsiți elementul pe care îl căutați în cadrul segmentului folosind această comparație.

Exemplu simplu

Să luăm un exemplu clar:

Acest tabel hash are 10 segmente. Pentru că sunt leneș, am pozat doar 5 segmente, dar știu că ești deștept, așa că te las să te imaginezi pe celelalte 5 singur. Am folosit o funcție hash modulo 10 a tastei. Cu alte cuvinte, stochez doar ultima cifră a cheii elementului pentru a-i găsi segmentul:

• dacă ultima cifră este 0, elementul se încadrează în segmentul 0,
• dacă ultima cifră este 1, elementul se încadrează în segmentul 1,
• dacă ultima cifră este 2, elementul se încadrează în zona 2,
• ...

Funcția de comparație pe care am folosit-o este pur și simplu egalitatea între două numere întregi.

Să presupunem că doriți să obțineți elementul 78:

• Tabelul hash calculează codul hash pentru 78, care este 8.
• Tabelul hash se uită la segmentul 8, iar primul element pe care îl găsește este 78.
• Ea îți returnează articolul 78
• Căutarea costă doar 2 operațiuni (unul pentru a calcula valoarea hash și celălalt pentru a căuta elementul din segment).

Acum să presupunem că doriți să obțineți elementul 59:

• Tabelul hash calculează codul hash pentru 59, care este 9.
• Tabelul hash caută în segmentul 9, primul element găsit este 99. Deoarece 99!=59, elementul 99 nu este un element valid.
• Folosind aceeași logică, se iau al doilea element (9), al treilea (79), ..., ultimul (29).
• Element nu a fost găsit.
• Căutarea a costat 7 operațiuni.

Funcție hash bună

După cum puteți vedea, în funcție de valoarea pe care o căutați, costul nu este același!

Dacă acum schimb funcția hash modulo 1 a cheii (adică luând ultimele 000 cifre), a doua căutare costă doar 000 operație, deoarece nu există elemente în segmentul 6. Adevărata provocare este să găsești o funcție hash bună care să creeze găleți care conțin un număr foarte mic de elemente.

În exemplul meu, găsirea unei funcții hash bună este ușoară. Dar acesta este un exemplu simplu, găsirea unei funcții hash bună este mai dificilă atunci când cheia este:

• șir (de exemplu, numele de familie)
• 2 rânduri (de exemplu - nume și prenume)
• 2 rânduri și data (de exemplu - nume, prenume și data nașterii)
• ...

Cu o funcție hash bună, căutările în tabelul hash costă O(1).

Tabelul Array vs Hash

De ce să nu folosiți o matrice?

Hmm, bună întrebare.

• Tabelul hash poate fi parțial încărcat în memorie, iar segmentele rămase pot rămâne pe disc.
• Cu o matrice trebuie să utilizați spațiu contiguu în memorie. Dacă încărcați o masă mare este foarte greu să găsești suficient spațiu continuu.
• Pentru un tabel hash, puteți selecta cheia dorită (de exemplu, țara și numele persoanei).

Pentru mai multe informații, puteți citi articolul despre JavaHashmap, care este o implementare eficientă a unui tabel hash; nu trebuie să înțelegeți Java pentru a înțelege conceptele abordate în acest articol.

Sursa: www.habr.com