Tere Habr! Esitan teie tähelepanu artikli tõlkele
"Kuidas relatsiooniline andmebaas töötab".

Relatsiooniandmebaaside puhul ei saa ma jätta arvamata, et midagi on puudu. Neid kasutatakse kõikjal. Saadaval on palju erinevaid andmebaase, alates väikesest ja kasulikust SQLite'ist kuni võimsa Teradatani. Kuid andmebaasi toimimist selgitavad vaid mõned artiklid. Saate ise otsida, kasutades "howdoesarelational Databasework", et näha, kui vähe tulemusi on. Pealegi on need artiklid lühikesed. Kui otsite uusimaid buzzy tehnoloogiaid (BigData, NoSQL või JavaScript), leiate põhjalikumaid artikleid nende toimimise kohta.

Kas relatsiooniandmebaasid on liiga vanad ja liiga igavad, et neid väljaspool ülikoolikursusi, uurimistöid ja raamatuid selgitada?

Arendajana vihkan ma kasutada midagi, millest ma aru ei saa. Ja kui andmebaase on kasutatud üle 40 aasta, peab põhjus olema. Aastate jooksul olen kulutanud sadu tunde, et mõista neid kummalisi musti kaste, mida ma iga päev kasutan. Relatsiooniandmebaasid väga huvitav, sest nad põhineb kasulikel ja korduvkasutatavatel kontseptsioonidel. Kui olete huvitatud andmebaasi mõistmisest, kuid teil pole kunagi olnud aega ega soovi sellesse laiaulatuslikku teemasse süveneda, peaksite seda artiklit nautima.

Kuigi selle artikli pealkiri on selgesõnaline, selle artikli eesmärk ei ole mõista, kuidas andmebaasi kasutada... Seega sa peaksid juba teadma, kuidas kirjutada lihtsat ühenduse taotlust ja põhipäringuid TOOR; muidu ei pruugi te sellest artiklist aru saada. See on ainus asi, mida peate teadma, ma selgitan ülejäänu.

Alustan arvutiteaduse põhitõdedest, näiteks algoritmide aja keerukusest (BigO). Ma tean, et mõned teist vihkavad seda kontseptsiooni, kuid ilma selleta ei saa te andmebaasi keerukusest aru. Kuna see on suur teema, Ma keskendun sellele mis minu arvates on oluline: kuidas andmebaas töötleb SQL päring. Ma lihtsalt tutvustan andmebaasi põhikontseptsioonidet saaksite artikli lõpus aimu, mis kapoti all toimub.

Kuna see on pikk ja tehniline artikkel, mis hõlmab palju algoritme ja andmestruktuure, võtke selle lugemiseks aega. Mõned mõisted võivad olla raskesti mõistetavad; võite need vahele jätta ja ikkagi saada üldise ettekujutuse.

Teadjamate jaoks on see artikkel jagatud kolmeks osaks:

• Ülevaade madala taseme ja kõrgetasemelistest andmebaasi komponentidest
• Ülevaade päringu optimeerimise protsessist
• Ülevaade tehingute ja puhverkogumi haldamisest

Tagasi põhitõdede juurde

Aastaid tagasi (kaugel-kaugel galaktikas...) pidid arendajad täpselt teadma, mitu operatsiooni nad kodeerisid. Nad teadsid oma algoritme ja andmestruktuure peast, sest nad ei saanud endale lubada oma aeglaste arvutite protsessori ja mälu raiskamist.

Selles osas tuletan teile meelde mõnda neist mõistetest, kuna need on andmebaasi mõistmiseks hädavajalikud. Tutvustan ka kontseptsiooni andmebaasi indeks.

O(1) vs O(n2)

Tänapäeval ei hooli paljud arendajad algoritmide ajalisest keerukusest... ja neil on õigus!

Kuid kui teil on palju andmeid (ma ei räägi tuhandetest) või kui teil on probleeme millisekunditega, on selle kontseptsiooni mõistmine ülioluline. Ja nagu võite ette kujutada, peavad andmebaasid mõlema olukorraga hakkama saama! Ma ei sunni sind kulutama rohkem aega, kui on vaja, et asjast aru saada. See aitab meil hiljem mõista kulupõhise optimeerimise kontseptsiooni (hind põhineb optimeerimine).

Mõiste

Algoritmi ajaline keerukus kasutatakse selleks, et näha, kui kaua võtab algoritm teatud andmehulga täitmiseks. Selle keerukuse kirjeldamiseks kasutame suurt matemaatilist tähistust O. Seda tähistust kasutatakse funktsiooniga, mis kirjeldab, kui palju tehteid vajab algoritm teatud arvu sisendite jaoks.

