Hej Habr! Predstavljam vam prevod članka
"Kako deluje relacijska zbirka podatkov".

Ko gre za relacijske baze podatkov, si ne morem kaj, da ne bi pomislil, da nekaj manjka. Uporabljajo se povsod. Na voljo je veliko različnih baz podatkov, od majhne in uporabne SQLite do zmogljive Teradata. Vendar obstaja le nekaj člankov, ki pojasnjujejo, kako baza podatkov deluje. Iščete lahko sami z uporabo "howdoesarelationaldatabasework", da vidite, kako malo je rezultatov. Poleg tega so ti članki kratki. Če iščete najnovejše buzzy tehnologije (BigData, NoSQL ali JavaScript), boste našli bolj poglobljene članke, ki pojasnjujejo, kako delujejo.

Ali so relacijske baze podatkov prestare in preveč dolgočasne, da bi jih razlagali zunaj univerzitetnih tečajev, raziskovalnih člankov in knjig?

Kot razvijalec sovražim uporabo nečesa, česar ne razumem. In če se baze podatkov uporabljajo več kot 40 let, mora obstajati razlog. Z leti sem porabil na stotine ur, da sem resnično razumel te čudne črne skrinjice, ki jih uporabljam vsak dan. Relacijske baze podatkov zelo zanimivo, saj jih temelji na uporabnih in ponovno uporabnih konceptih. Če vas zanima razumevanje baze podatkov, vendar nikoli niste imeli časa ali volje, da bi se poglobili v to široko temo, bi vam ta članek moral biti všeč.

Čeprav je naslov tega članka ekspliciten, namen tega članka ni razumeti, kako uporabljati bazo podatkov. Zato morali bi že znati napisati preprosto zahtevo za povezavo in osnovne poizvedbe DROBEN; drugače morda ne boste razumeli tega članka. To je edina stvar, ki jo morate vedeti, ostalo vam bom razložil.

Začel bom z nekaj osnovami računalništva, kot je časovna kompleksnost algoritmov (BigO). Vem, da nekateri od vas sovražite ta koncept, vendar brez njega ne boste mogli razumeti zapletenosti v bazi podatkov. Ker je to velika tema, Osredotočil se bom na kar se mi zdi pomembno: kako baza podatkov obdeluje SQL zahtevo. Se bom samo predstavil osnovni pojmi baze podatkovtako da boste na koncu članka imeli predstavo o tem, kaj se dogaja pod pokrovom.

Ker je to dolg in tehničen članek, ki vključuje veliko algoritmov in podatkovnih struktur, si vzemite čas in ga preberite. Nekatere koncepte je morda težko razumeti; lahko jih preskočite in še vedno dobite splošno predstavo.

Za bolj obveščene je ta članek razdeljen na 3 dele:

Pregled nizkonivojskih in visokonivojskih komponent baze podatkov
Pregled postopka optimizacije poizvedbe
Pregled upravljanja transakcij in vmesnega pomnilnika

Nazaj k osnovam

Pred leti (v galaksiji daleč, daleč stran ...) so morali razvijalci natančno vedeti, koliko operacij so kodirali. Svoje algoritme in podatkovne strukture so poznali na pamet, ker si niso mogli privoščiti zapravljanja procesorja in pomnilnika svojih počasnih računalnikov.

V tem delu vas bom spomnil na nekatere od teh konceptov, saj so bistveni za razumevanje baze podatkov. Predstavil bom tudi koncept indeks baze podatkov.

O(1) proti O(n2)

Dandanes mnogim razvijalcem ni mar za časovno zahtevnost algoritmov ... in prav imajo!

Ko pa imate opravka z veliko podatki (ne govorim o tisočih) ali če se trudite v milisekundah, postane razumevanje tega koncepta ključnega pomena. In kot si lahko predstavljate, se morajo baze podatkov spopasti z obema situacijama! Ne bom vas prisilil, da porabite več časa, kot je potrebno, da razumete bistvo. To nam bo pomagalo kasneje razumeti koncept optimizacije na podlagi stroškov (stroški temeljijo optimizacija).

Koncept

Časovna zahtevnost algoritma uporablja za ugotavljanje, koliko časa bo trajalo izvajanje algoritma za določeno količino podatkov. Za opis te kompleksnosti uporabljamo matematični zapis z velikim O. Ta zapis se uporablja s funkcijo, ki opisuje, koliko operacij potrebuje algoritem za dano število vhodov.

