Hoi Habr! Ik presintearje jo oandacht de oersetting fan it artikel
"Hoe wurket in relaasje databank".

As it giet om relasjonele databases kin ik it net helpe om te tinken dat der wat mist. Se wurde oeral brûkt. D'r binne in protte ferskillende databases beskikber, fan 'e lytse en brûkbere SQLite oant de krêftige Teradata. Mar d'r binne mar in pear artikels dy't útlizze hoe't de databank wurket. Jo kinne foar josels sykje mei "howdoesarelationaldatabasework" om te sjen hoe min resultaten d'r binne. Boppedat binne dizze artikels koart. As jo op syk binne nei de lêste buzzy technologyen (BigData, NoSQL of JavaScript), sille jo mear yngeande artikels fine dy't útlizze hoe't se wurkje.

Binne relaasjedatabases te âld en te saai om bûten universitêre kursussen, ûndersykspapieren en boeken te ferklearjen?

As ûntwikkelder haatsje ik eat te brûken dat ik net begryp. En as databases mear as 40 jier brûkt wurde, moat der in reden wêze. Yn 'e rin fan' e jierren haw ik hûnderten oeren bestege om dizze frjemde swarte doazen wirklik te begripen dy't ik elke dei brûk. Relasjonele databases hiel nijsgjirrich omdat se basearre op brûkbere en werbrûkbere konsepten. As jo ynteressearre binne yn it begripen fan in databank, mar noch noait de tiid of oanstriid hawwe om yn dit brede ûnderwerp te ferdjipjen, moatte jo genietsje fan dit artikel.

Hoewol de titel fan dit artikel eksplisyt is, it doel fan dit artikel is net te begripen hoe't jo de databank brûke. Dêrom, jo moatte al witte hoe't jo in ienfâldich ferbiningsfersyk en basisfragen skriuwe RAU; oars kinne jo dit artikel net begripe. Dat is it iennichste dat jo witte moatte, ik sil de rest útlizze.

Ik sil begjinne mei guon kompjûterwittenskiplike basis, lykas tiidkompleksiteit fan algoritmen (BigO). Ik wit dat guon fan jo dit konsept haatsje, mar sûnder it sille jo de fynsinnigens yn 'e databank net kinne begripe. Om't dit in grut ûnderwerp is, Ik sil rjochtsje op wat ik tink is wichtich: hoe't de databank ferwurket SQL enkête. Ik sil mar foarstelle basis databank konseptensadat jo oan 'e ein fan it artikel in idee hawwe fan wat der ûnder de motorkap bart.

Sûnt dit in lang en technysk artikel is dat in protte algoritmen en gegevensstruktueren omfettet, nim dan jo tiid om it troch te lêzen. Guon begripen kinne lestich te begripen wêze; jo kinne se oerslaan en dochs it algemiene idee krije.

Foar de mear saakkundigen ûnder jo is dit artikel ferdield yn 3 dielen:

Oersjoch fan databasekomponinten op leech nivo en heech nivo
Oersjoch fan de Query Optimization proses
Oersjoch fan Transaksje en Buffer Pool Management

Werom nei de basis

Jierren lyn (yn in galaxy fier, fier fuort...) moasten ûntwikkelders krekt it oantal operaasjes witte dat se kodearren. Se wisten har algoritmen en gegevensstruktueren út 'e holle, om't se it net koenen betelje om de CPU en ûnthâld fan har trage kompjûters te fergriemen.

Yn dit diel sil ik jo herinnerje oan guon fan dizze begripen, om't se essensjeel binne foar it begripen fan 'e databank. Ik sil it konsept ek yntrodusearje databank yndeks.

O(1) vs O(n2)

Tsjintwurdich skele in protte ûntwikkelders net oer de tiidkompleksiteit fan algoritmen ... en se hawwe gelyk!