Näiteks kui ma ütlen "selle algoritmi keerukus on O(some_function())", tähendab see, et algoritm nõuab teatud andmehulga töötlemiseks operatsioone mingi_funktsioon(a_kindel_andmete_summa).

Sel juhul Andmete hulk ei ole oluline**, muidu ** kuidas toimingute arv suureneb andmemahu suurenemisega. Ajaline keerukus ei anna täpset toimingute arvu, kuid on hea viis täitmisaja hindamiseks.

Sellel graafikul näete toimingute arvu versus sisendandmete hulk erinevat tüüpi algoritmi ajaliste keerukusega. Kasutasin nende kuvamiseks logaritmilist skaalat. Teisisõnu suureneb andmemaht kiiresti 1 miljardilt 1 miljardile. Näeme, et:

• O(1) ehk konstantne keerukus jääb konstantseks (muidu ei nimetaks seda konstantseks keerukuseks).
• O(logi(n)) jääb madalaks isegi miljardite andmete korral.
• Halvim raskus - O(n2), kus operatsioonide arv kasvab kiiresti.
• Ülejäänud kaks tüsistust suurenevad sama kiiresti.

näited

Väikese andmehulga korral on erinevus O(1) ja O(n2) vahel tühine. Oletame näiteks, et teil on algoritm, mis peab töötlema 2000 elementi.

• Algoritm O(1) maksab teile 1 operatsiooni
• Algoritm O(log(n)) maksab teile 7 toimingut
• Algoritm O(n) maksab teile 2 toimingut
• Algoritm O(n*log(n)) maksab teile 14 000 toimingut
• Algoritm O(n2) maksab teile 4 000 000 toimingut

Erinevus O(1) ja O(n2) vahel tundub suur (4 miljonit toimingut), kuid te kaotate maksimaalselt 2 ms, lihtsalt aega pilgutada silmi. Tõepoolest, kaasaegsed protsessorid suudavad töödelda sadu miljoneid toiminguid sekundis. Seetõttu ei ole jõudlus ja optimeerimine paljudes IT-projektides probleemiks.

Nagu ma ütlesin, on tohutute andmemahtudega töötamisel siiski oluline seda kontseptsiooni tunda. Kui seekord peab algoritm töötlema 1 000 000 elementi (mis pole andmebaasi jaoks nii palju):

• Algoritm O(1) maksab teile 1 operatsiooni
• Algoritm O(log(n)) maksab teile 14 toimingut
• Algoritm O(n) maksab teile 1 000 000 toimingut
• Algoritm O(n*log(n)) maksab teile 14 000 000 toimingut
• Algoritm O(n2) maksab teile 1 000 000 000 000 toimingut

Ma pole matemaatikat teinud, aga ma ütleks, et O(n2) algoritmiga on sul aega juua üks kohvi (isegi kaks!). Kui lisate andmemahule veel 0, on teil aega lõunauinaku tegemiseks.

Läheme sügavamale

Teile teadmiseks:

• Hea räsitabeli otsing leiab O(1) elemendi.
• Hästi tasakaalustatud puu otsimine annab tulemused O(log(n)).
• Massiivi otsimine annab tulemused O(n).
• Parimate sorteerimisalgoritmide keerukus on O(n*log(n)).
• Halval sorteerimisalgoritmil on keerukus O(n2).

Märkus. Järgmistes osades näeme neid algoritme ja andmestruktuure.

Algoritmi aja keerukust on mitut tüüpi:

• keskmine juhtumistsenaarium
• parimal juhul
• ja halvimal juhul

Aja keerukus on sageli halvim stsenaarium.

Ma rääkisin ainult algoritmi ajalisest keerukusest, kuid keerukus kehtib ka:

• algoritmi mälu tarbimine
• ketta I/O tarbimise algoritm

Muidugi on n2-st hullemaid tüsistusi, näiteks:

• n4: see on kohutav! Mõnel mainitud algoritmil on see keerukus.
• 3n: see on veelgi hullem! Üks algoritmidest, mida me selle artikli keskel näeme, on selle keerukusega (ja seda kasutatakse tegelikult paljudes andmebaasides).
• faktoriaal n: te ei saa kunagi tulemusi isegi väikese andmehulga korral.
• nn: Kui puutute kokku selle keerukusega, peaksite endalt küsima, kas see on tõesti teie tegevusvaldkond...

