Hey Habr! Cuirim i láthair d'aistriúchán ar an alt
"Conas a oibríonn bunachar sonraí coibhneasta".

Nuair a bhaineann sé le bunachair shonraí choibhneasta ní féidir liom cabhrú ach ceapaim go bhfuil rud éigin in easnamh. Úsáidtear iad i ngach áit. Tá go leor bunachair shonraí éagsúla ar fáil, ón SQLite beag agus úsáideach go dtí an Teradata cumhachtach. Ach níl ach cúpla alt a mhíníonn conas a oibríonn an bunachar sonraí. Is féidir leat cuardach a dhéanamh duit féin trí úsáid a bhaint as "howdoesarelationaldatabasework" chun a fháil amach cé chomh beag torthaí atá ann. Thairis sin, tá na hailt seo gearr. Má tá na teicneolaíochtaí buacach is déanaí á lorg agat (BigData, NoSQL nó JavaScript), gheobhaidh tú ailt níos doimhne a mhíníonn conas a oibríonn siad.

An bhfuil bunachair shonraí choibhneasta ró-shean agus ró-leadránach le míniú lasmuigh de chúrsaí ollscoile, páipéir thaighde agus leabhair?

Mar fhorbróir, is fuath liom rud éigin a úsáid nach dtuigim. Agus má úsáideadh bunachair shonraí ar feadh níos mó ná 40 bliain, ní mór go mbeadh cúis ann. Thar na blianta, chaith mé na céadta uair an chloig chun na boscaí dubha aisteach seo a úsáidim gach lá a thuiscint go fírinneach. bunachair shonraí ghaolmhara an-suimiúil mar gheall ar siad bunaithe ar choincheapa úsáideacha agus ath-inúsáidte. Más spéis leat bunachar sonraí a thuiscint, ach nach raibh an t-am nó an claonadh agat riamh dul i ngleic leis an ábhar leathan seo, ba cheart duit taitneamh a bhaint as an alt seo.

Cé go bhfuil teideal an ailt seo follasach, ní hé cuspóir an ailt seo a thuiscint conas an bunachar sonraí a úsáid. Dá bharr sin, ba cheart go mbeadh a fhios agat cheana féin conas iarratas nasc simplí agus ceisteanna bunúsacha a scríobh RAW; murach sin b'fhéidir nach dtuigeann tú an t-alt seo. Sin an t-aon rud a theastaíonn uait a bheith ar eolas agat, míneoidh mé an chuid eile.

Tosóidh mé le roinnt bunúsacha eolaíocht ríomhaireachta, mar shampla castacht ama na n-algartam (BigO). Tá a fhios agam gur fuath le cuid agaibh an coincheap seo, ach gan é ní bheidh tú in ann na castaí sa bhunachar sonraí a thuiscint. Ós rud é gur ábhar ollmhór é seo, Díreoidh mé ar an rud is dóigh liom atá tábhachtach: conas a phróiseálann an bunachar sonraí SQL fiosrúchán. Tabharfaidh mé isteach díreach coincheapa bunúsacha bunachar sonraíionas go mbeidh tuairim agat ag deireadh an ailt cad atá ar siúl faoin gcochall.

Ós rud é gur alt fada teicniúil é seo a bhfuil a lán algartaim agus struchtúr sonraí i gceist leis, tóg do chuid ama chun é a léamh. D’fhéadfadh go mbeadh sé deacair coincheapa áirithe a thuiscint; is féidir leat iad a scipeáil agus an smaoineamh ginearálta a fháil fós.

Dóibh siúd is eolach in bhur measc, tá an t-alt seo roinnte ina 3 chuid:

Forbhreathnú ar chomhpháirteanna bunachar sonraí ísealleibhéil agus ardleibhéil
Forbhreathnú ar Phróiseas Optamaithe na gCeisteanna
Forbhreathnú ar Idirbheart agus Bainistíocht Linn Maoláin

Ar ais go Basics

