Hei Habr! Cyflwynaf i'ch sylw gyfieithiad yr erthygl
"Sut mae cronfa ddata berthynol yn gweithio".

O ran cronfeydd data perthynol, ni allaf helpu ond meddwl bod rhywbeth ar goll. Maent yn cael eu defnyddio ym mhobman. Mae yna lawer o wahanol gronfeydd data ar gael, o'r SQLite bach a defnyddiol i'r Teradata pwerus. Ond dim ond ychydig o erthyglau sy'n esbonio sut mae'r gronfa ddata yn gweithio. Gallwch chwilio drosoch eich hun gan ddefnyddio "howdoesarelationaldatabasework" i weld cyn lleied o ganlyniadau sydd. Ar ben hynny, mae'r erthyglau hyn yn fyr. Os ydych chi'n chwilio am y technolegau bywiog diweddaraf (BigData, NoSQL neu JavaScript), fe welwch erthyglau mwy manwl yn esbonio sut maen nhw'n gweithio.

A yw cronfeydd data perthynol yn rhy hen ac yn rhy ddiflas i'w hesbonio y tu allan i gyrsiau prifysgol, papurau ymchwil a llyfrau?

Fel datblygwr, mae'n gas gen i ddefnyddio rhywbeth nad wyf yn ei ddeall. Ac os defnyddiwyd cronfeydd data am fwy na 40 mlynedd, rhaid bod rheswm. Dros y blynyddoedd, rydw i wedi treulio cannoedd o oriau i wir ddeall y blychau du rhyfedd hyn rydw i'n eu defnyddio bob dydd. Cronfeydd data perthynol diddorol iawn oherwydd nhw seiliedig ar gysyniadau defnyddiol y gellir eu hailddefnyddio. Os oes gennych ddiddordeb mewn deall cronfa ddata, ond nad ydych erioed wedi cael yr amser na'r awydd i ymchwilio i'r pwnc eang hwn, dylech fwynhau'r erthygl hon.

Er bod teitl yr erthygl hon yn glir, nid pwrpas yr erthygl hon yw deall sut i ddefnyddio'r gronfa ddata. Felly, dylech chi eisoes wybod sut i ysgrifennu cais cysylltiad syml ac ymholiadau sylfaenol RAW; fel arall efallai na fyddwch yn deall yr erthygl hon. Dyna'r unig beth sydd angen i chi ei wybod, byddaf yn esbonio'r gweddill.

Dechreuaf gyda rhai pethau sylfaenol cyfrifiadureg, megis cymhlethdod amser algorithmau (BigO). Rwy'n gwybod bod rhai ohonoch yn casáu'r cysyniad hwn, ond hebddo ni fyddwch yn gallu deall y cymhlethdodau y tu mewn i'r gronfa ddata. Gan fod hwn yn bwnc enfawr, Byddaf yn canolbwyntio ar yr hyn sy'n bwysig yn fy marn i: sut mae'r gronfa ddata yn prosesu SQL ymchwiliad. 'N annhymerus' jyst yn cyflwyno cysyniadau cronfa ddata sylfaenolfel bod gennych chi syniad ar ddiwedd yr erthygl beth sy'n digwydd o dan y cwfl.

Gan fod hon yn erthygl hir a thechnegol sy'n cynnwys llawer o algorithmau a strwythurau data, cymerwch eich amser i ddarllen drwyddi. Gall fod yn anodd deall rhai cysyniadau; gallwch eu hepgor a dal i gael y syniad cyffredinol.

I'r rhai mwy gwybodus yn eich plith, mae'r erthygl hon wedi'i rhannu'n 3 rhan:

Trosolwg o gydrannau cronfa ddata lefel isel a lefel uchel
Trosolwg o'r Broses Optimeiddio Ymholiad
Trosolwg o Reoli Trafodion a Chronfeydd Byffer

Yn ôl i'r Hanfodion

Flynyddoedd yn ôl (mewn galaeth ymhell, bell i ffwrdd...), roedd yn rhaid i ddatblygwyr wybod yn union nifer y llawdriniaethau yr oeddent yn eu codio. Roeddent yn gwybod eu halgorithmau a strwythurau data ar y cof oherwydd ni allent fforddio gwastraffu'r CPU a chof eu cyfrifiaduron araf.