Märkus. Ma ei andnud teile suure O-tähise tegelikku määratlust, vaid lihtsalt idee. Seda artiklit saate lugeda aadressil Wikipedia tegeliku (asümptootilise) määratluse jaoks.

MergeSort

Mida teete, kui teil on vaja kollektsiooni sorteerida? Mida? Kutsud funktsiooni sort()... Ok, hea vastus... Aga andmebaasi puhul pead sa aru saama, kuidas see sort() funktsioon töötab.

On mitmeid häid sortimisalgoritme, seega keskendun kõige olulisematele: liita sort. Te ei pruugi aru saada, miks andmete sortimine praegu kasulik on, kuid pärast päringu optimeerimise osa peaksite seda tegema. Veelgi enam, liitmissortimise mõistmine aitab meil hiljem mõista ühist andmebaasi ühendamise operatsiooni ühendada liituma (ühinemisühing).

Ühendage

Nagu paljud kasulikud algoritmid, tugineb liitmissortimine trikile: 2 sorteeritud massiivi, mille suurus on N/2, ühendamine N-elemendiliseks sorteeritud massiiviks maksab ainult N toimingut. Seda toimingut nimetatakse ühendamiseks.

Vaatame lihtsa näite abil, mida see tähendab:

See joonis näitab, et lõpliku sorteeritud 8-elemendilise massiivi koostamiseks peate 2 4-elemendilise massiivi üle kordama ainult üks kord. Kuna mõlemad 4-elemendilised massiivid on juba sorteeritud:

• 1) võrdlete mõlemat praegust elementi kahes massiivis (alguses praegune = esimene)
• 2) seejärel võtke väikseim, et panna see 8 elemendiga massiivi
• 3) ja liikuge massiivi järgmise elemendi juurde, kust võtsite väikseima elemendi
• ja korrake 1,2,3, kuni jõuate ühe massiivi viimase elemendini.
• Seejärel võtate teise massiivi ülejäänud elemendid, et panna need 8 elemendiga massiivi.

See toimib, kuna mõlemad 4-elemendilised massiivid on sorteeritud ja seega ei pea te nendes massiivides "tagasi minema".

Nüüd, kui me trikist aru saame, on siin minu ühendamise pseudokood:

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;

Ühenda sortimine jagab probleemi väiksemateks ülesanneteks ja seejärel otsib algülesande tulemuse saamiseks väiksemate ülesannete tulemused (märkus: seda tüüpi algoritmi nimetatakse jaga ja valluta). Kui te sellest algoritmist aru ei saa, ärge muretsege; Ma ei saanud sellest aru, kui seda esimest korda nägin. Kui see võib teid aidata, näen seda algoritmi kahefaasilise algoritmina:

• Jagamise faas, kus massiiv jagatakse väiksemateks massiivideks
• Sorteerimisfaas on see, kus väikesed massiivid kombineeritakse (kasutades liitmist), et moodustada suurem massiiv.

Jagamise faas

Jagamise etapis jagatakse massiiv 3 sammuna ühtseteks massiivideks. Formaalne sammude arv on log(N) (kuna N=8, log(N) = 3).

Kuidas ma seda tean?

Ma olen geenius! Ühesõnaga – matemaatika. Idee seisneb selles, et iga samm jagab algse massiivi suuruse 2-ga. Sammude arv näitab, mitu korda saate algse massiivi kaheks jagada. See on logaritmi täpne määratlus (alus 2).

Sorteerimisfaas

Sorteerimisfaasis alustatakse ühtsete (üheelemendiliste) massiividega. Iga etapi jooksul rakendate mitu liitmistoimingut ja kogumaksumus on N = 8 toimingut:

• Esimeses etapis on teil 4 liitmist, millest igaüks maksab 2 toimingut
• Teises etapis on teil 2 liitmist, millest igaüks maksab 4 toimingut
• Kolmandas etapis on teil 1 liitmine, mis maksab 8 toimingut

Kuna on log(N) samme, kogumaksumus N * logi(N) operatsioonid.

Ühendamise sortimise eelised

Miks see algoritm nii võimas on?

Sest:

• Saate seda muuta mälumahu vähendamiseks, nii et te ei loo uusi massiive, vaid muudate otse sisendmassiivi.

Märkus: seda tüüpi algoritmi nimetatakse in-koht (sorteerimine ilma lisamäluta).