Blianta ó shin (i réaltra i bhfad, i bhfad ar shiúl...), bhí ar fhorbróirí fios a bheith acu go beacht ar líon na n-oibríochtaí a bhí á gcódú acu. Bhí a n-halgartaim agus struchtúir sonraí ar eolas acu ó chroí mar ní raibh sé d'acmhainn acu an CPU agus cuimhne a gcuid ríomhairí mall a chur amú.

Sa chuid seo, meabhróidh mé roinnt de na coincheapa seo duit mar go bhfuil siad riachtanach chun an bunachar sonraí a thuiscint. Tabharfaidh mé isteach an coincheap freisin innéacs bunachar sonraí.

O(1) vs O(n2)

Sa lá atá inniu ann, is cuma le go leor forbróirí faoi chastacht ama na n-algartam ... agus tá an ceart acu!

Ach nuair a bhíonn tú ag déileáil le go leor sonraí (níl mé ag caint na mílte) nó má tá tú ag streachailt i milleasoicindí, bíonn sé ríthábhachtach an coincheap seo a thuiscint. Agus mar is féidir leat a shamhlú, caithfidh bunachair sonraí déileáil leis an dá chás! Ní chuirfidh mé iallach ort níos mó ama a chaitheamh ná mar is gá chun an pointe a chur in iúl. Cabhróidh sé seo linn coincheap an bharrfheabhsú costas-bhunaithe a thuiscint níos déanaí (costas bunaithe leas iomlán a bhaint).

Coincheap

Castacht ama an algartam a úsáidtear chun a fheiceáil cé chomh fada a thógfaidh sé chun algartam a rith le haghaidh méid áirithe sonraí. Chun cur síos a dhéanamh ar an gcastacht seo, úsáidimid nodaireacht mhatamaitice O. Úsáidtear an nodaireacht seo le feidhm a chuireann síos ar cé mhéad oibríocht a theastaíonn ó algartam le haghaidh líon áirithe ionchuir.

Mar shampla, nuair a deirim "tá castacht O(some_function()) ag an algartam seo", ciallaíonn sé go n-éilíonn an t-algartam roinnt oibríochtaí_function(a_certain_amount_of_data) chun méid áirithe sonraí a phróiseáil.

Sa chás seo, Ní hé an méid sonraí atá tábhachtach**, a mhalairt ** mar a mhéadaíonn líon na n-oibríochtaí le méadú ar mhéid na sonraí. Ní sholáthraíonn castacht ama líon beacht oibríochtaí, ach is bealach maith é chun am cur i gcrích a mheas.

Sa ghraf seo is féidir leat líon na n-oibríochtaí a fheiceáil i gcomparáid leis an méid sonraí ionchuir do chineálacha éagsúla castachtaí ama algartam. Bhain mé úsáid as scála logartamach chun iad a thaispeáint. I bhfocail eile, méadaíonn an méid sonraí go tapa ó 1 go 1 billiún.Is féidir linn a fheiceáil:

Fanann O(1) nó castacht leanúnach tairiseach (ar shlí ní thabharfaí castacht tairiseach uirthi).
O(Logáil isteach(n)) fós íseal fiú le na billiúin sonraí.
deacracht is measa - O(n2), áit a dtagann méadú tapa ar líon na n-oibríochtaí.
Méadaíonn an dá seachghalair eile chomh tapa céanna.

Примеры

Le méid beag sonraí, tá an difríocht idir O(1) agus O(n2) diomaibhseach. Mar shampla, déanaimis a rá go bhfuil algartam agat a chaithfidh 2000 eilimint a phróiseáil.

Cosnóidh an t-algartam O(1) 1 oibríocht duit
Cosnóidh an t-algartam O(log(n)) 7 oibríocht duit
Cosnóidh an t-algartam O(n) 2 oibríocht ort
Cosnóidh an t-algartam O(n*log(n)) 14 oibríocht ort
Cosnóidh an algartam O(n2) 4 oibríocht ort

Is cosúil go bhfuil an difríocht idir O(1) agus O(n2) mór (4 mhilliún oibríocht) ach caillfidh tú 2 ms ar a mhéad, níl ach an t-am agat chun do shúile a fhalla. Go deimhin, is féidir le próiseálaithe nua-aimseartha a phróiseáil na céadta milliún oibríochtaí in aghaidh an tsoicind. Sin é an fáth nach bhfuil feidhmíocht agus uasmhéadú ina cheist i go leor tionscadal TF.