Na primer, ko rečem "ta algoritem ima kompleksnost O(some_function())", to pomeni, da algoritem zahteva operacije some_function(a_certain_amount_of_data) za obdelavo določene količine podatkov.

V tem primeru Ni pomembna količina podatkov**, drugače ** kako se število operacij povečuje z naraščajočo količino podatkov. Časovna kompleksnost ne zagotavlja natančnega števila operacij, vendar je dober način za oceno časa izvajanja.

V tem grafu lahko vidite število operacij v primerjavi s količino vhodnih podatkov za različne vrste časovne kompleksnosti algoritmov. Za prikaz sem uporabil logaritemsko lestvico. Z drugimi besedami, količina podatkov se hitro poveča z 1 na 1 milijardo. Vidimo lahko, da:

O(1) ali konstantna kompleksnost ostane konstantna (sicer se ne bi imenovala konstantna kompleksnost).
O(prijavi(n)) ostaja nizka tudi z milijardami podatkov.
Najhujša težava - O(n2), kjer število operacij hitro narašča.
Druga dva zapleta naraščata enako hitro.

Primeri

Pri majhni količini podatkov je razlika med O(1) in O(n2) zanemarljiva. Na primer, recimo, da imate algoritem, ki mora obdelati 2000 elementov.

Algoritem O(1) vas bo stal 1 operacijo
Algoritem O(log(n)) vas bo stal 7 operacij
Algoritem O(n) vas bo stal 2 operacij
Algoritem O(n*log(n)) vas bo stal 14 operacij
Algoritem O(n2) vas bo stal 4 operacij

Razlika med O(1) in O(n2) se zdi velika (4 milijone operacij), vendar boste izgubili največ 2 ms, samo čas, da pomežiknete. Dejansko lahko sodobni procesorji obdelujejo stotine milijonov operacij na sekundo. Zato zmogljivost in optimizacija nista problem pri mnogih projektih IT.

Kot sem rekel, je pri delu z ogromnimi količinami podatkov še vedno pomembno poznati ta koncept. Če mora algoritem tokrat obdelati 1 elementov (kar ni tako veliko za bazo podatkov):

Algoritem O(1) vas bo stal 1 operacijo
Algoritem O(log(n)) vas bo stal 14 operacij
Algoritem O(n) vas bo stal 1 operacij
Algoritem O(n*log(n)) vas bo stal 14 operacij
Algoritem O(n2) vas bo stal 1 operacij

Nisem računal, vendar bi rekel, da imate z algoritmom O(n2) čas, da spijete kavo (celo dve!). Če količini podatkov dodate še 0, boste imeli čas za spanec.

Pojdimo globlje

Za vaše podatke:

Dobro iskanje zgoščene tabele najde element v O(1).
Iskanje po dobro uravnoteženem drevesu daje rezultate v O(log(n)).
Iskanje po matriki daje rezultate v O(n).
Najboljši algoritmi za razvrščanje imajo kompleksnost O(n*log(n)).
Slab algoritem za razvrščanje ima kompleksnost O(n2).

Opomba: V naslednjih delih bomo videli te algoritme in podatkovne strukture.

Obstaja več vrst časovne kompleksnosti algoritmov:

scenarij povprečnega primera
najboljši možni scenarij
in najslabši možni scenarij

Časovna zapletenost je pogosto najslabši možni scenarij.

Govoril sem le o časovni zahtevnosti algoritma, vendar kompleksnost velja tudi za:

poraba pomnilnika algoritma
algoritem porabe V/I diska

Seveda obstajajo zapleti, hujši od n2, na primer:

n4: to je grozno! Nekateri od omenjenih algoritmov imajo to kompleksnost.
3n: to je še huje! Eden od algoritmov, ki jih bomo videli na sredini tega članka, ima to zapletenost (in se dejansko uporablja v številnih zbirkah podatkov).
faktorial n: rezultatov ne boste nikoli dobili niti z majhno količino podatkov.
nn: Če naletite na to kompleksnost, se vprašajte, ali je to res vaše področje delovanja...

Opomba: Nisem vam dal dejanske definicije velikega O, samo idejo. Ta članek lahko preberete na Wikipedia za realno (asimptotično) definicijo.

MergeSort