• Saate seda muuta nii, et see kasutaks samaaegselt kettaruumi ja väikest mälumahtu, ilma et see tekitaks märkimisväärseid ketta sisend-/väljundkulusid. Idee on laadida mällu ainult need osad, mida praegu töödeldakse. See on oluline, kui peate sorteerima mitme gigabaidise tabeli ainult 100-megabaidise mälupuhvriga.

Märkus: seda tüüpi algoritmi nimetatakse väline sortimine.

• Saate seda muuta nii, et see töötaks mitmes protsessis/lõimes/serveris.

Näiteks hajutatud liitmise sortimine on üks peamisi komponente hadoop (mis on suurandmete struktuur).

• See algoritm võib muuta plii kullaks (tõesti!).

Seda sortimisalgoritmi kasutatakse enamikus (kui mitte kõigis) andmebaasides, kuid see pole ainus. Kui soovite rohkem teada saada, võite seda lugeda uurimistöö, kus käsitletakse levinud andmebaaside sortimisalgoritmide plusse ja miinuseid.

Massiivi-, puu- ja räsitabel

Nüüd, kui me mõistame aja keerukuse ja sortimise ideed, peaksin teile rääkima kolmest andmestruktuurist. See on oluline, sest nad on kaasaegsete andmebaaside aluseks. Tutvustan ka kontseptsiooni andmebaasi indeks.

Massiiv

Kahemõõtmeline massiiv on lihtsaim andmestruktuur. Tabelit võib pidada massiiviks. Näiteks:

See kahemõõtmeline massiiv on ridade ja veergudega tabel:

• Iga rida tähistab olemit
• Veerud salvestavad olemit kirjeldavad atribuudid.
• Iga veerg salvestab kindlat tüüpi andmeid (täisarv, string, kuupäev...).

See on mugav andmete salvestamiseks ja visualiseerimiseks, kuid kui on vaja leida konkreetne väärtus, siis see ei sobi.

Näiteks kui soovite leida kõiki Ühendkuningriigis töötavaid tüüpe, peaksite uurima iga rida, et teha kindlaks, kas see rida kuulub Ühendkuningriigile. See maksab teile N tehingutKus N - ridade arv, mis pole halb, aga kas saaks olla kiiremat teed? Nüüd on meil aeg puudega tutvust teha.

Märkus. Enamik kaasaegseid andmebaase pakuvad tabelite tõhusaks salvestamiseks laiendatud massiive: kuhjaga organiseeritud tabelid ja indeksiga korraldatud tabelid. Kuid see ei muuda konkreetse tingimuse kiire leidmise probleemi veergude rühmast.

Andmebaasi puu ja indeks

Binaarne otsingupuu on spetsiaalse omadusega binaarne puu, iga sõlme võti peab olema:

• suurem kui kõik vasakpoolsesse alampuusse salvestatud võtmed
• vähem kui kõik paremasse alampuusse salvestatud võtmed

Vaatame, mida see visuaalselt tähendab

Mõte

Sellel puul on N = 15 elementi. Oletame, et ma otsin 208:

• Alustan juurest, mille võti on 136. Kuna 136<208, vaatan sõlme 136 paremat alampuud.
• 398>208 seetõttu vaatan sõlme 398 vasakut alampuud
• 250>208 seetõttu vaatan sõlme 250 vasakut alampuud
• 200<208, seega ma vaatan sõlme 200 paremat alampuud. Kuid 200-l pole õiget alampuud, väärtust ei eksisteeri (sest kui see on olemas, on see õiges alampuus 200).

Oletame nüüd, et otsin 40

• Alustan juurest, mille võti on 136. Kuna 136 > 40, vaatan sõlme 136 vasakut alampuud.
• 80 > 40, seega vaatan sõlme 80 vasakut alampuud
• 40 = 40, sõlm on olemas. Otsin sõlme seest rea ID (pole pildil näidatud) ja otsin tabelist antud rea ID.
• Rea ID teadmine võimaldab mul täpselt teada, kus andmed tabelis asuvad, et saaksin need kohe kätte saada.

Lõpuks maksavad mõlemad otsingud mulle puu sees olevate tasemete arvu. Kui loete hoolikalt osa liitmise sortimise kohta, peaksite nägema, et seal on logi(N) tasemed. Selgub, otsingukulude logi (N), pole paha!

Tuleme tagasi oma probleemi juurde

Kuid see on väga abstraktne, nii et tuleme tagasi oma probleemi juurde. Lihtsa täisarvu asemel kujutage ette stringi, mis tähistab eelmises tabelis kellegi riiki. Oletame, et teil on puu, mis sisaldab tabeli välja „riik” (veerg 3):