Mar as jo te krijen hawwe mei in protte gegevens (ik ha it net tûzenen) of as jo yn millisekonden wrakselje, wurdt it kritysk om dit konsept te begripen. En sa't jo jo kinne foarstelle, moatte databases mei beide situaasjes omgean! Ik sil jo net mear tiid meitsje dan nedich om it punt oer te bringen. Dit sil ús helpe it konsept fan kosten-basearre optimalisaasje letter te begripen (kosten basearre Optimisaasje).

Konsept

Tiid kompleksiteit fan it algoritme brûkt om te sjen hoe lang it sil nimme om in algoritme út te fieren foar in opjûne hoemannichte gegevens. Om dizze kompleksiteit te beskriuwen, brûke wy wiskundige notaasje grutte O. Dizze notaasje wurdt brûkt mei in funksje dy't beskriuwt hoefolle operaasjes in algoritme nedich is foar in opjûne oantal yngongen.

Bygelyks, as ik sis "dit algoritme hat kompleksiteit O (some_function ())", betsjut it dat it algoritme fereasket some_function (a_certain_amount_of_data) operaasjes foar it ferwurkjen fan in bepaalde hoemannichte gegevens.

sa It is net de hoemannichte gegevens dy't telt **,oars ** hoe't it oantal operaasjes nimt ta mei tanimmend gegevensvolumint. Tiid kompleksiteit jout gjin krekte oantal operaasjes, mar is in goede manier om te skatten útfiering tiid.

Yn dizze grafyk kinne jo it oantal operaasjes sjen tsjin it bedrach fan ynfiergegevens foar ferskate soarten algoritme-tiidkompleksiteiten. Ik brûkte in logaritmyske skaal om se wer te jaan. Mei oare wurden, de hoemannichte gegevens nimt gau ta fan 1 nei 1 miljard. Wy kinne sjen dat:

O(1) of konstante kompleksiteit bliuwt konstant (oars soe it net konstante kompleksiteit wurde neamd).
O(lochboek(n)) bliuwt leech sels mei miljarden gegevens.
De minste muoite - O(n2), wêr't it oantal operaasjes hurd groeit.
De oare twa komplikaasjes ferheegje like fluch.

foarbylden

Mei in lytse hoemannichte gegevens is it ferskil tusken O(1) en O(n2) negligible. Litte wy bygelyks sizze dat jo in algoritme hawwe dat 2000 eleminten moat ferwurkje.

It O(1)-algoritme sil jo 1 operaasje kostje
It O(log(n))-algoritme sil jo 7 operaasjes kostje
It O (n) algoritme sil jo 2 operaasjes kostje
It O(n*log(n))-algoritme kostet jo 14 operaasjes
It O (n2) algoritme sil jo 4 operaasjes kostje

It ferskil tusken O(1) en O(n2) liket grut (4 miljoen operaasjes), mar jo sille maksimaal 2 ms ferlieze, krekt tiid om jo eagen te knipperen. Yndie, moderne processors kinne ferwurkje hûnderten miljoenen operaasjes per sekonde. Dit is wêrom prestaasjes en optimalisaasje gjin probleem binne yn in protte IT-projekten.

Lykas ik sei, is it noch altyd wichtich om dit konsept te kennen as jo wurkje mei enoarme hoemannichten gegevens. As dizze kear it algoritme 1 eleminten moat ferwurkje (wat net sa folle is foar in databank):

It O(1)-algoritme sil jo 1 operaasje kostje
It O(log(n))-algoritme sil jo 14 operaasjes kostje
It O (n) algoritme sil jo 1 operaasjes kostje
It O(n*log(n))-algoritme kostet jo 14 operaasjes
It O(n2)-algoritme sil jo 1 operaasjes kostje

Ik haw de wiskunde net dien, mar ik soe sizze dat jo mei it O(n2)-algoritme tiid hawwe om in kofje te drinken (sels twa!). As jo in oare 0 tafoegje oan it gegevensvolume, sille jo tiid hawwe om in dutje te nimmen.

Litte wy djipper gean

Foar referinsje:

In goed opsykjen fan hash-tabel fynt in elemint yn O (1).
It sykjen fan in goed lykwichtige beam produkt resultaten yn O(log(n)).
It sykjen fan in array produkt resultaten yn O(n).
De bêste sortearalgoritmen hawwe kompleksiteit O(n*log(n)).
In min sortearingsalgoritme hat kompleksiteit O(n2).

Opmerking: Yn 'e folgjende dielen sille wy dizze algoritmen en gegevensstruktueren sjen.

D'r binne ferskate soarten algoritme-tiidkompleksiteit:

gemiddelde gefal senario
bêste gefal senario
en it slimste gefal

Tiid kompleksiteit is faak it slimste gefal senario.

Ik hie it allinich oer de tiidkompleksiteit fan it algoritme, mar kompleksiteit jildt ek foar:

ûnthâld konsumpsje fan it algoritme
skiif I / O konsumpsje algoritme

Fansels binne d'r komplikaasjes slimmer dan n2, bygelyks:

n4: dit is ferskriklik! Guon fan 'e neamde algoritmen hawwe dizze kompleksiteit.
3n: dit is noch slimmer! Ien fan 'e algoritmen sille wy sjen yn' e midden fan dit artikel hat dizze kompleksiteit (en it wurdt eins brûkt yn in protte databases).
factorial n: do silst nea krije jo resultaten sels mei in lyts bedrach fan gegevens.
nn: As jo dizze kompleksiteit tsjinkomme, moatte jo josels ôffreegje oft dit echt jo aktiviteitsfjild is ...

Opmerking: ik joech jo net de eigentlike definysje fan 'e grutte O-oantsjutting, gewoan in idee. Jo kinne dit artikel lêze op Wikipedia foar de echte (asymptotyske) definysje.

MergeSort

Wat dogge jo as jo in kolleksje sortearje moatte? Wat? Jo neame de sort () funksje ... Ok, goed antwurd ... Mar foar in databank, Jo moatte begripe hoe't dizze soarte () funksje wurket.

D'r binne ferskate goede sortearalgoritmen, dus ik sil my rjochtsje op it wichtichste: sortearje gearfoegje. Jo kinne miskien net begripe wêrom't sortearjen fan gegevens op it stuit nuttich is, mar jo moatte nei it queryoptimalisaasjediel. Boppedat sil it begripen fan merge sort helpe ús letter te begripen fan 'e mienskiplike databank join operaasje neamd fusearje join (fúzjeferiening).

Fusearje

Lykas in protte nuttige algoritmen, fertrout sortearje op in trúk: it kombinearjen fan 2 sortearre arrays fan grutte N/2 yn in N-elemint sortearre array kostet mar N operaasjes. Dizze operaasje wurdt gearfoegjen neamd.

Litte wy sjen wat dit betsjut mei in ienfâldich foarbyld:

Dizze figuer lit sjen dat om de úteinlike sortearre 8-elemint array te bouwen, jo mar ien kear oer de 2 4-elemint arrays moatte iterearje. Sûnt beide 4-elemint arrays binne al sortearre:

1) jo fergelykje beide aktuele eleminten yn twa arrays (oan it begjin aktueel = earst)
2) nim dan de lytste om it yn in 8 elemint array te setten
3) en gean nei it folgjende elemint yn 'e array wêr't jo it lytste elemint hawwe nommen
en werhelje 1,2,3 oant jo berikke it lêste elemint fan ien fan de arrays.
Dan nimme jo de oerbleaune eleminten fan 'e oare array om se yn in 8 elemint array te setten.

Dit wurket omdat beide 4-elemint arrays wurde sortearre en dus jo hoege net te "werom" yn dy arrays.

No't wy de trúk begripe, hjir is myn pseudokoade foar gearfoeging:

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;

Merge sort brekt in probleem yn lytsere problemen en fynt dan de resultaten fan 'e lytsere problemen om it resultaat fan it orizjinele probleem te krijen (notysje: dit soarte algoritme wurdt divide and conquer neamd). As jo dit algoritme net begripe, meitsje jo gjin soargen; Ik begriep it net de earste kear dat ik it seach. As it jo kin helpe, sjoch ik dit algoritme as in twa-faze algoritme:

Division faze, dêr't de array is ferdield yn lytsere arrays
De sortearring faze is dêr't lytse arrays wurde kombinearre (mei help fan union) te foarmjen in grutter array.

Divyzje faze

Yn 'e divyzjestage wurdt de array ferdield yn ienheidsarrays yn 3 stappen. It formele oantal stappen is log(N) (sûnt N=8, log(N) = 3).

Hoe kin ik dit witte?

Ik bin geniaal! Yn in wurd - wiskunde. It idee is dat elke stap dielt de grutte fan 'e orizjinele array troch 2. It oantal stappen is it oantal kearen dat jo de orizjinele array yn twa dielen kinne. Dit is de krekte definysje fan in logaritme (basis 2).

Sortearje faze

Yn 'e sortearfaze begjinne jo mei unitêre (single-elemint) arrays. Tidens elke stap tapasse jo meardere gearfoegingsoperaasjes en de totale kosten binne N = 8 operaasjes:

Yn 'e earste etappe hawwe jo 4 fúzjes dy't elk 2 operaasjes kostje
Yn 'e twadde stap hawwe jo 2 fúzjes dy't elk 4 operaasjes kostje
Yn 'e tredde stap hawwe jo 1 fúzje dy't 8 operaasjes kostet

Om't d'r log(N) stappen binne, totale kosten N * log(N) operaasjes.

Foardielen fan fusearje sort

Wêrom is dit algoritme sa machtich?

Omdat:

Jo kinne it feroarje om de ûnthâldfoetôfdruk te ferminderjen, sadat jo gjin nije arrays meitsje, mar de ynfier-array direkt wizigje.

Opmerking: dit soarte algoritme wurdt neamd in-plak (soarte sûnder ekstra ûnthâld).

Jo kinne it feroarje om skiifromte en in lyts bedrach fan ûnthâld tagelyk te brûken sûnder signifikante skiif I / O-overhead te meitsjen. It idee is om allinich de dielen yn it ûnthâld te laden dy't op it stuit wurde ferwurke. Dit is wichtich as jo moatte sortearje in multi-gigabyte tabel mei mar in 100-megabyte ûnthâld buffer.

Opmerking: dit soarte algoritme wurdt neamd eksterne soarte.

Jo kinne it feroarje om te rinnen op meardere prosessen/threads/servers.

Bygelyks, ferdielde fúzjesoarte is ien fan 'e wichtichste komponinten Hadoop (dat is in struktuer yn grutte data).

Dit algoritme kin lead yn goud feroarje (echt!).

Dit sortearalgoritme wurdt brûkt yn 'e measte (as net alle) databases, mar it is net de ienige. As jo mear witte wolle, kinne jo dit lêze ûndersyk wurk, dy't de foar- en neidielen besprekt fan mienskiplike algoritmen foar sortearring fan databases.

Array, Tree en Hash Tabel

No't wy it idee fan tiidkompleksiteit en sortearring begripe, soe ik jo moatte fertelle oer 3 gegevensstruktueren. Dit is wichtich omdat se binne de basis fan moderne databases. Ik sil ek it konsept yntrodusearje databank yndeks.

Массив

In twadiminsjonale array is de ienfâldichste gegevensstruktuer. In tabel kin tocht wurde as in array. Bygelyks:

Dizze 2-diminsjonale array is in tabel mei rigen en kolommen:

Elke line stiet foar in entiteit
Kolommen bewarje eigenskippen dy't de entiteit beskriuwe.
Elke kolom bewarret gegevens fan in spesifyk type (integer, tekenrige, datum ...).

Dit is handich foar it bewarjen en visualisearjen fan gegevens, lykwols, as jo in spesifike wearde moatte fine, is dit net geskikt.

As jo bygelyks alle jonges wolle fine dy't yn it Feriene Keninkryk wurkje, moatte jo elke rige besjen om te bepalen oft dy rige ta it Feriene Keninkryk heart. It kostet jo N transaksjeswêr N - oantal rigels, dat is net min, mar koe der in fluggere manier? No is it tiid foar ús om yn 'e kunde te kommen mei de beammen.