Yn y rhan hon, byddaf yn eich atgoffa o rai o'r cysyniadau hyn gan eu bod yn hanfodol i ddeall y gronfa ddata. Byddaf hefyd yn cyflwyno’r cysyniad mynegai cronfa ddata.

O(1) yn erbyn O(n2)

Y dyddiau hyn, nid yw llawer o ddatblygwyr yn poeni am gymhlethdod amser algorithmau ... ac maen nhw'n iawn!

Ond pan fyddwch chi'n delio â llawer o ddata (nid wyf yn siarad miloedd) neu os ydych chi'n cael trafferth mewn milieiliadau, mae'n dod yn hanfodol deall y cysyniad hwn. Ac fel y gallwch ddychmygu, mae'n rhaid i gronfeydd data ddelio â'r ddwy sefyllfa! Ni wnaf i chi dreulio mwy o amser nag sydd ei angen i gyfleu'r pwynt. Bydd hyn yn ein helpu i ddeall y cysyniad o optimeiddio ar sail cost yn ddiweddarach (costio yn seiliedig optimeiddio).

Cysyniad

Cymhlethdod amser yr algorithm defnyddio i weld faint o amser y bydd yn ei gymryd i weithredu algorithm ar gyfer swm penodol o ddata. I ddisgrifio'r cymhlethdod hwn, rydym yn defnyddio nodiant mathemategol mawr O. Defnyddir y nodiant hwn gyda ffwythiant sy'n disgrifio faint o weithrediadau sydd eu hangen ar algorithm ar gyfer nifer penodol o fewnbynnau.

Er enghraifft, pan ddywedaf "mae gan yr algorithm hwn gymhlethdod O (some_function ())", mae'n golygu bod angen rhai gweithrediadau_function (a_certain_amount_of_data) ar yr algorithm i brosesu rhywfaint o ddata.

Yn yr achos hwn, Nid faint o ddata sy'n bwysig**, fel arall ** sut mae nifer y llawdriniaethau yn cynyddu gyda chyfaint data cynyddol. Nid yw cymhlethdod amser yn darparu union nifer o weithrediadau, ond mae'n ffordd dda o amcangyfrif amser gweithredu.

Yn y graff hwn gallwch weld nifer y gweithrediadau yn erbyn swm y data mewnbwn ar gyfer gwahanol fathau o gymhlethdodau amser algorithm. Defnyddiais raddfa logarithmig i'w harddangos. Mewn geiriau eraill, mae swm y data yn cynyddu'n gyflym o 1 i 1 biliwn. Gallwn weld:

Mae O(1) neu gymhlethdod cyson yn aros yn gyson (fel arall ni fyddai'n cael ei alw'n gymhlethdod cyson).
O(mewngofnodi(n)) yn parhau i fod yn isel hyd yn oed gyda biliynau o ddata.
Anhawster gwaethaf - O(n2), lle mae nifer y llawdriniaethau'n cynyddu'n gyflym.
Mae'r ddau gymhlethdod arall yn cynyddu yr un mor gyflym.

Примеры

Gyda swm bach o ddata, mae'r gwahaniaeth rhwng O(1) ac O(n2) yn ddibwys. Er enghraifft, gadewch i ni ddweud bod gennych algorithm sydd angen prosesu 2000 o elfennau.

Bydd yr algorithm O(1) yn costio 1 gweithrediad i chi
Bydd yr algorithm O(log(n)) yn costio 7 gweithrediad i chi
Bydd yr algorithm O(n) yn costio 2 o weithrediadau i chi
Bydd yr algorithm O(n*log(n)) yn costio 14 o weithrediadau i chi
Bydd yr algorithm O(n2) yn costio 4 o weithrediadau i chi

Mae'r gwahaniaeth rhwng O(1) ac O(n2) yn ymddangos yn fawr (4 miliwn o lawdriniaethau) ond byddwch yn colli uchafswm o 2 ms, dim ond amser i blincio'ch llygaid. Yn wir, gall proseswyr modern brosesu cannoedd o filiynau o lawdriniaethau yr eiliad. Dyma pam nad yw perfformiad ac optimeiddio yn broblem mewn llawer o brosiectau TG.