• Kui soovite teada, kes Ühendkuningriigis töötab
• vaatate puud, et saada Suurbritanniat tähistav sõlm
• "UKnode" seest leiate Ühendkuningriigi töötajate kirjete asukoha.

Kui kasutate massiivi otse, maksab see otsing N toimingu asemel logi(N). See, mida te just esitasite, oli andmebaasi indeks.

Saate luua indeksipuu mis tahes väljade rühma jaoks (string, number, 2 rida, number ja string, kuupäev...), kui teil on funktsioon võtmete (st väljarühmade) võrdlemiseks, et saaksite määrata järjestus võtmete vahel (mis kehtib kõigi andmebaasi põhitüüpide puhul).

B+Puuindeks

Kuigi see puu töötab konkreetse väärtuse saamiseks hästi, on vajaduse korral SUUR probleem saada kahe väärtuse vahele mitu elementi. See maksab O(N), sest peate vaatama puu iga sõlme ja kontrollima, kas see on nende kahe väärtuse vahel (nt puu järjestatud läbimise korral). Pealegi pole see toiming ketta I/O-sõbralik, kuna peate lugema kogu puu. Peame leidma viisi tõhusaks täitmiseks vahemiku taotlus. Selle probleemi lahendamiseks kasutavad kaasaegsed andmebaasid eelmise puu muudetud versiooni nimega B+Tree. B+puu puus:

• ainult madalaimad sõlmed (lehed) salvestada teavet (ridade asukoht seotud tabelis)
• ülejäänud sõlmed on siin marsruutimiseks õigesse sõlme otsimise ajal.

Nagu näete, on siin rohkem sõlme (kaks korda). Tõepoolest, teil on lisasõlmed, "otsustussõlmed", mis aitavad teil leida õige sõlme (mis salvestab seotud tabelis olevate ridade asukoha). Kuid otsingu keerukus on endiselt O(log(N)) (on ainult üks tase veel). Suur erinevus seisneb selles madalama taseme sõlmed on ühendatud nende järglastega.

Selle B+Tree abil, kui otsite väärtusi 40 ja 100 vahel:

• Peate lihtsalt otsima 40 (või lähimat väärtust pärast 40, kui 40 pole olemas), nagu tegite eelmise puu puhul.
• Seejärel koguge otseste pärijalinkide abil 40 pärijat, kuni jõuate 100-ni.

Oletame, et leiate M järglast ja puul on N sõlme. Konkreetse sõlme leidmine maksab log(N), nagu eelmine puu. Kuid kui olete selle sõlme hankinud, saate M-operatsioonides M järglast koos viidetega nende järglastele. See otsing maksab ainult M+log(N) tehteid võrreldes eelmise puu N operatsiooniga. Lisaks ei pea te lugema kogu puud (ainult M+log(N) sõlme), mis tähendab vähem kettakasutust. Kui M on väike (nt 200 rida) ja N on suur (1 000 000 rida), on erinevus SUUR.

Kuid siin on (jälle!) uued probleemid. Kui lisate või kustutate rea andmebaasis (ja sellega seotud B+Tree indeksis):

• B+Tree sees olevate sõlmede vahel tuleb hoida korda, vastasel juhul ei leia te sortimata puu seest sõlmi.
• peate hoidma B+Tree-s minimaalset võimalikku tasemete arvu, vastasel juhul muutub O(log(N)) ajaline keerukus O(N).

Ehk siis B+Tree peab olema isekorrastuv ja tasakaalus. Õnneks on see nutikate kustutamise ja sisestamise toimingutega võimalik. Kuid see maksab: B+ puusse sisestamised ja kustutamised maksavad O(log(N)). Sellepärast on mõned teist seda kuulnud liiga paljude indeksite kasutamine pole hea mõte. Tõesti, aeglustate rea kiiret lisamist/värskendamist/kustutamist tabelissest andmebaas peab värskendama tabeli indekseid, kasutades iga indeksi jaoks kallist O(log(N)) operatsiooni. Lisaks tähendab indeksite lisamine rohkem töökoormust tehingujuht (kirjeldatakse artikli lõpus).

Lisateavet leiate Vikipeedia artiklist B+Puu. Kui soovite näidet B+Tree rakendamisest andmebaasis, vaadake Selle artikli и Selle artikli juhtivalt MySQL-i arendajalt. Mõlemad keskenduvad sellele, kuidas InnoDB (MySQL-i mootor) indekseid käsitleb.