Kaj storite, ko morate razvrstiti zbirko? Kaj? Pokličete funkcijo sort() ... V redu, dober odgovor ... Toda za bazo podatkov morate razumeti, kako ta funkcija sort() deluje.

Obstaja več dobrih algoritmov za razvrščanje, zato se bom osredotočil na najpomembnejše: razvrščanje z združitvijo. Morda trenutno ne razumete, zakaj je razvrščanje podatkov uporabno, vendar bi morali po delu optimizacije poizvedbe. Poleg tega nam bo razumevanje razvrščanja z združevanjem pomagalo pozneje razumeti skupno operacijo združevanja baze podatkov, imenovano združiti pridružite (združitveno združenje).

Spoji

Kot mnogi uporabni algoritmi se razvrščanje z združitvijo opira na trik: združevanje 2 razvrščenih nizov velikosti N/2 v N-elementno razvrščeno polje stane samo N operacij. Ta operacija se imenuje združevanje.

Poglejmo, kaj to pomeni s preprostim primerom:

Ta slika prikazuje, da morate za izdelavo končne razvrščene 8-elementne matrike le enkrat ponoviti 2 4-elementni matriki. Ker sta obe 4-elementni matriki že razvrščeni:

1) primerjate oba trenutna elementa v dveh nizih (na začetku trenutni = prvi)
2) nato vzemite najmanjšega, da ga postavite v niz 8 elementov
3) in se premaknite na naslednji element v nizu, kjer ste vzeli najmanjši element
in ponavljajte 1,2,3, dokler ne dosežete zadnjega elementa enega od nizov.
Nato vzamete preostale elemente druge matrike, da jih postavite v matriko z 8 elementi.

To deluje, ker sta obe 4-elementni matriki razvrščeni in se vam ni treba "vrniti" v teh matrikah.

Zdaj, ko razumemo trik, je tukaj moja psevdokoda za spajanje:

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;

Razvrščanje z združitvijo razdeli problem na manjše probleme in nato poišče rezultate manjših problemov, da dobi rezultat prvotnega problema (opomba: ta vrsta algoritma se imenuje deli in vladaj). Če ne razumete tega algoritma, ne skrbite; Nisem razumel, ko sem prvič videl. Če vam lahko pomaga, vidim ta algoritem kot dvofazni algoritem:

Faza delitve, kjer je niz razdeljen na manjše nize
V fazi razvrščanja so majhne matrike združene (z uporabo unije) v večjo matriko.

Faza delitve

V fazi delitve se niz razdeli na enotne nize v 3 korakih. Formalno število korakov je log(N) (ker je N=8, je log(N) = 3).

Kako to vem?

jaz sem genij! Z eno besedo - matematika. Ideja je, da vsak korak deli velikost prvotne matrike z 2. Število korakov je, kolikokrat lahko prvotno matriko razdelite na dvoje. To je natančna definicija logaritma (osnova 2).

Faza razvrščanja

V fazi razvrščanja začnete z enotnimi (enoelementnimi) nizi. Med vsakim korakom uporabite več operacij spajanja in skupni strošek je N = 8 operacij:

V prvi fazi imate 4 združitve, od katerih vsaka stane 2 operaciji
V drugem koraku imate 2 združitvi, ki vsaka stane 4 operacije
V tretjem koraku imate 1 spajanje, ki stane 8 operacij

Ker je log(N) korakov, skupni stroški N * log(N) operacij.

Prednosti razvrščanja z združitvijo

Zakaj je ta algoritem tako močan?

Ker:

Lahko ga spremenite, da zmanjšate pomnilniški odtis, tako da ne ustvarjate novih nizov, ampak neposredno spreminjate vhodno polje.

Opomba: ta vrsta algoritma se imenuje in -mesto (razvrščanje brez dodatnega pomnilnika).

Spremenite ga lahko tako, da bo hkrati uporabljal prostor na disku in majhno količino pomnilnika, ne da bi pri tem povzročili velike V/I stroške. Ideja je, da v pomnilnik naložimo samo tiste dele, ki so trenutno v obdelavi. To je pomembno, ko morate razvrstiti večgigabajtno tabelo s samo 100-megabajtnim medpomnilnikom.

Opomba: ta vrsta algoritma se imenuje zunanja vrsta.

Spremenite ga lahko tako, da deluje v več procesih/nitih/strežnikih.