Fel y dywedais, mae'n dal yn bwysig gwybod y cysyniad hwn wrth weithio gyda symiau enfawr o ddata. Os y tro hwn mae'n rhaid i'r algorithm brosesu 1 o elfennau (nad yw cymaint â hynny ar gyfer cronfa ddata):

Bydd yr algorithm O(1) yn costio 1 gweithrediad i chi
Bydd yr algorithm O(log(n)) yn costio 14 gweithrediad i chi
Bydd yr algorithm O(n) yn costio 1 o weithrediadau i chi
Bydd yr algorithm O(n*log(n)) yn costio 14 o weithrediadau i chi
Bydd yr algorithm O(n2) yn costio 1 o weithrediadau i chi

Dydw i ddim wedi gwneud y mathemateg, ond byddwn i'n dweud bod gennych chi amser gyda'r algorithm O(n2) i yfed coffi (hyd yn oed dau!). Os ychwanegwch 0 arall at gyfaint y data, bydd gennych amser i gymryd nap.

Gadewch i ni fynd yn ddyfnach

Er gwybodaeth:

Mae chwiliad tabl stwnsh da yn dod o hyd i elfen yn O(1).
Mae chwilio coeden gytbwys yn cynhyrchu canlyniadau yn O(log(n)).
Mae chwilio arae yn cynhyrchu canlyniadau yn O(n).
Mae gan yr algorithmau didoli gorau gymhlethdod O(n*log(n)).
Mae gan algorithm didoli gwael gymhlethdod O(n2).

Nodyn: Yn y rhannau canlynol byddwn yn gweld yr algorithmau a'r strwythurau data hyn.

Mae sawl math o gymhlethdod amser algorithm:

senario achos cyfartalog
senario achos gorau
a'r senario waethaf

Cymhlethdod amser yn aml yw'r sefyllfa waethaf.

Dim ond am gymhlethdod amser yr algorithm yr oeddwn yn siarad, ond mae cymhlethdod hefyd yn berthnasol i:

defnydd cof o'r algorithm
algorithm defnydd disg I/O

Wrth gwrs, mae cymhlethdodau yn waeth na n2, er enghraifft:

n4: mae hyn yn ofnadwy! Mae gan rai o'r algorithmau a grybwyllwyd y cymhlethdod hwn.
3n: mae hyn yn waeth byth! Mae gan un o'r algorithmau a welwn yng nghanol yr erthygl hon y cymhlethdod hwn (ac fe'i defnyddir mewn llawer o gronfeydd data mewn gwirionedd).
ffactoraidd n: ni fyddwch byth yn cael eich canlyniadau hyd yn oed gydag ychydig bach o ddata.
nn: Os byddwch yn dod ar draws y cymhlethdod hwn, dylech ofyn i chi'ch hun ai hwn yw eich maes gweithgaredd mewn gwirionedd...

Nodyn: Wnes i ddim rhoi'r diffiniad gwirioneddol o'r dynodiad O mawr i chi, dim ond syniad. Gallwch ddarllen yr erthygl hon yn Wikipedia am y diffiniad go iawn (asymptotig).

MergeSort

Beth ydych chi'n ei wneud pan fydd angen i chi drefnu casgliad? Beth? Rydych chi'n galw'r swyddogaeth sort () ... Iawn, ateb da... Ond ar gyfer cronfa ddata, mae'n rhaid i chi ddeall sut mae'r swyddogaeth math () hon yn gweithio.

Mae yna sawl algorithm didoli da, felly byddaf yn canolbwyntio ar y pwysicaf: fath uno. Efallai nad ydych chi'n deall pam mae didoli data yn ddefnyddiol ar hyn o bryd, ond dylech chi ar ôl y rhan optimeiddio ymholiad. Ar ben hynny, bydd deall trefn uno yn ein helpu yn ddiweddarach i ddeall y gweithrediad ymuno cronfa ddata cyffredin o'r enw uno ymuno (cymdeithas uno).

Uno

Fel llawer o algorithmau defnyddiol, mae didoli cyfuniad yn dibynnu ar gamp: mae cyfuno 2 arae wedi'u didoli o faint N/2 yn arae wedi'i didoli â N/XNUMX yn costio gweithrediadau N yn unig. Gelwir y llawdriniaeth hon yn uno.

