Hæ Habr! Ég kynni þér þýðingu greinarinnar
"Hvernig virkar venslagagnagrunnur".

Þegar kemur að venslagagnagrunnum get ég ekki annað en haldið að eitthvað vanti. Þau eru notuð alls staðar. Það eru margir mismunandi gagnagrunnar í boði, allt frá litlu og gagnlegu SQLite til öflugs Teradata. En það eru aðeins nokkrar greinar sem útskýra hvernig gagnagrunnurinn virkar. Þú getur leitað sjálfur með því að nota „howdoesarelationaldatabasework“ til að sjá hversu fáar niðurstöður eru. Þar að auki eru þessar greinar stuttar. Ef þú ert að leita að nýjustu buzzy tækninni (BigData, NoSQL eða JavaScript), muntu finna ítarlegri greinar sem útskýra hvernig þær virka.

Eru tengslagagnagrunnar of gamlir og of leiðinlegir til að hægt sé að útskýra þau utan háskólanámskeiða, rannsóknarritgerða og bóka?

Sem verktaki hata ég að nota eitthvað sem ég skil ekki. Og ef gagnagrunnar hafa verið notaðir í meira en 40 ár hlýtur það að vera ástæða. Í gegnum árin hef ég eytt hundruðum klukkustunda í að skilja þessa undarlegu svörtu kassa sem ég nota á hverjum degi. Venslagagnagrunnar mjög áhugavert vegna þess að þeir byggt á gagnlegum og endurnýtanlegum hugtökum. Ef þú hefur áhuga á að skilja gagnagrunn, en hefur aldrei haft tíma eða tilhneigingu til að kafa ofan í þetta víðtæka efni, ættir þú að njóta þessarar greinar.

Þó fyrirsögn þessarar greinar sé skýr, tilgangur þessarar greinar er ekki að skilja hvernig á að nota gagnagrunninn. Þess vegna, þú ættir nú þegar að vita hvernig á að skrifa einfalda tengingarbeiðni og grunnfyrirspurnir SKRÁ; annars skilurðu kannski ekki þessa grein. Það er það eina sem þú þarft að vita, ég skal útskýra restina.

Ég mun byrja á nokkrum grunnatriðum í tölvunarfræði, eins og tímaflækju reiknirit (BigO). Ég veit að sum ykkar hata þetta hugtak, en án þess muntu ekki geta skilið ranghala gagnagrunninn. Þar sem þetta er stórt umræðuefni, Ég mun einbeita mér að það sem mér finnst mikilvægt: hvernig gagnagrunnurinn vinnur SQL fyrirspurn. Ég skal bara kynna grunnhugtök gagnagrunnsþannig að í lok greinarinnar hefurðu hugmynd um hvað er að gerast undir hettunni.

Þar sem þetta er löng og tæknileg grein sem felur í sér mikið af reikniritum og gagnaskipulagi, gefðu þér tíma til að lesa í gegnum hana. Sum hugtök geta verið erfið að skilja; þú getur sleppt þeim og samt fengið almenna hugmynd.

Fyrir þá sem eru fróðari meðal ykkar er þessari grein skipt í 3 hluta:

Yfirlit yfir gagnagrunnshluta á lágu og háu stigi
Yfirlit yfir hagræðingarferli fyrirspurna
Yfirlit yfir stjórnun viðskipta og biðminni

Aftur í grunnatriði

Fyrir mörgum árum (í vetrarbraut langt, langt í burtu...) þurftu verktaki að vita nákvæmlega fjölda aðgerða sem þeir voru að kóða. Þeir kunnu reiknirit sín og gagnauppbyggingu utanbókar vegna þess að þeir höfðu ekki efni á að sóa örgjörvanum og minni hægu tölvunnar sinna.

Í þessum hluta mun ég minna þig á sum þessara hugtaka þar sem þau eru nauðsynleg til að skilja gagnagrunninn. Ég mun einnig kynna hugtakið gagnagrunnsvísitölu.

O(1) á móti O(n2)

Nú á dögum er mörgum forriturum sama um hversu flókið tíma reiknirit eru... og það er rétt!