Mar a dúirt mé, tá sé fós tábhachtach go mbeadh an coincheap seo ar eolas agus tú ag obair le méideanna ollmhóra sonraí. Más rud é an uair seo caithfidh an algartam 1 eilimint a phróiseáil (nach bhfuil an oiread sin le haghaidh bunachar sonraí):

Cosnóidh an t-algartam O(1) 1 oibríocht duit
Cosnóidh an t-algartam O(log(n)) 14 oibríocht duit
Cosnóidh an algartam O(n) 1 oibríocht duit
Cosnóidh an t-algartam O(n*log(n)) 14 oibríocht duit
Cosnóidh an t-algartam O(n2) 1 oibríocht ort

Níl an mata déanta agam, ach déarfainn leis an algartam O(n2) go bhfuil am agat caife a ól (fiú dhá cheann!). Má chuireann tú 0 eile leis an méid sonraí, beidh am agat an staighre a ghlacadh.

A ligean ar dul níos doimhne

Chun do chuid faisnéise:

Aimsíonn cuardach tábla hais mhaith eilimint in O(1).
Nuair a chuardaítear crann dea-chothromaithe, faightear torthaí in O(log(n)).
Nuair a chuardaítear eagar, faightear torthaí in O(n).
Tá castacht O(n*log(n)) ag na halgartaim sórtála is fearr.
Tá castacht O(n2) ag droch-algartam sórtála.

Nóta: Sna codanna seo a leanas feicfimid na halgartaim agus na struchtúir sonraí seo.

Tá roinnt cineálacha castachta ama algartam ann:

meánchás cás
cás is fearr
agus an cás is measa

Is minic gurb é castacht ama an cás is measa.

Ní raibh mé ag caint ach faoi chastacht ama an algartam, ach baineann castacht freisin le:

tomhaltas cuimhne an algartam
algartam tomhaltais diosca I/O

Ar ndóigh, tá deacrachtaí níos measa ná n2, mar shampla:

n4: tá sé seo uafásach! Tá an chastacht seo ag cuid de na halgartaim a luaitear.
3n: tá sé seo níos measa fós! Tá an chastacht seo ag ceann de na halgartaim a fheicfimid i lár an ailt seo (agus úsáidtear é i go leor bunachair shonraí).
factorial n: ní bhfaighidh tú do thorthaí go deo fiú le méid beag sonraí.
nn: Má thagann tú trasna ar an gcastacht seo, ba cheart duit fiafraí díot féin an é seo do réimse gníomhaíochta i ndáiríre...

Nóta: Níor thug mé an sainmhíniú iarbhír duit ar an ainmniúchán mór O, ach smaoineamh. Is féidir leat an t-alt seo a léamh ag Vicipéid don sainmhíniú fíor (asimptotic).

CumascSort

Cad a dhéanann tú nuair is gá duit bailiúchán a shórtáil? Cad? Glaonn tú ar an fheidhm sort()... Ceart go leor, freagra maith... Ach maidir le bunachar sonraí, caithfidh tú a thuiscint conas a oibríonn an fheidhm sort() seo.

Tá roinnt mhaith halgartaim sórtála ann, mar sin díreoidh mé ar na cinn is tábhachtaí: sórtáil chumasc. B'fhéidir nach dtuigeann tú cén fáth go bhfuil sórtáil sonraí úsáideach faoi láthair, ach ba cheart duit tar éis an chuid leas iomlán a bhaint as ceist. Ina theannta sin, cabhróidh tuiscint a fháil ar shórtáil chumaisc linn níos déanaí an oibríocht cheangail bhunachar sonraí ar a dtugtar a thuiscint merge páirt a ghlacadh (cumann cumaisc).

Cumaisc

Cosúil le go leor halgartaim úsáideacha, bíonn sórtáil chumaisc ag brath ar chleas: ní chosnaíonn sé ach N oibríochtaí a chomhcheangal le 2 eagar sórtáilte ar mhéid N/2 in eagar sórtáilte eilimint N. Cumasc a thugtar ar an oibríocht seo.