Opmerking: De measte moderne databases jouwe útwreide arrays foar it effisjint opslaan fan tabellen: heap-organisearre tabellen en yndeks-organisearre tabellen. Mar dit feroaret net it probleem om fluch in spesifike betingst te finen yn in groep kolommen.

Databankbeam en yndeks

In binêre sykbeam is in binêre beam mei in spesjale eigenskip, de kaai by elke node moat wêze:

grutter as alle kaaien opslein yn de linker subtree
minder as alle kaaien opslein yn de rjochter subtree

Litte wy sjen wat dit visueel betsjut

Idea

Dizze beam hat N = 15 eleminten. Litte wy sizze dat ik nei 208 sykje:

Ik begjin by de root wêrfan de kaai 136 is. Sûnt 136<208 sjoch ik nei de rjochter subtree fan node 136.
398>208 dêrom sjoch ik nei de linker subtree fan node 398
250>208 dêrom sjoch ik nei de linker subtree fan node 250
200<208, dêrom sjoch ik nei de rjochter subtree fan node 200. Mar 200 hat gjin rjochter subtree, wearde bestiet net (want as it bestiet, sil it yn 'e rjochter subtree 200 wêze).

Litte wy no sizze dat ik 40 sykje

Ik begjin by de root wêrfan de kaai 136 is. Sûnt 136 > 40 sjoch ik nei de linker subtree fan node 136.
80 > 40, dêrom sjoch ik nei de linker subtree fan knooppunt 80
40= 40, node bestiet. Ik helje de rige ID binnen it knooppunt (net op 'e foto) en sjoch yn' e tabel foar de opjûne rige ID.
It witten fan de rige ID lit my krekt witte wêr't de gegevens yn 'e tabel binne, sadat ik it direkt kin ophelje.

Op it lêst sille beide sykopdrachten my it oantal nivo's yn 'e beam kostje. As jo it diel oer sortearje gearfoegje, moatte jo sjen dat d'r log (N) nivo's binne. It docht bliken, sykkosten log(N), net min!

Lit ús weromgean nei ús probleem

Mar dit is heul abstrakt, dus litte wy weromgean nei ús probleem. Ynstee fan in ienfâldich hiel getal, stel jo in tekenrige foar dy't it lân fan immen yn 'e foarige tabel fertsjintwurdiget. Litte wy sizze dat jo in beam hawwe dy't it "lân" fjild (kolom 3) fan 'e tabel befettet:

As jo wolle witte wa't wurket yn it Feriene Keninkryk
jo sjogge nei de beam om it knooppunt te krijen dat Grut-Brittanje fertsjintwurdiget
binnen "UKnode" fine jo de lokaasje fan UK worker records.

Dizze sykopdracht kostet log(N) operaasjes ynstee fan N operaasjes as jo de array direkt brûke. Wat jo krekt presintearre wie databank yndeks.

Jo kinne in yndeksbeam bouwe foar elke groep fjilden (string, nûmer, 2 rigels, nûmer en tekenrige, datum ...) sa lang as jo in funksje hawwe om toetsen te fergelykjen (dus fjildgroepen) sadat jo ynstelle kinne oarder tusken de kaaien (wat it gefal is foar alle basistypen yn 'e databank).

B+TreeIndex

Wylst dizze beam goed wurket foar it krijen fan in spesifike wearde, is d'r in GROOT probleem as jo nedich binne krije meardere eleminten tusken twa wearden. Dit sil O(N) kostje, om't jo elke knooppunt yn 'e beam moatte besjen en kontrolearje oft it tusken dizze twa wearden is (bgl. Boppedat, dizze operaasje is net skiif I / O freonlik sûnt jo moatte lêze de hiele beam. Wy moatte in manier fine om effisjint út te fieren berik fersyk. Om dit probleem op te lossen, brûke moderne databases in wizige ferzje fan 'e foarige beam neamd B + Tree. Yn in B+beambeam:

allinnich de leechste knopen (blêden) winkel ynformaasje (lokaasje fan rigen yn 'e relatearre tabel)
de rest fan de knopen binne hjir foar routing nei it juste knooppunt by syktocht.

Sa't jo sjen kinne, binne d'r mear knopen hjir (twa kear). Ja, jo hawwe ekstra knopen, "beslútknooppunten", dy't jo helpe om it juste knooppunt te finen (dy't de lokaasje fan 'e rigen yn' e assosjearre tabel bewarret). Mar de sykkompleksiteit is noch altyd O(log(N)) (der is mar ien nivo mear). It grutte ferskil is dat knopen op it legere nivo binne ferbûn mei har opfolgers.

Mei dizze B + Tree, as jo op syk binne nei wearden tusken 40 en 100:

Jo moatte gewoan sykje nei 40 (of de tichtste wearde nei 40 as 40 net bestiet) lykas jo dien hawwe mei de foarige beam.
Sammelje dan 40 erfgenamten mei direkte erfgenamten oant jo 100 berikke.

Litte wy sizze dat jo M-opfolgers fine en de beam hat N knopen. It finen fan in spesifyk knooppunt kostet log (N) lykas de foarige beam. Mar as jo ienris dizze knooppunt krije, sille jo M-opfolgers krije yn M-operaasjes mei ferwizings nei har opfolgers. Dizze sykopdracht kostet allinnich M+log(N) operaasjes ferlike mei N operaasjes op de foarige beam. Boppedat hoege jo net de folsleine beam te lêzen (allinich M+log(N) knopen), wat minder skiifgebrûk betsjut. As M is lyts (bgl. 200 rows) en N is grut (1 rows), der sil in GROOT ferskil.

Mar der binne nije problemen hjir (wer!). As jo in rige tafoegje of wiskje yn 'e databank (en dus yn 'e assosjearre B+Tree-yndeks):

jo moatte oarder hâlde tusken de knopen yn in B+Tree, oars kinne jo de knopen yn in net-sortearre beam net fine.
jo moatte it minimaal mooglike oantal nivo's yn B+Tree hâlde, oars wurdt de O(log(N)) tiidkompleksiteit O(N).

Mei oare wurden, B+Tree moat selsbestelle en lykwichtich wêze. Gelokkich is dit mooglik mei smart wiskje en ynfoegje operaasjes. Mar dit komt op kosten: ynfoegingen en wiskjen yn in B+-beam kostje O(log(N)). Dêrom hawwe guon fan jimme dat heard it brûken fan tefolle yndeksen is gjin goed idee. Werklik, jo fertrage fluch ynfoegje / update / wiskje fan in rige yn in tabelom't de databank de yndeksen fan 'e tabel moat bywurkje mei in djoere O (log (N)) operaasje foar elke yndeks. Boppedat betsjut it tafoegjen fan yndeksen mear wurkdruk foar transaksje manager (sil wurde beskreaun oan 'e ein fan it artikel).

Foar mear details kinne jo it Wikipedia-artikel sjen oer B+Beam. As jo in foarbyld wolle fan ymplemintaasje fan B + Tree yn in databank, sjoch dan ris dit artikel и dit artikel fan in liedende MySQL-ûntwikkelder. Se rjochtsje har beide op hoe't InnoDB (de MySQL-motor) yndeksen behannelet.

Opmerking: In lêzer fertelde my dat, troch optimisaasjes op leech nivo, de B + beam folslein balansearre moat wêze.

Hastabel

Us lêste wichtige gegevensstruktuer is de hash-tabel. Dit is heul handich as jo wearden fluch wolle opsykje. Boppedat sil it begripen fan in hash-tabel ús letter helpe om in mienskiplike databank-join-operaasje te begripen neamd in hash join ( hash join). Dizze gegevensstruktuer wurdt ek brûkt troch de databank om guon ynterne dingen op te slaan (bgl. slot tafel of buffer pool, sille wy beide begripen letter sjen).

In hash-tabel is in gegevensstruktuer dy't fluch in elemint fynt op basis fan syn kaai. Om in hash-tabel te bouwen moatte jo definiearje:

clue foar jo eleminten
hash funksje foar kaaien. De berekkene kaai-hashes jouwe de lokaasje fan 'e eleminten (neamd segminten ).
funksje foar it fergelykjen fan toetsen. As jo ienris it juste segmint hawwe fûn, moatte jo it elemint fine wêr't jo nei sykje binnen it segmint mei dizze fergeliking.

In ienfâldich foarbyld

Litte wy in dúdlik foarbyld nimme:

Dizze hash-tabel hat 10 segminten. Om't ik lui bin, haw ik mar 5 segminten ôfbylde, mar ik wit dat jo tûk binne, dus ik lit jo de oare 5 op jo eigen ôfbyldzje. Ik brûkte in hash funksje modulo 10 fan de kaai. Mei oare wurden, ik bewarje allinich it lêste sifer fan 'e kaai fan it elemint om syn segmint te finen:

as it lêste sifer 0 is, falt it elemint yn segment 0,
as it lêste sifer 1 is, falt it elemint yn segment 1,
as it lêste sifer 2 is, falt it elemint yn gebiet 2,
...

De ferlikingsfunksje dy't ik brûkte is gewoan gelikensens tusken twa heule getallen.

Litte wy sizze dat jo elemint 78 krije wolle:

De hash-tabel berekkent de hash-koade foar 78, dat is 8.
De hash-tabel sjocht nei segmint 8, en it earste elemint dat it fynt is 78.
Se jout item 78 oan dy werom
Sykje kostet mar 2 operaasjes (ien om de hashwearde te berekkenjen en de oare om it elemint binnen it segmint op te sykjen).

Litte wy no sizze dat jo elemint 59 krije wolle:

De hash-tabel berekkent de hash-koade foar 59, dat is 9.
De hash-tabel siket yn segmint 9, it earste fûnemint is 99. Sûnt 99!=59 is elemint 99 gjin jildich elemint.
Mei deselde logika wurde it twadde elemint (9), de tredde (79), ..., de lêste (29) nommen.
Elemint net fûn.
It sykjen koste 7 operaasjes.

Goede hashfunksje

Sa't jo sjen kinne, ôfhinklik fan de wearde dy't jo sykje, de kosten binne net itselde!

As ik no de hashfunksje modulo 1 fan 'e kaai feroarje (dat is, de lêste 000 sifers nimme), kostet de twadde opsykje allinich 000 operaasje, om't d'r gjin eleminten binne yn segment 6. De echte útdaging is om in goede hashfunksje te finen dy't bakken sil meitsje mei in heul lyts oantal eleminten.

Yn myn foarbyld is it finen fan in goede hashfunksje maklik. Mar dit is in ienfâldich foarbyld, it finen fan in goede hashfunksje is dreger as de kaai is:

string (bygelyks - achternamme)
2 rigels (bygelyks - achternamme en foarnamme)
2 rigels en datum (bygelyks - achternamme, foarnamme en bertedatum)
...

Mei in goede hashfunksje kostje hash-tabelopsykjen O(1).

Array vs hash tabel

Wêrom net in array brûke?

Hmm, goede fraach.

De hashtafel kin wêze foar in part laden yn it ûnthâld, en de oerbleaune segminten kinne bliuwe op 'e skiif.
Mei in array moatte jo trochgeande romte yn it ûnthâld brûke. As jo laden in grutte tafel it is heul lestich om genôch trochgeande romte te finen.
Foar in hash tabel, kinne jo selektearje de kaai jo wolle (Bygelyks, lân en persoan syn efternamme).

Foar mear ynformaasje kinne jo it artikel lêze oer JavaHashMap, dat is in effisjinte ymplemintaasje fan in hash tabel; jo hoege Java net te begripen om de begripen te begripen dy't yn dit artikel behannele wurde.

Boarne: www.habr.com

Hoe relaasjedatabases wurkje (diel 1)