Gadewch i ni weld beth mae hyn yn ei olygu gydag enghraifft syml:

Mae'r ffigur hwn yn dangos, er mwyn adeiladu'r arae 8 elfen derfynol wedi'i didoli, mai dim ond unwaith y bydd angen i chi ailadrodd dros y 2 arae o 4 elfen. Gan fod y ddau arae 4-elfen eisoes wedi'u didoli:

1) rydych chi'n cymharu'r ddwy elfen gyfredol mewn dwy arae (ar y dechrau cerrynt = cyntaf)
2) yna cymerwch yr un lleiaf i'w roi mewn arae 8 elfen
3) a symudwch i'r elfen nesaf yn yr arae lle cymeroch yr elfen leiaf
ac ailadroddwch 1,2,3 nes i chi gyrraedd elfen olaf un o'r araeau.
Yna byddwch yn cymryd yr elfennau sy'n weddill o'r arae arall i'w rhoi mewn arae 8 elfen.

Mae hyn yn gweithio oherwydd bod y ddau araeau 4-elfen yn cael eu didoli ac felly nid oes rhaid i chi "fynd yn ôl" yn yr araeau hynny.

Nawr ein bod ni'n deall y tric, dyma fy ffuggod ar gyfer uno:

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;

Mae didoli Cyfuno yn torri problem yn broblemau llai ac yna'n dod o hyd i ganlyniadau'r problemau llai i gael canlyniad y broblem wreiddiol (noder: gelwir y math hwn o algorithm yn rhannu a gorchfygu). Os nad ydych chi'n deall yr algorithm hwn, peidiwch â phoeni; Doeddwn i ddim yn ei ddeall y tro cyntaf i mi ei weld. Os gall eich helpu, rwy'n gweld yr algorithm hwn fel algorithm dau gam:

Cyfnod rhannu, lle mae'r arae wedi'i rannu'n araeau llai
Y cam didoli yw pan fydd araeau bach yn cael eu cyfuno (gan ddefnyddio undeb) i ffurfio arae fwy.

Cyfnod adran

Yn y cam rhannu, rhennir yr arae yn araeau unedol mewn 3 cham. Y nifer ffurfiol o gamau yw log(N) (ers N=8, log(N) = 3).

Sut ydw i'n gwybod hyn?

Rwy'n athrylith! Mewn gair - mathemateg. Y syniad yw bod pob cam yn rhannu maint yr arae wreiddiol â 2. Y nifer o gamau yw'r nifer o weithiau y gallwch chi rannu'r arae wreiddiol yn ddau. Dyma'r union ddiffiniad o logarithm (sylfaen 2).

Cyfnod didoli

Yn y cyfnod didoli, rydych chi'n dechrau gydag araeau unedol (elfen sengl). Yn ystod pob cam byddwch yn cymhwyso gweithrediadau uno lluosog a chyfanswm y gost yw N = 8 gweithrediad:

Yn y cam cyntaf mae gennych 4 cyfuniad sy'n costio 2 weithred yr un
Yn yr ail gam mae gennych 2 gyfuniad sy'n costio 4 gweithrediad yr un
Yn y trydydd cam mae gennych 1 uno sy'n costio 8 gweithrediad

Gan fod yna gamau log(N), cyfanswm cost N * gweithrediadau log(N)..

Manteision math uno

Pam mae'r algorithm hwn mor bwerus?

Oherwydd:

Gallwch ei newid i leihau'r ôl troed cof fel nad ydych yn creu araeau newydd ond yn addasu'r arae mewnbwn yn uniongyrchol.

Sylwch: gelwir y math hwn o algorithm in-le (didoli heb gof ychwanegol).

Gallwch ei newid i ddefnyddio gofod disg ac ychydig bach o gof ar yr un pryd heb achosi disg I/O sylweddol uwchben. Y syniad yw llwytho i'r cof dim ond y rhannau hynny sy'n cael eu prosesu ar hyn o bryd. Mae hyn yn bwysig pan fydd angen i chi ddidoli bwrdd aml-gigabeit gyda byffer cof 100-megabyte yn unig.