Na primer, porazdeljeno združevanje je ena ključnih komponent Hadoop (ki je struktura v velikih podatkih).

Ta algoritem lahko spremeni svinec v zlato (res!).

Ta algoritem razvrščanja se uporablja v večini (če ne v vseh) bazah podatkov, vendar ni edini. Če želite izvedeti več, lahko preberete to raziskovalno delo, ki razpravlja o prednostih in slabostih običajnih algoritmov za razvrščanje baz podatkov.

Matrična, drevesna in zgoščena tabela

Zdaj, ko razumemo zamisel o časovni kompleksnosti in razvrščanju, bi vam moral povedati o treh podatkovnih strukturah. To je pomembno, ker so so osnova sodobnih baz podatkov. Predstavil bom tudi koncept indeks baze podatkov.

Array

Dvodimenzionalni niz je najpreprostejša podatkovna struktura. Tabelo si lahko predstavljamo kot niz. Na primer:

Ta 2-dimenzionalni niz je tabela z vrsticami in stolpci:

Vsaka vrstica predstavlja entiteto
Stolpci shranjujejo lastnosti, ki opisujejo entiteto.
Vsak stolpec hrani podatke določene vrste (celo število, niz, datum ...).

To je priročno za shranjevanje in vizualizacijo podatkov, vendar, ko morate najti določeno vrednost, to ni primerno.

Če bi na primer želeli najti vse fante, ki delajo v Združenem kraljestvu, bi morali pogledati vsako vrstico, da ugotovite, ali ta vrstica pripada Združenemu kraljestvu. Stalo vas bo N transakcijČe N - število vrstic, kar ni slabo, a bi lahko obstajal hitrejši način? Zdaj je čas, da se seznanimo z drevesi.

Opomba: večina sodobnih baz podatkov nudi razširjena polja za učinkovito shranjevanje tabel: kopično organizirane tabele in indeksno organizirane tabele. Vendar to ne spremeni težave pri hitrem iskanju določenega pogoja v skupini stolpcev.

Drevo baze podatkov in indeks

Binarno iskalno drevo je binarno drevo s posebno lastnostjo, ključ v vsakem vozlišču mora biti:

večji od vseh ključev, shranjenih v levem poddrevesu
manj kot vsi ključi, shranjeni v desnem poddrevesu

Poglejmo, kaj to vizualno pomeni

Ideja

To drevo ima N = 15 elementov. Recimo, da iščem 208:

Začnem pri korenu, katerega ključ je 136. Ker je 136<208, pogledam desno poddrevo vozlišča 136.
398>208 torej gledam levo poddrevo vozlišča 398
250>208 torej gledam levo poddrevo vozlišča 250
200<208, torej gledam desno poddrevo vozlišča 200. Toda 200 nima pravega poddrevesa, vrednost ne obstaja (ker če obstaja, bo v desnem poddrevesu 200).

Zdaj pa recimo, da iščem 40

Začnem pri korenu, katerega ključ je 136. Ker je 136 > 40, pogledam levo poddrevo vozlišča 136.
80 > 40, zato gledam levo poddrevo vozlišča 80
40 = 40, vozlišče obstaja. Pridobim ID vrstice znotraj vozlišča (ne na sliki) in v tabeli poiščem podani ID vrstice.
Če poznam ID vrstice, lahko natančno vem, kje so podatki v tabeli, tako da jih lahko takoj pridobim.

Na koncu me bosta obe iskanji stali toliko ravni znotraj drevesa. Če natančno preberete del o razvrščanju z združevanjem, bi morali videti, da obstajajo ravni dnevnika (N). Izkazalo se je, dnevnik stroškov iskanja (N), ni slabo!

Vrnimo se k našemu problemu

Toda to je zelo abstraktno, zato se vrnimo k našemu problemu. Namesto preprostega celega števila si zamislite niz, ki predstavlja državo nekoga v prejšnji tabeli. Recimo, da imate drevo, ki vsebuje polje »država« (stolpec 3) tabele:

Če želite vedeti, kdo dela v Združenem kraljestvu
pogledate drevo, da dobite vozlišče, ki predstavlja Veliko Britanijo
znotraj »UKnode« boste našli lokacijo evidenc delavcev v Združenem kraljestvu.