Märkus. Lugeja ütles mulle, et madala taseme optimeerimise tõttu peaks B+ puu olema täielikult tasakaalustatud.

Hashtable

Meie viimane oluline andmestruktuur on räsitabel. See on väga kasulik, kui soovite väärtusi kiiresti otsida. Veelgi enam, räsitabeli mõistmine aitab meil hiljem mõista ühist andmebaasi ühendamise operatsiooni, mida nimetatakse räsiliitumiseks ( hash liituda). Seda andmestruktuuri kasutab andmebaas ka teatud sisemiste asjade (nt. lukusta laud või puhverbassein, näeme mõlemat mõistet hiljem).

Räsitabel on andmestruktuur, mis leiab võtme järgi kiiresti elemendi. Räsitabeli koostamiseks peate määratlema:

• vihje teie elementide jaoks
• räsifunktsioon võtmete jaoks. Arvutatud võtmeräsid annavad elementide asukoha (nn segmendid ).
• klahvide võrdlemise funktsioon. Kui olete õige segmendi leidnud, peate selle võrdluse abil leidma segmendist otsitava elemendi.

Lihtne näide

Võtame selge näite:

Sellel räsitabelis on 10 segmenti. Kuna ma olen laisk, kujutasin ma ainult 5 segmenti, kuid ma tean, et sa oled tark, nii et ma lasen teil ülejäänud 5 omaette kujutada. Kasutasin võtme räsifunktsiooni modulo 10. Teisisõnu salvestan selle segmendi leidmiseks ainult elemendi võtme viimase numbri:

• kui viimane number on 0, langeb element segmenti 0,
• kui viimane number on 1, langeb element segmenti 1,
• kui viimane number on 2, langeb element piirkonda 2,
• ...

Võrdlusfunktsioon, mida ma kasutasin, on lihtsalt võrdsus kahe täisarvu vahel.

Oletame, et soovite hankida elemendi 78:

• Räsitabel arvutab räsikoodi 78 jaoks, mis on 8.
• Räsitabel vaatleb segmenti 8 ja esimene leitud element on 78.
• Ta tagastab teile kauba 78
• Otsing maksab ainult 2 toimingut (üks räsiväärtuse arvutamiseks ja teine ​​segmendi elemendi otsimiseks).

Oletame nüüd, et soovite hankida elemendi 59:

• Räsitabel arvutab räsikoodi 59 jaoks, mis on 9.
• Räsitabel otsib segmendis 9, esimene leitud element on 99. Kuna 99!=59, siis element 99 ei ole kehtiv element.
• Sama loogikat kasutades võetakse teine ​​element (9), kolmas (79), ..., viimane (29).
• Elementi ei leitud.
• Otsing maksis 7 operatsiooni.

Hea räsifunktsioon

Nagu näete, ei ole hind sõltuvalt otsitavast väärtusest sama!

Kui ma muudan nüüd võtme räsifunktsiooni modulo 1 000 000 (st võtan viimased 6 numbrit), maksab teine ​​otsing ainult 1 toimingu, kuna segmendis 000059 pole elemente. Tõeline väljakutse on leida hea räsifunktsioon, mis loob ämbrid, mis sisaldavad väga väikest arvu elemente.

Minu näites on hea räsifunktsiooni leidmine lihtne. Kuid see on lihtne näide, hea räsifunktsiooni leidmine on keerulisem, kui võti on:

• string (näiteks - perekonnanimi)
• 2 rida (näiteks - perekonnanimi ja eesnimi)
• 2 rida ja kuupäev (näiteks - perekonnanimi, eesnimi ja sünniaeg)
• ...

Hea räsifunktsiooni korral maksavad räsitabeli otsingud O(1).

Massiivi vs räsi tabel

Miks mitte kasutada massiivi?

Hmm, hea küsimus.

• Räsi tabel võib olla osaliselt mällu laaditud, ja ülejäänud segmendid võivad jääda kettale.
• Massiivi puhul peate kasutama mälus külgnevat ruumi. Kui laadite suurt lauda piisavalt pidevat ruumi on väga raske leida.
• Räsitabeli jaoks saate valida soovitud võtme (näiteks riigi ja isiku perekonnanime).

Lisateabe saamiseks võite lugeda artiklit JavaHashMap, mis on räsitabeli tõhus teostus; selles artiklis käsitletud mõistete mõistmiseks ei pea te Javast aru saama.

Allikas: www.habr.com