Feicfimid cad a chiallaíonn sé seo le sampla simplí:

Léiríonn an figiúr seo nach gá duit ach aon uair amháin a athrá thar na 8 eagair de 2 eilimint chun an t-eagar críochnaitheach sórtáilte 4 eilimint a thógáil. Ós rud é go bhfuil an dá eagar ceithre eilimint sórtáilte cheana féin:

1) déanann tú an dá eilimint reatha a chur i gcomparáid in dhá eagar (ag an tús reatha = an chéad cheann)
2) ansin tóg an ceann is lú chun é a chur in eagar 8 eilimint
3) agus bog go dtí an chéad eilimint eile san eagar inar ghlac tú an eilimint is lú
agus déan 1,2,3 arís go dtí go sroicheann tú an eilimint dheireanach de cheann de na eagair.
Ansin glacann tú na heilimintí atá fágtha den eagar eile chun iad a chur in eagar 8 n-eilimintí.

Oibríonn sé seo toisc go bhfuil an dá eagair 4-eilimint sórtáilte agus mar sin ní gá duit "dul ar ais" sna eagair sin.

Anois go dtuigeann muid an cleas, seo é mo pseudocode le haghaidh cumasc:

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;

Briseann sórtáil Cumaisc fadhb ina fadhbanna níos lú agus ansin aimsíonn sé torthaí na bhfadhbanna níos lú chun toradh na faidhbe bunaidh a fháil (nóta: tugtar deighilt agus conquer ar an gcineál seo algartam). Mura dtuigeann tú an algartam seo, ná bí buartha; Níor thuig mé é an chéad uair a chonaic mé é. Más féidir leis cabhrú leat, feicim an algartam seo mar algartam dhá chéim:

Céim rannán, ina bhfuil an t-eagar roinnte ina eagair níos lú
Is é an chéim sórtála nuair a chuirtear eagair bheaga le chéile (ag baint úsáide as aontas) chun eagar níos mó a dhéanamh.

Céim rannán

Sa chéim roinnte, roinntear an t-eagar ina eagair aonadach i 3 chéim. Is é an líon foirmiúil céimeanna ná log(N) (ó N=8, log(N) = 3).

Conas a bheidh a fhios agam faoi seo?

Is genius mé! I bhfocal - matamaitic. Is é an smaoineamh go roinneann gach céim méid an eagar bunaidh faoi 2. Is é líon na gcéimeanna ná an líon uaireanta is féidir leat an t-eagar bunaidh a roinnt ina dhá cheann. Seo é an sainmhíniú beacht ar logartaim (bonn 2).

Céim sórtála

Sa chéim sórtála, tosaíonn tú le eagair aonadacha (aon eilimint). Le linn gach céime cuireann tú oibríochtaí cumaisc i bhfeidhm agus is é N = 8 oibríocht an costas iomlán:

Sa chéad chéim tá 4 chumasc agat a chosnaíonn 2 oibríocht an ceann
Sa dara céim tá 2 chumasc agat a chosnaíonn 4 oibríocht an ceann
Sa tríú céim tá cumasc amháin agat a chosnaíonn 1 oibríocht

Ós rud é go bhfuil céimeanna log(N), costas iomlán N * oibríochtaí log(N)..

Buntáistí a bhaineann le cumasc a shórtáil

Cén fáth a bhfuil an algartam seo chomh cumhachtach?

Mar:

Is féidir leat é a athrú chun an lorg cuimhne a laghdú ionas nach gcruthóidh tú eagair nua ach go modhnóidh tú an t-eagar ionchuir go díreach.

Tabhair faoi deara: tugtar algartam den chineál seo in-áit (sórtáil gan cuimhne breise).

Is féidir leat é a athrú chun spás diosca agus méid beag cuimhne a úsáid ag an am céanna gan diosca I/O suntasach a thabhú. Is é an smaoineamh ná na codanna sin atá á bpróiseáil faoi láthair a luchtú isteach sa chuimhne amháin. Tá sé seo tábhachtach nuair is gá duit tábla il-gigabyte a shórtáil le maolán cuimhne 100-megabyte amháin.