En þegar þú ert að fást við mikið af gögnum (ég er ekki að tala um þúsundir) eða ef þú ert að berjast á millisekúndum, verður mikilvægt að skilja þetta hugtak. Og eins og þú getur ímyndað þér þurfa gagnagrunnar að takast á við báðar aðstæður! Ég mun ekki láta þig eyða meiri tíma en nauðsynlegt er til að koma málinu á framfæri. Þetta mun hjálpa okkur að skilja hugtakið kostnaðarmiðaða hagræðingu síðar (kostnaður byggt hagræðingu).

Hugtak

Tímaflókið reiknirit notað til að sjá hversu langan tíma reiknirit mun taka að klára fyrir tiltekið magn gagna. Til að lýsa þessum margbreytileika notum við stóra O stærðfræðilega nótnaskrift. Þessi nótnaskrift er notuð með falli sem lýsir hversu margar aðgerðir reiknirit þarf fyrir tiltekinn fjölda inntak.

Til dæmis, þegar ég segi "þetta reiknirit hefur flókið O(einhver_fall())", þá þýðir það að reikniritið krefst einhvers_falls(a_vissu_magns_gagna) til að vinna ákveðið magn af gögnum.

Í þessu tilviki, Það er ekki magn gagna sem skiptir máli**, annars ** hvernig aðgerðum fjölgar með auknu gagnamagni. Tímaflæki gefur ekki upp nákvæman fjölda aðgerða, en er góð leið til að áætla framkvæmdartíma.

Í þessu grafi er hægt að sjá fjölda aðgerða á móti magni inntaksgagna fyrir mismunandi gerðir af algrím tímaflækju. Ég notaði lógaritmískan kvarða til að sýna þær. Með öðrum orðum, magn gagna eykst fljótt úr 1 í 1 milljarð. Við getum séð að:

O(1) eða stöðugur margbreytileiki helst stöðugur (annars væri það ekki kallað stöðugt flækjustig).
O(skrá(n)) helst lágt jafnvel með milljarða gagna.
Verstu erfiðleikar - O(n2), þar sem aðgerðum fjölgar hratt.
Hinir tveir fylgikvillarnir aukast jafn hratt.

dæmi

Með lítið magn af gögnum er munurinn á O(1) og O(n2) hverfandi. Segjum til dæmis að þú sért með reiknirit sem þarf að vinna úr 2000 þáttum.

O(1) reikniritið mun kosta þig 1 aðgerð
O(log(n)) reikniritið mun kosta þig 7 aðgerðir
O(n) reikniritið mun kosta þig 2 aðgerðir
O(n*log(n)) reikniritið mun kosta þig 14 aðgerðir
O(n2) reikniritið mun kosta þig 4 aðgerðir

Munurinn á O(1) og O(n2) virðist mikill (4 milljónir aðgerða) en þú munt missa að hámarki 2 ms, bara kominn tími til að blikka augunum. Reyndar geta nútíma örgjörvar unnið hundruð milljóna aðgerða á sekúndu. Þetta er ástæðan fyrir því að árangur og hagræðing eru ekki vandamál í mörgum upplýsingatækniverkefnum.

Eins og ég sagði er samt mikilvægt að þekkja þetta hugtak þegar unnið er með mikið magn af gögnum. Ef að þessu sinni þarf reikniritið að vinna úr 1 þáttum (sem er ekki svo mikið fyrir gagnagrunn):

O(1) reikniritið mun kosta þig 1 aðgerð
O(log(n)) reikniritið mun kosta þig 14 aðgerðir
O(n) reikniritið mun kosta þig 1 aðgerðir
O(n*log(n)) reikniritið mun kosta þig 14 aðgerðir
O(n2) reikniritið mun kosta þig 1 aðgerðir

Ég hef ekki reiknað út, en ég myndi segja að með O(n2) reikniritinu hefurðu tíma til að drekka kaffi (jafnvel tvö!). Ef þú bætir öðru 0 við gagnamagnið hefurðu tíma til að taka þér blund.

Við skulum fara dýpra

Fyrir þinn upplýsingar:

Góð kjötkássatöfluleit finnur stak í O(1).
Leit í tré sem er í góðu jafnvægi gefur niðurstöður í O(log(n)).
Leit í fylki gefur niðurstöður í O(n).
Bestu flokkunaralgrímin hafa margbreytileikann O(n*log(n)).
Slæmt flokkunaralgrím hefur margbreytileika O(n2).

Athugið: Í eftirfarandi hlutum munum við sjá þessi reiknirit og gagnaskipulag.

Það eru nokkrar gerðir af tímaflækju reiknirit:

meðaltilvik
besta tilfelli
og í versta falli

Tímaflókið er oft versta tilvikið.

Ég var aðeins að tala um tímaflækju reikniritsins, en flókið á einnig við um:

minnisnotkun reikniritsins
diskur I/O neyslu reiknirit

Auðvitað eru fylgikvillar verri en n2, til dæmis:

n4: þetta er hræðilegt! Sumar af nefndum reikniritum hafa þetta flókið.
3n: þetta er enn verra! Eitt af reikniritunum sem við munum sjá í miðri þessari grein hefur þessa margbreytileika (og það er reyndar notað í mörgum gagnagrunnum).
þáttabundið n: þú munt aldrei fá niðurstöður þínar jafnvel með lítið magn af gögnum.
nn: Ef þú lendir í þessum margbreytileika ættirðu að spyrja sjálfan þig hvort þetta sé virkilega þitt starfssvið...

Athugið: Ég gaf þér ekki raunverulega skilgreiningu á stóru O merkingunni, bara hugmynd. Þú getur lesið þessa grein á Wikipedia fyrir raunverulega (einkennalausa) skilgreiningu.

MergeSort

Hvað gerir þú þegar þú þarft að flokka safn? Hvað? Þú kallar sort() aðgerðina... Allt í lagi, gott svar... En fyrir gagnagrunn verður þú að skilja hvernig þessi sort() aðgerð virkar.

Það eru nokkrir góðir flokkunaralgrím, svo ég mun einbeita mér að því mikilvægasta: sameina flokk. Þú skilur kannski ekki hvers vegna flokkun gagna er gagnleg núna, en þú ættir að fara eftir fínstillingarhluta fyrirspurnarinnar. Þar að auki, skilningur á sameiningu mun hjálpa okkur síðar að skilja algengu gagnagrunnstengingaraðgerðina sem kallast sameinast taka þátt (sameiningarfélag).

Sameina

Eins og mörg gagnleg reiknirit, byggir sameinuð flokkun á brellu: að sameina 2 flokkaðar fylki af stærð N/2 í N-þátta flokkað fylki kostar aðeins N aðgerðir. Þessi aðgerð er kölluð sameining.

Við skulum sjá hvað þetta þýðir með einföldu dæmi:

Þessi mynd sýnir að til að byggja upp endanlega flokkaða 8-þátta fylkið þarftu aðeins að endurtaka einu sinni yfir 2 4-eininga fylkin. Þar sem bæði 4-eininga fylkin eru þegar flokkuð:

1) þú berð saman báða núverandi þættina í tveimur fylkjum (í upphafi núverandi = fyrst)
2) taktu síðan þann minnsta til að setja hann í 8 frumefni fylki
3) og farðu í næsta stak í fylkinu þar sem þú tókst minnsta þáttinn
og endurtaktu 1,2,3 þar til þú nærð síðasta þætti eins af fylkjunum.
Síðan tekur þú þá þætti sem eftir eru af hinu fylkinu til að setja þá í 8 þátta fylki.

Þetta virkar vegna þess að bæði 4-þátta fylkin eru flokkuð og svo þú þarft ekki að "fara til baka" í þessum fylkjum.

Nú þegar við skiljum bragðið, hér er gervikóði minn fyrir sameiningu:

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;

Sameina flokkun skiptir vandamáli í smærri verkefni og finnur síðan niðurstöður smærri vandamála til að fá niðurstöðu upprunalega vandamálsins (ath. þessi tegund reiknirit er kallað deila og sigra). Ef þú skilur ekki þetta reiknirit skaltu ekki hafa áhyggjur; Ég skildi það ekki í fyrsta skipti sem ég sá það. Ef það getur hjálpað þér, lít ég á þetta reiknirit sem tveggja fasa reiknirit:

Deilingarfasa, þar sem fylkinu er skipt í smærri fylki
Flokkunarfasinn er þar sem lítil fylki eru sameinuð (með því að nota sameiningu) til að mynda stærra fylki.

Deildaráfangi

Í skiptingarstiginu er fylkinu skipt í einingafylki í 3 þrepum. Formlegur fjöldi þrepa er log(N) (þar sem N=8, log(N) = 3).

Hvernig veit ég þetta?

ég er snillingur! Í einu orði sagt - stærðfræði. Hugmyndin er sú að hvert skref deilir stærð upprunalegu fylkisins með 2. Fjöldi þrepa er fjöldi skipta sem hægt er að skipta upprunalegu fylkinu í tvennt. Þetta er nákvæm skilgreining á lógaritma (grunnur 2).

Flokkunarfasi

Í flokkunarfasanum byrjarðu með eininga fylki (einn þáttur). Í hverju skrefi notar þú margar sameiningaraðgerðir og heildarkostnaður er N = 8 aðgerðir:

Á fyrsta stigi ertu með 4 sameiningar sem kosta 2 aðgerðir hver
Í öðru skrefi ertu með 2 sameiningar sem kosta 4 aðgerðir hver
Í þriðja skrefi ertu með 1 sameiningu sem kostar 8 aðgerðir

Þar sem það eru log(N) skref, heildarkostnaður N * log(N) aðgerðir.

Kostir samrunategundar

Af hverju er þetta reiknirit svona öflugt?

Vegna þess að:

Þú getur breytt því til að minnka minnisfótsporið þannig að þú býrð ekki til nýjar fylki heldur breytir inntaksfylki beint.

Athugið: Þessi tegund af reiknirit er kölluð in-staður (raða án viðbótarminni).

Þú getur breytt því til að nota diskpláss og lítið magn af minni á sama tíma án þess að hafa verulegan I/O kostnað á disknum. Hugmyndin er að hlaða aðeins inn í minnið þá hluta sem eru í vinnslu. Þetta er mikilvægt þegar þú þarft að flokka multi-gígabæta töflu með aðeins 100 megabæta minni biðminni.

Athugið: Þessi tegund af reiknirit er kölluð ytri tegund.

Þú getur breytt því til að keyra á mörgum ferlum/þráðum/þjónum.

Til dæmis er dreifð samrunaflokkun einn af lykilþáttunum Hadoop (sem er uppbygging í stórum gögnum).

Þetta reiknirit getur breytt blýi í gull (í alvöru!).

Þetta flokkunaralgrím er notað í flestum (ef ekki öllum) gagnagrunnum, en það er ekki það eina. Ef þú vilt vita meira geturðu lesið þetta rannsóknarvinnu, sem fjallar um kosti og galla algengra gagnagrunnsflokkunaralgríma.

Fylki, tré og kjötkássatöflu

Nú þegar við skiljum hugmyndina um flókið tíma og flokkun ætti ég að segja þér frá 3 gagnaskipulagi. Þetta er mikilvægt vegna þess að þeir eru undirstaða nútíma gagnagrunna. Ég mun einnig kynna hugtakið gagnagrunnsvísitölu.

Array

Tvívítt fylki er einfaldasta gagnauppbyggingin. Líta má á borð sem fylki. Til dæmis:

Þetta tvívíddar fylki er tafla með línum og dálkum:

Hver lína táknar einingu
Dálkar geyma eiginleika sem lýsa einingunni.
Hver dálkur geymir gögn af ákveðinni gerð (heiltala, strengur, dagsetning...).

Þetta er þægilegt til að geyma og sjá gögn, en þegar þú þarft að finna ákveðið gildi hentar þetta ekki.

Til dæmis, ef þú vilt finna alla krakkana sem vinna í Bretlandi, þarftu að skoða hverja röð til að ákvarða hvort sú röð tilheyri Bretlandi. Það mun kosta þig N viðskiptihvar N - fjöldi lína, sem er ekki slæmt, en gæti verið hraðari leið? Nú er komið að því að við kynnumst trjánum.