Sylwch: gelwir y math hwn o algorithm didoli allanol.

Gallwch ei newid i redeg ar brosesau / edafedd / gweinyddwyr lluosog.

Er enghraifft, didoli cyfuniad dosranedig yw un o'r cydrannau allweddol Hadoop (sy'n strwythur mewn data mawr).

Gall yr algorithm hwn droi plwm yn aur (mewn gwirionedd!).

Defnyddir yr algorithm didoli hwn yn y rhan fwyaf o gronfeydd data (os nad y cyfan), ond nid dyma'r unig un. Os ydych chi eisiau gwybod mwy, gallwch chi ddarllen hwn gwaith ymchwil, sy'n trafod manteision ac anfanteision algorithmau didoli cronfa ddata cyffredin.

Arae, Coed a Bwrdd Hash

Nawr ein bod yn deall y syniad o gymhlethdod amser a didoli, dylwn ddweud wrthych am 3 strwythur data. Mae hyn yn bwysig oherwydd nhw yn sail i gronfeydd data modern. Byddaf hefyd yn cyflwyno’r cysyniad mynegai cronfa ddata.

Array

Arae dau ddimensiwn yw'r strwythur data symlaf. Gellir meddwl am fwrdd fel arae. Er enghraifft:

Mae'r arae 2 ddimensiwn hwn yn dabl gyda rhesi a cholofnau:

Mae pob llinell yn cynrychioli endid
Mae colofnau'n storio priodweddau sy'n disgrifio'r endid.
Mae pob colofn yn storio data o fath penodol (cyfanrif, llinyn, dyddiad...).

Mae hyn yn gyfleus ar gyfer storio a delweddu data, fodd bynnag, pan fydd angen i chi ddod o hyd i werth penodol, nid yw hyn yn addas.

Er enghraifft, pe baech am ddod o hyd i'r holl ddynion sy'n gweithio yn y DU, byddai angen ichi edrych ar bob rhes i benderfynu a yw'r rhes honno'n perthyn i'r DU. Bydd yn costio N trafodion i chille N - nifer y llinellau, nad yw'n ddrwg, ond a allai fod ffordd gyflymach? Nawr mae'n bryd i ni ddod yn gyfarwydd â'r coed.

Nodyn: Mae'r rhan fwyaf o gronfeydd data modern yn darparu araeau estynedig ar gyfer storio tablau'n effeithlon: tablau trefniadol pentwr a thablau trefniadol mynegai. Ond nid yw hyn yn newid y broblem o ddod o hyd i gyflwr penodol yn gyflym mewn grŵp o golofnau.

Coeden cronfa ddata a mynegai

Mae coeden chwilio ddeuaidd yn goeden ddeuaidd gydag eiddo arbennig, rhaid i'r allwedd wrth bob nod fod:

yn fwy na'r holl allweddi sydd wedi'u storio yn yr is-goeden chwith
llai na'r holl allweddi sydd wedi'u storio yn yr is-goeden gywir

Gadewch i ni weld beth mae hyn yn ei olygu yn weledol

Syniad

Mae gan y goeden hon N = 15 elfen. Gadewch i ni ddweud fy mod yn edrych am 208:

Dechreuaf ar y gwraidd y mae ei allwedd yn 136. Ers 136<208, rwy'n edrych ar yr is-goeden dde o nod 136.
398>208 felly rwy'n edrych ar is-goeden chwith nod 398
250>208 felly rwy'n edrych ar is-goeden chwith nod 250
200<208, felly yr wyf yn edrych ar is-bren cywir nod 200. Ond nid oes gan 200 is-bren cywir, nid yw gwerth yn bodoli (oherwydd os yw'n bodoli, bydd yn yr is-goeden gywir 200).

Nawr gadewch i ni ddweud fy mod i'n edrych am 40

Dechreuaf ar y gwraidd y mae ei allwedd yn 136. Ers 136 > 40, rwy'n edrych ar is-goeden chwith nod 136.
80 > 40, felly rwy'n edrych ar is-goeden chwith nod 80
40= 40, nod yn bodoli. Rwy'n adfer yr ID rhes y tu mewn i'r nod (na ddangosir yn y llun) ac yn edrych yn y tabl am yr ID rhes a roddir.
Mae gwybod yr ID rhes yn fy ngalluogi i wybod yn union ble mae'r data yn y tabl, felly gallaf ei adfer ar unwaith.

Yn y diwedd, bydd y ddau chwiliad yn costio nifer y lefelau y tu mewn i'r goeden i mi. Os darllenwch y rhan am ddidoli uno yn ofalus, dylech weld bod yna lefelau log(N). Mae'n troi allan, log cost chwilio(N), ddim yn ddrwg!

Gadewch i ni ddychwelyd at ein problem

Ond mae hyn yn haniaethol iawn, felly gadewch i ni fynd yn ôl at ein problem. Yn lle cyfanrif syml, dychmygwch linyn sy'n cynrychioli gwlad rhywun yn y tabl blaenorol. Dywedwch fod gennych chi goeden sy'n cynnwys y maes "gwlad" (colofn 3) o'r tabl:

Os ydych chi eisiau gwybod pwy sy'n gweithio yn y DU
rydych chi'n edrych ar y goeden i gael y nod sy'n cynrychioli Prydain Fawr
y tu mewn i "UKnode" fe welwch leoliad cofnodion gweithwyr y DU.

Bydd y chwiliad hwn yn costio gweithrediadau log(N) yn lle gweithrediadau N os byddwch yn defnyddio'r arae yn uniongyrchol. Yr hyn yr ydych newydd ei gyflwyno oedd mynegai cronfa ddata.

Gallwch adeiladu coeden fynegai ar gyfer unrhyw grŵp o feysydd (llinyn, rhif, 2 linell, rhif a llinyn, dyddiad...) cyn belled â bod gennych swyddogaeth i gymharu bysellau (hy grwpiau maes) fel y gallwch osod trefn ymhlith yr allweddi (sy'n wir am unrhyw fathau sylfaenol yn y gronfa ddata).

Mynegai Coed B+

Er bod y goeden hon yn gweithio'n dda ar gyfer cael gwerth penodol, mae problem FAWR pan fo angen cael elfennau lluosog rhwng dau werth. Bydd hyn yn costio O(N) oherwydd bydd yn rhaid i chi edrych ar bob nod yn y goeden a gwirio a yw rhwng y ddau werth hyn (e.e. gyda llwybr trefniadol o'r goeden). Ar ben hynny, nid yw'r llawdriniaeth hon yn gyfeillgar i ddisg I/O gan fod yn rhaid i chi ddarllen y goeden gyfan. Mae angen inni ddod o hyd i ffordd o weithredu'n effeithlon cais ystod. I ddatrys y broblem hon, mae cronfeydd data modern yn defnyddio fersiwn wedi'i haddasu o'r goeden flaenorol o'r enw B+Tree. Mewn coeden B+:

dim ond y nodau isaf (dail) storio gwybodaeth (lleoliad rhesi yn y tabl cysylltiedig)
mae gweddill y nodau yma ar gyfer llwybro i'r nod cywir yn ystod chwilio.

Fel y gwelwch, mae mwy o nodau yma (ddwywaith). Yn wir, mae gennych nodau ychwanegol, "nodau penderfynu", a fydd yn eich helpu i ddod o hyd i'r nod cywir (sy'n storio lleoliad y rhesi yn y tabl cysylltiedig). Ond cymhlethdod chwilio yw O(log(N)) o hyd (dim ond un lefel arall sydd). Y gwahaniaeth mawr yw hynny mae nodau ar y lefel is yn gysylltiedig â'u holynwyr.

Gyda'r Goeden B+ hon, os ydych chi'n chwilio am werthoedd rhwng 40 a 100:

Mae angen i chi chwilio am 40 (neu'r gwerth agosaf ar ôl 40 os nad yw 40 yn bodoli) fel y gwnaethoch gyda'r goeden flaenorol.
Yna casglwch 40 o etifeddion gan ddefnyddio cysylltiadau etifeddol uniongyrchol nes i chi gyrraedd 100.

Dywedwch eich bod chi'n dod o hyd i olynwyr M ac mae gan y goeden nodau N. Mae dod o hyd i nod penodol yn costio log(N) fel y goeden flaenorol. Ond unwaith y byddwch yn cael y nod hwn, byddwch yn cael olynwyr M mewn gweithrediadau M gyda chyfeiriadau at eu holynwyr. Mae'r chwiliad hwn yn costio M+log(N) yn unig gweithrediadau o gymharu â gweithrediadau N ar y goeden flaenorol. Ar ben hynny, nid oes rhaid i chi ddarllen y goeden lawn (dim ond nodau M + log (N)), sy'n golygu llai o ddefnydd disg. Os yw M yn fach (ee 200 rhes) ac N yn fawr (1 o resi), bydd gwahaniaeth MAWR.

Ond mae problemau newydd yma (eto!). Os ydych chi'n ychwanegu neu'n dileu rhes yn y gronfa ddata (ac felly yn y mynegai B+Coed cysylltiedig):

rhaid i chi gadw trefn rhwng y nodau y tu mewn i Goeden B+, fel arall ni fyddwch yn gallu dod o hyd i'r nodau y tu mewn i goeden heb ei didoli.
rhaid i chi gadw'r nifer lleiaf posibl o lefelau yn B+Coed, fel arall bydd cymhlethdod amser O(log(N)) yn dod yn O(N).

Mewn geiriau eraill, mae'n rhaid i B+Coeden fod yn hunan-drefnol a chytbwys. Yn ffodus, mae hyn yn bosibl gyda gweithrediadau dileu a mewnosod craff. Ond mae cost i hyn: cost gosod a dileu coeden B+ O(log(N)). Dyna pam mae rhai ohonoch wedi clywed hynny nid yw defnyddio gormod o fynegeion yn syniad da. Mewn gwirionedd, rydych yn arafu mewnosod/diweddaru/dileu rhes mewn tabl yn gyflymoherwydd bod angen i'r gronfa ddata ddiweddaru mynegeion y tabl gan ddefnyddio gweithrediad O(log(N)) drud ar gyfer pob mynegai. Ar ben hynny, mae ychwanegu mynegeion yn golygu mwy o lwyth gwaith ar gyfer rheolwr trafodion (bydd yn cael ei ddisgrifio ar ddiwedd yr erthygl).

Am fwy o fanylion, gallwch weld yr erthygl Wicipedia ar B+Coed. Os ydych chi eisiau enghraifft o weithredu B+Tree mewn cronfa ddata, edrychwch yr erthygl hon и yr erthygl hon gan ddatblygwr MySQL blaenllaw. Mae'r ddau yn canolbwyntio ar sut mae InnoDB (peiriant MySQL) yn trin mynegeion.

Nodyn: Dywedodd darllenydd wrthyf, oherwydd optimeiddio lefel isel, y dylai'r goeden B+ fod yn gwbl gytbwys.

Hashtable

Ein strwythur data pwysig olaf yw'r tabl hash. Mae hyn yn ddefnyddiol iawn pan fyddwch chi eisiau chwilio am werthoedd yn gyflym. Ar ben hynny, bydd deall tabl hash yn ein helpu yn ddiweddarach i ddeall gweithrediad ymuno cronfa ddata cyffredin o'r enw hash join ( hash ymuno). Mae’r strwythur data hwn hefyd yn cael ei ddefnyddio gan y gronfa ddata i storio rhai pethau mewnol (e.e. bwrdd clo neu pwll byffer, byddwn yn gweld y ddau gysyniad hyn yn ddiweddarach).

Mae tabl stwnsh yn strwythur data sy'n dod o hyd i elfen yn gyflym wrth ei chywair. I adeiladu tabl hash mae angen i chi ddiffinio:

ключ ar gyfer eich elfennau
swyddogaeth hash am allweddi. Mae'r hashes allwedd a gyfrifwyd yn rhoi lleoliad yr elfennau (o'r enw segmentau ).
swyddogaeth ar gyfer cymharu allweddi. Unwaith y byddwch wedi dod o hyd i'r segment cywir, rhaid i chi ddod o hyd i'r elfen yr ydych yn chwilio amdani o fewn y segment gan ddefnyddio'r gymhariaeth hon.

Enghraifft syml

Gadewch i ni gymryd enghraifft glir:

Mae gan y tabl hash hwn 10 segment. Oherwydd fy mod i'n ddiog, dim ond 5 segment wnes i eu llun, ond dwi'n gwybod eich bod chi'n graff, felly byddaf yn gadael i chi ddarlunio'r 5 arall ar eich pen eich hun. Defnyddiais fodwlo ffwythiant hash 10 o'r allwedd. Mewn geiriau eraill, dim ond digid olaf allwedd yr elfen rwy'n ei storio i ddod o hyd i'w segment:

os yw'r digid olaf yn 0, mae'r elfen yn disgyn i segment 0,
os yw'r digid olaf yn 1, mae'r elfen yn disgyn i segment 1,
os yw'r digid olaf yn 2, mae'r elfen yn disgyn i arwynebedd 2,
...

Y swyddogaeth gymharu a ddefnyddiais yn syml yw cydraddoldeb rhwng dau gyfanrif.

Gadewch i ni ddweud eich bod am gael elfen 78:

Mae'r tabl hash yn cyfrifo'r cod hash ar gyfer 78, sef 8.
Mae'r tabl hash yn edrych ar segment 8, a'r elfen gyntaf y mae'n ei darganfod yw 78.
Mae hi'n dychwelyd eitem 78 i chi
Mae chwilio yn costio 2 weithred yn unig (un i gyfrifo'r gwerth hash a'r llall i chwilio am yr elfen o fewn y segment).

Nawr gadewch i ni ddweud eich bod am gael elfen 59:

Mae'r tabl hash yn cyfrifo'r cod hash ar gyfer 59, sef 9.
Mae'r tabl stwnsh yn chwilio yn segment 9, yr elfen gyntaf a ddarganfuwyd yw 99. Ers 99!=59, nid yw elfen 99 yn elfen ddilys.
Gan ddefnyddio'r un rhesymeg, cymerir yr ail elfen (9), y drydedd (79), ..., yr olaf (29).
Elfen heb ei chanfod.
Costiodd y chwiliad 7 gweithrediad.

Swyddogaeth hash da

Fel y gallwch weld, yn dibynnu ar y gwerth yr ydych yn chwilio amdano, nid yw'r gost yr un peth!

Os byddaf nawr yn newid y ffwythiant hash modwlo 1 o'r allwedd (hynny yw, gan gymryd y 000 digid olaf), dim ond 000 gweithrediad y mae'r ail chwiliad yn ei gostio gan nad oes unrhyw elfennau yn segment 6. Yr her wirioneddol yw dod o hyd i swyddogaeth hash dda a fydd yn creu bwcedi sy'n cynnwys nifer fach iawn o elfennau.

Yn fy enghraifft, mae dod o hyd i swyddogaeth hash dda yn hawdd. Ond mae hon yn enghraifft syml, mae dod o hyd i swyddogaeth hash dda yn anoddach pan mai'r allwedd yw:

llinyn (er enghraifft - enw olaf)
2 linell (er enghraifft - enw olaf ac enw cyntaf)
2 linell a dyddiad (er enghraifft - cyfenw, enw cyntaf a dyddiad geni)
...

Gyda swyddogaeth stwnsh dda, mae chwilio tabl stwnsh yn costio O(1).

Array vs bwrdd hash

Beth am ddefnyddio arae?

Hmm, cwestiwn da.

Gall y bwrdd hash fod wedi'i lwytho'n rhannol i'r cof, a gall y segmentau sy'n weddill aros ar y ddisg.
Gydag arae rhaid i chi ddefnyddio gofod cyffiniol yn y cof. Os ydych chi'n llwytho bwrdd mawr mae'n anodd iawn dod o hyd i ddigon o le di-dor.
Ar gyfer tabl hash, gallwch ddewis yr allwedd rydych chi ei eisiau (er enghraifft, enw olaf gwlad a pherson).

Am ragor o wybodaeth, gallwch ddarllen yr erthygl am JavaHashMap, sy'n weithrediad effeithlon o dabl hash; nid oes angen i chi ddeall Java i ddeall y cysyniadau a gwmpesir yn yr erthygl hon.

Ffynhonnell: hab.com

Sut mae Cronfeydd Data Perthynol yn Gweithio (Rhan 1)