Tabhair faoi deara: tugtar algartam den chineál seo sórt seachtrach.

Is féidir leat é a athrú chun a reáchtáil ar phróisis / snáitheanna / freastalaithe iolracha.

Mar shampla, tá sórtáil chumaisc dáilte ar cheann de na príomhchodanna Hadoop (atá ina struchtúr i sonraí móra).

Is féidir leis an algartam seo luaidhe a thiontú ina ór (i ndáiríre!).

Úsáidtear an t-algartam sórtála seo i bhformhór na mbunachair sonraí (más rud é nach léir), ach ní hé an t-aon cheann amháin é. Más mian leat tuilleadh eolais a fháil, is féidir leat é seo a léamh obair thaighde, a phléann na buntáistí agus na míbhuntáistí a bhaineann le halgartaim sórtála bunachar sonraí coitianta.

Eagar, Crann agus Tábla Hash

Anois go dtuigeann muid an smaoineamh ar chastacht ama agus sórtáil, ba chóir dom a insint duit faoi 3 struchtúr sonraí. Tá sé seo tábhachtach mar gheall siad atá mar bhunús le bunachair shonraí nua-aimseartha. Tabharfaidh mé isteach an coincheap freisin innéacs bunachar sonraí.

Массив

Is é eagar déthoiseach an struchtúr sonraí is simplí. Is féidir smaoineamh ar thábla mar eagar. Mar shampla:

Is tábla é an t-eagar déthoiseach seo le sraitheanna agus colúin:

Léiríonn gach líne eintiteas
Stórálann colúin airíonna a chuireann síos ar an eintiteas.
Stórálann gach colún sonraí de chineál ar leith (slánuimhir, teaghrán, dáta...).

Tá sé seo áisiúil chun sonraí a stóráil agus a léirshamhlú, áfach, nuair is gá duit luach sonrach a fháil, níl sé seo oiriúnach.

Mar shampla, dá mbeifeá ag iarraidh teacht ar na fir go léir a oibríonn sa RA, bheadh ort breathnú ar gach sraith le fáil amach an mbaineann an tsraith sin leis an RA. Cosnóidh sé N idirbhearta ortI gcás ina N - líon na línte, nach bhfuil go dona, ach d'fhéadfadh go mbeadh bealach níos tapúla? Anois tá sé in am againn aithne a chur ar na crainn.

Nóta: Soláthraíonn formhór na mbunachair shonraí nua-aimseartha eagair leathnaithe chun táblaí a stóráil go héifeachtach: táblaí eagraithe carn agus táblaí innéacs-eagraithe. Ach ní athraíonn sé seo an fhadhb a bhaineann le riocht sonrach a aimsiú go tapa i ngrúpa colúin.

Crann bunachar sonraí agus innéacs

Is crann dénártha cuardaigh é crann cuardaigh dénártha le maoin speisialta, ní mór gurb é an eochair ag gach nód:

níos mó ná go léir na heochracha atá stóráilte sa subtree chlé
níos lú ná na heochracha go léir atá stóráilte sa subtree ceart

A ligean ar a fheiceáil cad a chiallaíonn sé seo amhairc

Idea

Tá N = 15 eilimint ag an gcrann seo. Ligean le rá go bhfuilim ag lorg 208:

Tosaím ag an bhfréamh arb é 136 an eochair.
398>208 dá bhrí sin táim ag féachaint ar an bhfochrann clé de nód 398
250>208 dá bhrí sin táim ag féachaint ar an bhfochrann clé de nód 250
200<208, dá bhrí sin táim ag féachaint ar an bhfochrann ceart de nód 200. Ach níl fo-chraobh ceart ag 200, níl luach ann (mar má tá sé ann, beidh sé san fhochrann ceart 200).

Anois, a ligean ar a rá go bhfuil mé ag lorg 40