Athugið: Flestir nútíma gagnagrunnar bjóða upp á útbreidd fylki til að geyma töflur á skilvirkan hátt: hrúguskipulagðar töflur og vísitöluskipulagðar töflur. En þetta breytir ekki vandamálinu við að finna fljótt ákveðið ástand í hópi dálka.

Gagnagrunnstré og vísitala

Tvíundarleitartré er tvíundartré með sérstakan eiginleika, lykillinn á hverjum hnút verður að vera:

stærri en allir takkarnir sem eru geymdir í vinstra undirtrénu
minna en allir lyklar sem eru geymdir í hægra undirtrénu

Við skulum sjá hvað þetta þýðir sjónrænt

Hugmynd

Þetta tré hefur N = 15 frumefni. Segjum að ég sé að leita að 208:

Ég byrja á rótinni þar sem lykillinn er 136. Þar sem 136<208 horfi ég á hægri undirtré hnút 136.
398>208 þess vegna er ég að horfa á vinstra undirtré hnút 398
250>208 þess vegna er ég að horfa á vinstra undirtré hnút 250
200<208, þess vegna er ég að horfa á hægri undirtré hnút 200. En 200 hefur ekkert rétt undirtré, gildi er ekki til (því ef það er til þá verður það í hægri undirtrénu 200).

Segjum nú að ég sé að leita að 40

Ég byrja á rótinni þar sem lykillinn er 136. Þar sem 136 > 40 horfi ég á vinstri undirtré hnút 136.
80 > 40, þess vegna er ég að horfa á vinstri undirtré hnút 80
40= 40, hnútur er til. Ég sæki raðauðkennið inni í hnútnum (ekki sýnt á myndinni) og leita í töflunni fyrir uppgefið raðauðkenni.
Með því að þekkja línuauðkennið veit ég nákvæmlega hvar gögnin eru í töflunni, svo ég get sótt þau samstundis.

Að lokum mun báðar leitirnar kosta mig fjölda stiga inni í trénu. Ef þú lest hlutann um samrunaflokk vandlega ættirðu að sjá að það eru log(N) stig. Það kemur í ljós, leitarkostnaðarskrá(N), ekki slæmt!

Snúum okkur aftur að vandamáli okkar

En þetta er mjög abstrakt, svo við skulum snúa okkur aftur að vandamálinu. Í stað einfaldrar heiltölu, ímyndaðu þér streng sem táknar land einhvers í fyrri töflunni. Segjum að þú sért með tré sem inniheldur "land" reitinn (dálkur 3) í töflunni:

Ef þú vilt vita hver vinnur í Bretlandi
þú horfir á tréð til að fá hnútinn sem táknar Stóra-Bretland
inni í "UKnode" finnurðu staðsetningu breskra starfsmannaskráa.

Þessi leit mun kosta log(N) aðgerðir í stað N aðgerðir ef þú notar fylkið beint. Það sem þú kynntir var gagnagrunnsvísitölu.

Þú getur byggt upp vísitölutré fyrir hvaða hóp reita sem er (strengur, tala, 2 línur, tala og strengur, dagsetning...) svo framarlega sem þú hefur aðgerð til að bera saman lykla (þ.e. reitahópa) svo þú getir stillt röð meðal lykla (sem á við um allar grunngerðir í gagnagrunninum).

B+Trjávísitala

Þó að þetta tré virki vel til að fá ákveðið gildi, þá er STÓRT vandamál þegar þú þarft fáðu marga þætti á milli tveggja gilda. Þetta mun kosta O(N) vegna þess að þú verður að skoða hvern hnút í trénu og athuga hvort hann sé á milli þessara tveggja gilda (t.d. með skipulögðu yfirferð trésins). Þar að auki er þessi aðgerð ekki I/O vingjarnlegur diskur þar sem þú þarft að lesa allt tréð. Við þurfum að finna leið til að framkvæma á skilvirkan hátt svið beiðni. Til að leysa þetta vandamál nota nútíma gagnagrunnar breytta útgáfu af fyrra tré sem kallast B+Tree. Í B+Tré tré:

aðeins neðstu hnúðarnir (blöðin) geyma upplýsingar (staðsetning lína í tengdri töflu)
restin af hnútunum eru hér fyrir leiðsögn í réttan hnút við leit.

Eins og þú sérð eru fleiri hnútar hér (tvisvar). Reyndar ertu með fleiri hnúta, "ákvörðunarhnúta", sem munu hjálpa þér að finna rétta hnútinn (sem geymir staðsetningu raðanna í tilheyrandi töflu). En flókið leit er samt O(log(N)) (það er bara eitt stig í viðbót). Stóri munurinn er sá hnútar á neðra stigi eru tengdir arftaka þeirra.

Með þessu B+tré, ef þú ert að leita að gildum á milli 40 og 100:

Þú þarft bara að leita að 40 (eða næsta gildi á eftir 40 ef 40 er ekki til) eins og þú gerðir með fyrra tré.
Safnaðu síðan 40 erfingjum með beinum erfingjatenglum þar til þú nærð 100.

Segjum að þú finnir M arftaka og tréð hafi N hnúta. Að finna ákveðinn hnút kostar log(N) eins og fyrra tréð. En þegar þú færð þennan hnút færðu M arftaka í M aðgerðum með tilvísunum í arftaka þeirra. Þessi leit kostar aðeins M+log(N) aðgerðir samanborið við N aðgerðir á fyrra tré. Þar að auki þarftu ekki að lesa allt tréð (aðeins M+log(N) hnútar), sem þýðir minni diskanotkun. Ef M er lítið (t.d. 200 raðir) og N er stórt (1 raðir) verður MIKILL munur.

En það eru ný vandamál hér (aftur!). Ef þú bætir við eða eyðir línu í gagnagrunninum (og þar af leiðandi í tilheyrandi B+Trjávísi):

þú verður að viðhalda röð á milli hnúta inni í B+tré, annars muntu ekki geta fundið hnúðana inni í óflokkuðu tré.
þú verður að halda lágmarksfjölda mögulegra stiga í B+Tré, annars verður O(log(N)) tímaflækjan O(N).

Með öðrum orðum, B+Tree verður að vera sjálfskipað og í jafnvægi. Sem betur fer er þetta mögulegt með snjallri eyðingu og innsetningu. En þetta kostar sitt: innsetningar og brottfellingar í B+ tré kosta O(log(N)). Þess vegna hafa sumir ykkar heyrt það að nota of margar vísitölur er ekki góð hugmynd. Í alvöru, þú ert að hægja á hraðri innsetningu/uppfærslu/eyðingu á röð í töfluvegna þess að gagnagrunnurinn þarf að uppfæra vísitölur töflunnar með því að nota dýra O(log(N)) aðgerð fyrir hverja vísitölu. Þar að auki þýðir það meira vinnuálag að bæta við vísitölum viðskiptastjóri (Verður lýst í lok greinarinnar).

Fyrir frekari upplýsingar er hægt að sjá Wikipedia grein um B+Tré. Ef þú vilt dæmi um að útfæra B+Tree í gagnagrunn skaltu skoða þessi grein и þessi grein frá leiðandi MySQL forritara. Þeir einbeita sér báðir að því hvernig InnoDB (MySQL vélin) meðhöndlar vísitölur.

Athugið: Lesandi sagði mér að vegna hagræðingar á lágu stigi ætti B+ tréð að vera í fullkomnu jafnvægi.

Hashtable

Síðasta mikilvæga gagnauppbyggingin okkar er kjötkássataflan. Þetta er mjög gagnlegt þegar þú vilt fljótt fletta upp gildum. Þar að auki mun skilningur á kjötkássatöflu hjálpa okkur síðar að skilja algenga gagnagrunnstengingaraðgerð sem kallast kjötkássatenging ( hass join). Þessi gagnauppbygging er einnig notuð af gagnagrunninum til að geyma innri hluti (t.d. læsa borð eða biðminni laug, við munum sjá bæði þessi hugtök síðar).

Kjötkássatafla er gagnauppbygging sem finnur fljótt frumefni eftir lyklinum sínum. Til að búa til kjötkássatöflu þarftu að skilgreina:

ключ fyrir þættina þína
kjötkássa virka fyrir lykla. Tölvulykilkássarnir gefa upp staðsetningu frumefna (kallað hluti ).
aðgerð til að bera saman lykla. Þegar þú hefur fundið rétta hlutann verður þú að finna þáttinn sem þú ert að leita að innan hlutans með því að nota þennan samanburð.

Einfalt dæmi

Tökum skýrt dæmi:

Þessi kjötkássatafla hefur 10 hluta. Vegna þess að ég er latur, tók ég bara 5 hluti á mynd, en ég veit að þú ert klár, svo ég leyfi þér að mynda hina 5 á eigin spýtur. Ég notaði kjötkássaaðgerð modulo 10 af lyklinum. Með öðrum orðum, ég geymi aðeins síðasta tölustafinn í lykli frumefnisins til að finna hluta þess:

ef síðasti stafurinn er 0 fellur frumefnið í 0 hluta,
ef síðasti stafurinn er 1 fellur frumefnið í 1 hluta,
ef síðasti stafurinn er 2 fellur frumefnið inn í svæði 2,
...

Samanburðarfallið sem ég notaði er einfaldlega jafnræði milli tveggja heiltalna.

Segjum að þú viljir fá þátt 78:

Hash-taflan reiknar út kjötkássakóðann fyrir 78, sem er 8.
Hash-taflan lítur á hluta 8 og fyrsti þátturinn sem hún finnur er 78.
Hún skilar hlut 78 til þín
Leit kostar aðeins 2 aðgerðir (annar til að reikna út kjötkássagildið og hitt til að fletta upp stakinu innan hlutans).

Segjum nú að þú viljir fá þátt 59:

Hash-taflan reiknar út kjötkássakóðann fyrir 59, sem er 9.
Hash taflan leitar í hluta 9, fyrsti þátturinn sem fannst er 99. Þar sem 99!=59 er þáttur 99 ekki gildur þáttur.
Með sömu rökfræði er annar þátturinn (9), sá þriðji (79), ..., sá síðasti (29) tekinn.
Eining fannst ekki.
Leitin kostaði 7 aðgerðir.

Góð kjötkássaaðgerð

Eins og þú sérð, fer eftir því hvaða verðmæti þú ert að leita að, kostnaðurinn er ekki sá sami!

Ef ég breyti nú kjötkássafallinu modulo 1 af lyklinum (þ.e. tek síðustu 000 tölustafina), þá kostar önnur uppfletting aðeins 000 aðgerð þar sem engir þættir eru í hluta 6. Raunverulega áskorunin er að finna góða kjötkássaaðgerð sem mun búa til fötu sem innihalda mjög fáan fjölda þátta.

Í mínu dæmi er auðvelt að finna góða kjötkássaaðgerð. En þetta er einfalt dæmi, að finna góða kjötkássaaðgerð er erfiðara þegar lykillinn er:

strengur (til dæmis - eftirnafn)
2 línur (til dæmis - eftirnafn og fornafn)
2 línur og dagsetning (til dæmis - eftirnafn, fornafn og fæðingardagur)
...

Með góðri kjötkássaaðgerð kosta uppflettingar á kjötkássatöflu O(1).

Fylki vs kjötkássa borð

Af hverju ekki að nota fylki?

Hmm, góð spurning.

Hash borðið getur verið hlaðinn að hluta til í minni, og hlutir sem eftir eru geta verið áfram á disknum.
Með fylki verður þú að nota samfellt rými í minni. Ef þú ert að hlaða stóru borði það er mjög erfitt að finna nóg samfellt pláss.
Fyrir kjötkássatöflu geturðu valið lykilinn sem þú vilt (til dæmis land og eftirnafn einstaklings).

Fyrir frekari upplýsingar er hægt að lesa greinina um JavaHashMap, sem er skilvirk útfærsla á kjötkássatöflu; þú þarft ekki að skilja Java til að skilja hugtökin sem fjallað er um í þessari grein.

Heimild: www.habr.com

Hvernig venslagagnagrunnar virka (1. hluti)