Če matriko uporabite neposredno, bo to iskanje stalo log(N) operacij namesto N operacij. Kar ste pravkar predstavili, je bilo indeks baze podatkov.

Indeksno drevo lahko zgradite za katero koli skupino polj (niz, številka, 2 vrstici, številka in niz, datum ...), če imate funkcijo za primerjavo ključev (tj. skupin polj), tako da lahko nastavite vrstni red med ključi (kar velja za vse osnovne tipe v bazi podatkov).

B+TreeIndex

Medtem ko to drevo deluje dobro za pridobivanje določene vrednosti, obstaja VELIKA težava, ko jo potrebujete dobite več elementov med dvema vrednostma. To bo stalo O(N), ker boste morali pogledati vsako vozlišče v drevesu in preveriti, ali je med tema dvema vrednostma (npr. z urejenim prečkanjem drevesa). Poleg tega ta operacija ni prijazna do V/I diska, saj morate prebrati celotno drevo. Najti moramo način za učinkovito izvedbo zahteva obsega. Za rešitev tega problema sodobne baze podatkov uporabljajo spremenjeno različico prejšnjega drevesa, imenovano B+Tree. V drevesu B+Tree:

samo najnižji vozli (listi) shranjevanje informacij (lokacija vrstic v povezani tabeli)
preostala vozlišča so tukaj za usmerjanje na pravilno vozlišče med iskanjem.

Kot lahko vidite, je tukaj več vozlišč (dvakrat). Dejansko imate dodatna vozlišča, "vozlišča odločanja", ki vam bodo pomagala najti pravo vozlišče (ki shranjuje lokacijo vrstic v povezani tabeli). Toda kompleksnost iskanja je še vedno O(log(N)) (obstaja samo še ena stopnja). Velika razlika je v tem vozlišča na nižji ravni so povezana s svojimi nasledniki.

S tem B+Tree, če iščete vrednosti med 40 in 100:

Samo poiskati morate 40 (ali najbližjo vrednost za 40, če 40 ne obstaja), kot ste storili s prejšnjim drevesom.
Nato zberite 40 dedičev z neposrednimi povezavami dedičev, dokler jih ne dosežete 100.

Recimo, da najdete M naslednikov in ima drevo N vozlišč. Iskanje določenega vozlišča stane log(N) kot prejšnje drevo. Ko pa dobite to vozlišče, boste dobili M naslednikov v M operacijah s sklicevanjem na njihove naslednike. To iskanje stane samo M+log(N) operacij v primerjavi z N operacijami na prejšnjem drevesu. Poleg tega vam ni treba brati celotnega drevesa (samo M+log(N) vozlišč), kar pomeni manjšo uporabo diska. Če je M majhen (npr. 200 vrstic) in N velik (1 vrstic), bo razlika VELIKA.

A tu (spet!) nastanejo nove težave. Če dodate ali izbrišete vrstico v bazi podatkov (in s tem v povezanem indeksu B+Tree):

ohraniti morate red med vozlišči znotraj drevesa B+Tree, drugače ne boste mogli najti vozlišč znotraj nerazvrščenega drevesa.
obdržati morate najmanjše možno število ravni v B+Tree, sicer O(log(N)) časovna zapletenost postane O(N).

Z drugimi besedami, B+drevo mora biti samourejevalno in uravnoteženo. Na srečo je to mogoče s pametnimi operacijami brisanja in vstavljanja. Toda to ima svojo ceno: vstavljanja in brisanja v drevesu B+ stanejo O(log(N)). Zato ste nekateri to slišali uporaba preveč indeksov ni dobra ideja. res, upočasnjujete hitro vstavljanje/posodabljanje/brisanje vrstice v tabeliker mora zbirka podatkov posodobiti indekse tabele z uporabo drage operacije O(log(N)) za vsak indeks. Poleg tega dodajanje indeksov pomeni večjo delovno obremenitev za upravitelj transakcij (opisano bo na koncu članka).

Za več podrobnosti si lahko ogledate članek o Wikipediji B+drevo. Če želite primer implementacije B+Tree v bazo podatkov, si oglejte ta članek и ta članek od vodilnega razvijalca MySQL. Oba se osredotočata na to, kako InnoDB (motor MySQL) obravnava indekse.

Opomba: bralec mi je povedal, da bi moralo biti zaradi optimizacij na nizki ravni drevo B+ popolnoma uravnoteženo.