Tosaíonn mé ag an fhréamh a bhfuil a eochair 136. Ós rud é 136 > 40, táim ar an subtree clé de nód 136.
80 > 40, mar sin táim ag féachaint ar an bhfochrann clé de nód 80
40= 40, nód ann. Aisghabhaim an t-aitheantas ró taobh istigh den nód (nach dtaispeántar sa phictiúr) agus táim sa tábla don ID ró a thugtar.
Má bhíonn aithne agam ar an ró-aitheantas is féidir liom fios a bheith agam go díreach cá bhfuil na sonraí sa tábla, ionas gur féidir liom iad a aisghabháil láithreach.

Sa deireadh, cosnóidh an dá chuardach líon na leibhéal taobh istigh den chrann dom. Má léann tú an chuid faoi shórtáil chumaisc go cúramach, ba cheart duit a fheiceáil go bhfuil leibhéil loga (N). Tharlaíonn sé, loga costas cuardaigh(N), ní dona!

Fillfimid ar ár bhfadhb

Ach tá sé seo an-teibí, mar sin a ligean ar ais go dtí ár fhadhb. In ionad slánuimhir shimplí, samhlaigh teaghrán a sheasann do thír duine sa tábla roimhe seo. Ligean le rá go bhfuil crann agat ina bhfuil an réimse "tír" (colún 3) den tábla:

Más mian leat a fháil amach cé a oibríonn sa RA
féachann tú ar an gcrann chun an nód a sheasann don Bhreatain Mhór a fháil
taobh istigh de "UKnode" gheobhaidh tú an suíomh na taifid oibrithe RA.

Cosnóidh an cuardach seo oibríochtaí loga(N) seachas oibríochtaí N má úsáideann tú an t-eagar go díreach. Ba é an rud a chuir tú i láthair díreach innéacs bunachar sonraí.

Is féidir leat crann innéacs a thógáil le haghaidh aon ghrúpa réimsí (teaghrán, uimhir, 2 líne, uimhir agus teaghrán, dáta...) chomh fada agus a bhfuil feidhm agat chun eochracha a chur i gcomparáid (.i. grúpaí réimse) ionas gur féidir leat a shocrú ordú i measc na heochracha (mar atá i gcás aon chineálacha bunúsacha sa bhunachar sonraí).

B+Innéacs Crann

Cé go n-oibríonn an crann seo go maith chun luach sonrach a fháil, tá fadhb BIG nuair is gá duit ilghnéithe a fháil idir dhá luach. Cosnóidh sé seo O(N) mar beidh ort féachaint ar gach nód sa chrann agus seiceáil an bhfuil sé idir an dá luach seo (m.sh. le trasnú ordúil an chrainn). Ina theannta sin, níl an oibríocht seo cairdiúil do dhiosca I/O mar go gcaithfidh tú an crann ar fad a léamh. Ní mór dúinn teacht ar bhealach a fhorghníomhú go héifeachtach iarratas raon. Chun an fhadhb seo a réiteach, úsáideann bunachair shonraí nua-aimseartha leagan mionathraithe den chrann roimhe seo ar a dtugtar B+Tree. I gcrann B+:

na nóid is ísle amháin (duilleoga) stóráil faisnéise (suíomh na rónna sa tábla gaolmhar)
tá an chuid eile de na nóid anseo le haghaidh ródú go dtí an nód ceart le linn cuardaigh.

Mar a fheiceann tú, tá níos mó nóid anseo (faoi dhó). Go deimhin, tá nóid bhreise agat, "nóid chinnidh", a chabhróidh leat an nód ceart a aimsiú (a stórálann suíomh na sraitheanna sa tábla gaolmhar). Ach tá castacht an chuardaigh fós ag O(log(N)) (níl ach leibhéal amháin eile). Is é an difríocht mhór go tá nóid ag an leibhéal níos ísle ceangailte lena gcomharbaí.

Leis an gCrann B+ seo, má tá tú ag lorg luachanna idir 40 agus 100:

Ní gá duit ach 40 a lorg (nó an luach is gaire tar éis 40 mura bhfuil 40 ann) mar a rinne tú leis an gcrann roimhe seo.
Ansin bailigh 40 oidhre ag baint úsáide as naisc dhíreacha oidhre go dtí go mbainfidh tú 100 amach.

Ligean le rá go bhfaighidh tú comharba M agus tá nóid N ag an gcrann. Loga(N) cosúil leis an gcrann roimhe seo a fháil ar nód ar leith. Ach a luaithe a gheobhaidh tú an nód seo, gheobhaidh tú comharba M in oibríochtaí M le tagairtí dá gcomharbaí. Ní chosnaíonn an cuardach seo ach M+log(N) oibríochtaí i gcomparáid le N oibríochtaí ar an gcrann roimhe sin. Ina theannta sin, ní gá duit an crann iomlán a léamh (nóid M + log(N) amháin), rud a chiallaíonn go n-úsáidtear níos lú diosca. Má tá M beag (m.sh. 200 sraith) agus N mór (1 sraitheanna), beidh difríocht BIG ann.

Ach tá fadhbanna nua anseo (arís!). Má chuireann tú nó má scriosann tú ró sa bhunachar sonraí (agus mar sin san innéacs B+Crann a bhaineann leis):

ní mór duit ord a choinneáil idir na nóid taobh istigh de Chrann B+, nó ní bheidh tú in ann na nóid taobh istigh de chrann neamhshórtáilte a aimsiú.
ní mór duit an t-íoslíon leibhéal is féidir a choinneáil i B+Tree, nó déantar O(N) de chastacht ama O(log(N)).

I bhfocail eile, caithfidh B+Tree a bheith féin-ordaithe agus cothrom. Ar ámharaí an tsaoil, is féidir é seo a dhéanamh le hoibríochtaí cliste a scriosadh agus a chur isteach. Ach tá costas ag baint leis seo: costas O(log(N)) a chuirtear isteach agus a scriosadh i gcrann B+. Sin an fáth ar chuala cuid agaibh é sin ní smaoineamh maith é an iomarca innéacsanna a úsáid. Go deimhin, tá tú ag moilliú síos go tapa cuir isteach/nuashonraigh/scrios as a chéile i dtáblamar ní mór don bhunachar sonraí innéacsanna an tábla a nuashonrú ag baint úsáide as oibríocht chostasach O(log(N)) do gach innéacs. Ina theannta sin, ciallaíonn cur innéacsanna níos mó ualach oibre le haghaidh bainisteoir idirbheart (cuirfear síos air ag deireadh an ailt).

Le haghaidh tuilleadh sonraí, is féidir leat an t-alt Vicipéid ar B+crann. Más mian leat sampla de B+Tree a chur i bhfeidhm i mbunachar sonraí, féach airteagal seo и airteagal seo ó phríomhfhorbróir MySQL. Díríonn siad araon ar an gcaoi a láimhseálann InnoDB (an t-inneall MySQL) innéacsanna.

Nóta: Dúirt léitheoir liom, mar gheall ar bharrfheabhsú ar leibhéal íseal, gur cheart go mbeadh an crann B+ cothromaithe go hiomlán.

Hashtable

Is é ár struchtúr sonraí tábhachtach deireanach ná an tábla hash. Tá sé seo an-úsáideach nuair is mian leat luachanna a chuardach go tapa. Ina theannta sin, cabhróidh tuiscint ar thábla hash linn oibriú le chéile bunachar sonraí coitianta ar a dtugtar ceangal hash a thuiscint níos déanaí ( hash páirt a ghlacadh). Úsáideann an bunachar sonraí an struchtúr sonraí seo freisin chun roinnt rudaí inmheánacha a stóráil (m.sh. tábla glas nó linn maolánach, feicfimid an dá choincheap seo níos déanaí).

Is éard is tábla hais ann ná struchtúr sonraí a aimsíonn eilimint go tapa trína heochair. Chun tábla hash a thógáil ní mór duit a shainiú:

ключ do do eilimintí
feidhm hash le haghaidh eochracha. Tugann na hashes eochair ríofa suíomh na n-eilimintí (ar a dtugtar deighleoga ).
feidhm chun eochracha a chur i gcomparáid. Nuair a bheidh an mhír cheart aimsithe agat, ní mór duit an eilimint atá uait a aimsiú laistigh den mhír agus an chomparáid seo á úsáid agat.