Razpršitvena tabela

Naša zadnja pomembna podatkovna struktura je zgoščena tabela. To je zelo uporabno, ko želite hitro poiskati vrednosti. Poleg tega nam bo razumevanje zgoščene tabele kasneje pomagalo razumeti običajno operacijo združevanja baze podatkov, imenovano zgoščeno združevanje ( hash join). To strukturo podatkov baza podatkov uporablja tudi za shranjevanje nekaterih notranjih stvari (npr. zaklepanje mize ali vmesni bazen, oba koncepta bomo videli pozneje).

Zgoščevalna tabela je podatkovna struktura, ki hitro najde element na podlagi njegovega ključa. Če želite zgraditi zgoščeno tabelo, morate definirati:

namig za vaše elemente
hash funkcija za ključe. Izračunane zgoščene vrednosti ključa dajejo lokacijo elementov (imenovanih segmenti ).
funkcijo za primerjavo ključev. Ko najdete pravi segment, morate s to primerjavo najti element, ki ga iščete znotraj segmenta.

Preprost primer

Vzemimo jasen primer:

Ta zgoščena tabela ima 10 segmentov. Ker sem len, sem slikal samo 5 segmentov, vem pa, da si pameten, zato ti pustim, da si ostalih 5 slikaš sam. Uporabil sem zgoščevalno funkcijo modulo 10 ključa. Z drugimi besedami, shranim samo zadnjo številko ključa elementa, da najdem njegov segment:

če je zadnja številka 0, element pade v segment 0,
če je zadnja številka 1, element pade v segment 1,
če je zadnja številka 2, element sodi v območje 2,
...

Primerjalna funkcija, ki sem jo uporabil, je preprosto enakost med dvema celima številoma.

Recimo, da želite dobiti element 78:

Zgoščevalna tabela izračuna zgoščevalno kodo za 78, kar je 8.
Zgoščevalna tabela gleda na segment 8 in prvi element, ki ga najde, je 78.
Vrne vam predmet 78
Iskanje stane le 2 operaciji (eden za izračun zgoščene vrednosti in drugi za iskanje elementa znotraj segmenta).

Zdaj pa recimo, da želite dobiti element 59:

Zgoščevalna tabela izračuna zgoščevalno kodo za 59, kar je 9.
Zgoščevalna tabela išče v segmentu 9, prvi najdeni element je 99. Ker je 99!=59, element 99 ni veljaven element.
Po isti logiki se vzame drugi element (9), tretji (79), ..., zadnji (29).
Element ni bil najden.
Iskanje je stalo 7 operacij.

Dobra zgoščevalna funkcija

Kot lahko vidite, stroški niso enaki glede na vrednost, ki jo iščete!

Če zdaj spremenim zgoščevalno funkcijo po modulu 1 ključa (to je, vzamem zadnjih 000 števk), drugo iskanje stane le 000 operacijo, ker v segmentu 6 ni elementov. Pravi izziv je najti dobro zgoščevalno funkcijo, ki bo ustvarila vedra, ki vsebujejo zelo majhno število elementov.

V mojem primeru je iskanje dobre zgoščevalne funkcije preprosto. Toda to je preprost primer, iskanje dobre zgoščevalne funkcije je težje, če je ključ:

niz (na primer - priimek)
2 vrstici (na primer - priimek in ime)
2 vrstici in datum (na primer - priimek, ime in datum rojstva)
...

Z dobro zgoščevalno funkcijo stane iskanje zgoščevalnih tabel O(1).

Matrična proti zgoščeni tabeli

Zakaj ne bi uporabili matrike?

Hmm, dobro vprašanje.

Zgoščevalna tabela je lahko delno naložen v pomnilnik, preostali segmenti pa lahko ostanejo na disku.
Pri matriki morate uporabiti sosednji prostor v pomnilniku. Če nalagate veliko mizo zelo težko je najti dovolj neprekinjenega prostora.
Za zgoščeno tabelo lahko izberete želeni ključ (na primer državo in priimek osebe).

Za več informacij si lahko preberete članek o JavaHashMap, ki je učinkovita izvedba zgoščene tabele; ni vam treba razumeti Jave, da bi razumeli koncepte, obravnavane v tem članku.

Vir: www.habr.com

Kako delujejo relacijske baze podatkov (1. del)