Sampla simplí

Glacaimis sampla soiléir:

Tá 10 mír sa tábla hash seo. Toisc go bhfuil mé leisciúil, níor léirigh mé ach 5 mhír, ach tá a fhios agam go bhfuil tú cliste, mar sin ligfidh mé duit na 5 cinn eile a phictiúr leat féin. D'úsáid mé feidhm hash modulo 10 den eochair. I bhfocail eile, ní stórálann mé ach an dhigit dheireanach d'eochair an eilimint chun a deighleog a fháil:

más é 0 an digit dheireanach, titeann an eilimint i mír 0,
más é 1 an digit dheireanach, titeann an eilimint i mír 1,
más é 2 an digit dheireanach, titeann an eilimint isteach i limistéar 2,
...

Níl sa fheidhm chomparáide a d’úsáid mé ach comhionannas idir dhá shlánuimhir.

Ligean le rá gur mhaith leat eilimint 78 a fháil:

Ríomhann an tábla hash an cód hash do 78, is é sin 8.
Breathnaíonn an tábla hash ar mhír 8, agus is é 78 an chéad eilimint a aimsíonn sé.
Tugann sí mír 78 ar ais chugat
Ní chosnaíonn cuardaigh ach 2 oibríocht (ceann amháin chun an luach hais a ríomh agus an ceann eile chun an eilimint laistigh den teascán a chuardach).

Anois, déarfaimid gur mhaith leat eilimint 59 a fháil:

Ríomhann an tábla hash an cód hash do 59, is é sin 9.
Cuardaíonn an tábla hais i mír 9, is é 99 an chéad eilimint a aimsítear. Ós rud é go 99!=59, ní eilimint bhailí í eilimint 99.
Ag baint úsáide as an loighic chéanna, tógtar an dara eilimint (9), an tríú (79), ..., an ceann deireanach (29).
Níor aimsíodh an eilimint.
Chosain an cuardach 7 oibríocht.

Feidhm hash maith

Mar a fheiceann tú, ag brath ar an luach atá á lorg agat, níl an costas mar an gcéanna!

Má athraím anois an fheidhm hash modulo 1 den eochair (is é sin, na 000 dhigit dheireanacha a thógáil), ní chosnaíonn an dara cuardach ach oibríocht 000 toisc nach bhfuil aon eilimintí sa mhír 6. Is é an fíordhúshlán ná feidhm mhaith hash a aimsiú a chruthóidh buicéid ina bhfuil líon an-bheag eilimintí.

I mo shampla, tá sé éasca feidhm hash maith a aimsiú. Ach is sampla simplí é seo, tá sé níos deacra feidhm hash maith a aimsiú nuair is é an eochair:

teaghrán (mar shampla - sloinne)
2 líne (mar shampla - sloinne agus céadainm)
2 líne agus dáta (mar shampla - sloinne, céad ainm agus dáta breithe)
...

Le feidhm hash maith, cosnaíonn cuardaigh tábla hais O(1).

Eagar vs tábla hash

Cén fáth nach n-úsáidfeá eagar?

Hmm, ceist mhaith.

Is féidir leis an tábla hash luchtaithe go páirteach i gcuimhne, agus is féidir leis na codanna atá fágtha fanacht ar an diosca.
Le eagar ní mór duit spás tadhlach a úsáid mar chuimhne. Má tá tú ag luchtú tábla mór tá sé an-deacair go leor spáis leanúnach a fháil.
Le haghaidh tábla hash, is féidir leat an eochair a theastaíonn uait a roghnú (mar shampla, sloinne tíre agus duine).

Chun tuilleadh eolais a fháil, is féidir leat an t-alt a léamh faoi javaHashMap, atá ina chur i bhfeidhm éifeachtach tábla hash; ní gá duit Java a thuiscint chun na coincheapa a chlúdaítear san Airteagal seo a thuiscint.

Foinse: will.com

Conas a Oibríonn Bunachair Choibhneasta (Cuid 1)