Hi Habr! Bidh mi a’ toirt d’ aire eadar-theangachadh an artaigil
"Ciamar a tha stòr-dàta dàimh ag obair".

Nuair a thig e gu stòran-dàta dàimh chan urrainn dhomh cuideachadh ach smaoineachadh gu bheil rudeigin a dhìth. Tha iad air an cleachdadh anns gach àite. Tha mòran stòran-dàta eadar-dhealaichte rim faighinn, bhon SQLite beag agus feumail gu Teradata cumhachdach. Ach chan eil ann ach beagan artaigilean a mhìnicheas mar a tha an stòr-dàta ag obair. Faodaidh tu thu fhèin a lorg le bhith a’ cleachdadh “howdoesarelationaldatabasework” gus faicinn dè cho beag de thoraidhean a th’ ann. A bharrachd air an sin, tha na h-artaigilean seo goirid. Ma tha thu a’ coimhead airson na teicneòlasan buzzy as ùire (BigData, NoSQL no JavaScript), gheibh thu barrachd artaigilean nas doimhne a’ mìneachadh mar a tha iad ag obair.

A bheil stòran-dàta dàimh ro shean agus ro thrang airson a mhìneachadh taobh a-muigh chùrsaichean oilthigh, pàipearan rannsachaidh agus leabhraichean?

Mar leasaiche, is fuath leam a bhith a’ cleachdadh rudeigin nach eil mi a’ tuigsinn. Agus ma chaidh stòran-dàta a chleachdadh airson còrr is 40 bliadhna, feumaidh adhbhar a bhith ann. Thar nam bliadhnaichean, tha mi air ceudan uairean a thìde a chuir seachad a’ tuigsinn nam bogsaichean dubha neònach sin a bhios mi a’ cleachdadh a h-uile latha. Stòr-dàta Dàimheach gu math inntinneach oir tha iad stèidhichte air bun-bheachdan feumail agus ath-chleachdadh. Ma tha ùidh agad ann a bhith a’ tuigsinn stòr-dàta, ach nach robh ùine no miann agad a-riamh sgrùdadh a dhèanamh air a’ chuspair fharsaing seo, bu chòir dhut an artaigil seo a mhealtainn.

Ged a tha tiotal an artaigil seo follaiseach, chan e adhbhar an artaigil seo tuigsinn mar a chleachdas tu an stòr-dàta. Mar sin, bu chòir dhut fios a bhith agad mu thràth mar a sgrìobhas tu iarrtas ceangail sìmplidh agus ceistean bunaiteach RAW; air neo is dòcha nach tuig thu an artaigil seo. Sin an aon rud a dh’ fheumas tu a bhith eòlach, mìnichidh mi an còrr.

Tòisichidh mi le cuid de bhunaitean saidheans coimpiutaireachd, leithid iom-fhillteachd ùine nan algorithms (BigO). Tha fios agam gu bheil gràin aig cuid agaibh air a’ bhun-bheachd seo, ach às aonais sin cha bhith e comasach dhut na dlùth-cheanglaichean taobh a-staigh an stòr-dàta a thuigsinn. Leis gur e cuspair mòr a tha seo, Cuiridh mi fòcas air na tha mi a’ smaoineachadh a tha cudromach: mar a tha an stòr-dàta ag obair SQL rannsachadh. Bheir mi a-steach dìreach bun-bheachdan stòr-dàtagus am bi beachd agad aig deireadh an artaigil air dè tha dol fon chochall.

Leis gur e artaigil fada agus teignigeach a tha seo anns a bheil tòrr algorithms agus structaran dàta, gabh do chuid ùine airson leughadh troimhe. Faodaidh cuid de bhun-bheachdan a bhith duilich a thuigsinn; faodaidh tu an sgioblachadh agus fhathast am beachd coitcheann fhaighinn.

Airson an fheadhainn as eòlaiche nur measg, tha an artaigil seo air a roinn ann an 3 pàirtean:

• Sealladh farsaing air co-phàirtean stòr-dàta aig ìre ìosal agus àrd-ìre
• Sealladh farsaing air a’ phròiseas Optimization Ceist
• Sealladh farsaing air Gnìomh agus Riaghladh Pool Bufair

Air ais gu bunaitean

O chionn bhliadhnaichean (ann an galaxy fada, fada air falbh ...), dh'fheumadh fios a bhith aig luchd-leasachaidh dè dìreach an àireamh de ghnìomhachdan a bha iad a 'còdadh. Bha eòlas aca air na h-algorithms agus na structaran dàta aca le cridhe oir cha b’ urrainn dhaibh an CPU agus cuimhne nan coimpiutairean slaodach aca a chaitheamh.

Anns a 'phàirt seo, cuiridh mi nad chuimhne cuid de na bun-bheachdan sin oir tha iad riatanach airson an stòr-dàta a thuigsinn. Bheir mi a-steach am bun-bheachd cuideachd clàr-amais stòr-dàta.

O(1) vs O(n2)

An-diugh, chan eil dragh aig mòran de luchd-leasachaidh mu iom-fhillteachd ùine algorithms ... agus tha iad ceart!

Ach nuair a tha thu a’ dèiligeadh ri tòrr dàta (chan eil mi a’ bruidhinn mìltean) no ma tha thu a’ strì ann am milliseconds, bidh e deatamach a’ bhun-bheachd seo a thuigsinn. Agus mar a shaoileadh tu, feumaidh stòran-dàta dèiligeadh ris an dà shuidheachadh! Cha toir mi ort barrachd ùine a chaitheamh na tha riatanach gus a’ phuing a chuir an cèill. Cuidichidh seo sinn le bhith a’ tuigsinn bun-bheachd optimization stèidhichte air cosgais nas fhaide air adhart (cosgais stèidhichte optimization).

Bun-bheachd

Iom-fhillteachd ùine an algairim air a chleachdadh gus faicinn dè cho fada ‘s a bheir algairim gus a chrìochnachadh airson tomhas sònraichte de dhàta. Airson cunntas a thoirt air an iom-fhillteachd seo, bidh sinn a’ cleachdadh comharradh matamataigeach mòr O. Tha an comharradh seo air a chleachdadh le gnìomh a tha ag innse cia mheud gnìomh a tha a dhìth air algairim airson àireamh shònraichte de chuir-a-steach.

Mar eisimpleir, nuair a chanas mi “tha iom-fhillteachd O (some_function ()) aig an algairim seo", tha e a’ ciallachadh gu bheil feum aig an algairim air cuid de ghnìomhachd (a_certain_amount_of_data) gus tomhas sònraichte de dhàta a phròiseasadh.

Mar sin, Chan e an ìre de dhàta a tha cudromach**, air dhòigh eile ** mar a tha an àireamh de ghnìomhachd ag àrdachadh le meud dàta a’ sìor fhàs. Chan eil iom-fhillteachd ùine a’ toirt seachad àireamh cheart de ghnìomhachd, ach tha e na dhòigh math air ùine cur gu bàs a thomhas.

Anns a’ ghraf seo chì thu an àireamh de dh’ obrachaidhean an coimeas ris an ìre de dhàta cuir a-steach airson diofar sheòrsaichean iom-fhillteachd ùine algairim. Chleachd mi sgèile logarithmach airson an taisbeanadh. Ann am faclan eile, bidh an àireamh de dhàta ag èirigh gu luath bho 1 gu 1 billean. Chì sinn:

• Tha O(1) no iom-fhillteachd seasmhach fhathast seasmhach (air dhòigh eile cha bhiodh e air ainmeachadh mar iom-fhillteachd seasmhach).
• O(log(n)) fhathast ìosal eadhon le billeanan de dhàta.
• An duilgheadas as miosa - O(n2), far a bheil an àireamh de ghnìomhachdan a’ fàs gu luath.
• Bidh an dà dhuilgheadas eile ag àrdachadh a cheart cho luath.

eisimpleirean

Le glè bheag de dhàta, tha an diofar eadar O(1) agus O(n2) glè bheag. Mar eisimpleir, canaidh sinn gu bheil algorithm agad a dh’ fheumas 2000 eileamaid a phròiseasadh.

• Cosgaidh an algairim O(1) 1 obrachadh dhut
• Cosgaidh an algairim O(log(n)) 7 obrachaidhean dhut
• Cosgaidh an algairim O(n) 2 gnìomhachd dhut
• Cosgaidh an algairim O(n*log(n)) 14 gnìomhachd dhut
• Cosgaidh an algairim O(n2) 4 gnìomhachd dhut

Tha coltas mòr air an eadar-dhealachadh eadar O(1) agus O(n2) (4 millean gnìomhachd) ach caillidh tu 2 ms aig a’ char as àirde, dìreach ùine airson do shùilean a bhrùthadh. Gu dearbh, faodaidh luchd-giullachd an latha an-diugh pròiseasadh ceudan de mhilleanan de ghnìomhachd gach diog. Sin as coireach nach eil coileanadh agus optimization na chùis ann am mòran phròiseactan IT.

Mar a thuirt mi, tha e fhathast cudromach fios a bhith agad air a’ bhun-bheachd seo nuair a bhios tu ag obair le tòrr dàta. Ma dh'fheumas an algairim an turas seo 1 eileamaid a phròiseasadh (nach eil cho mòr airson stòr-dàta):

• Cosgaidh an algairim O(1) 1 obrachadh dhut
• Cosgaidh an algairim O(log(n)) 14 obrachaidhean dhut
• Cosgaidh an algairim O(n) 1 gnìomhachd dhut
• Cosgaidh an algairim O(n*log(n)) 14 gnìomhachd dhut
• Cosgaidh an algairim O(n2) 1 gnìomhachd dhut

Cha do rinn mi am matamataigs, ach chanainn leis an algairim O (n2) gu bheil ùine agad cofaidh òl (eadhon dhà!). Ma chuireas tu 0 eile ris an tomhas dàta, bidh ùine agad nap a ghabhail.

Rachamaid nas doimhne

Airson iomradh:

• Lorgaidh deagh sgrùdadh clàr hash eileamaid ann an O(1).
• Le bhith a’ sgrùdadh craobh le deagh chothromachadh bheir sin toraidhean ann an O(log(n)).
• Bheir rannsachadh sreath toraidhean ann an O(n).
• Tha iom-fhillteachd O(n * log(n)) aig na h-algorithms seòrsachaidh as fheàrr.
• Tha iom-fhillteachd O(n2) aig algairim seòrsachaidh dona.

Nota: Anns na pàirtean a leanas chì sinn na h-algorithms agus na structaran dàta sin.

Tha grunn sheòrsaichean de iom-fhillteachd ùine algorithm ann:

• suidheachadh cùise cuibheasach
• suidheachadh cùise as fheàrr
• agus an suidheachadh as miosa

Is e iom-fhillteachd ùine gu tric an suidheachadh as miosa.

Cha robh mi a’ bruidhinn ach mu iom-fhillteachd ùine an algairim, ach tha iom-fhillteachd cuideachd a’ buntainn ri:

• caitheamh cuimhne air an algairim
• algairim caitheamh diosc I/O

Gu dearbh, tha duilgheadasan nas miosa na n2, mar eisimpleir:

• n4: tha seo uamhasach! Tha an iom-fhillteachd seo aig cuid de na h-algorithms a chaidh ainmeachadh.
• 3n: tha seo nas miosa buileach! Tha an iom-fhillteachd seo aig aon de na h-algorithms a chì sinn ann am meadhan an artaigil seo (agus tha e air a chleachdadh ann an iomadh stòr-dàta).
• factorial n: chan fhaigh thu na toraidhean agad gu bràth eadhon le beagan dàta.
• nn: Ma thachras tu air an iom-fhillteachd seo, bu chòir dhut faighneachd dhut fhèin an e seo an raon gnìomhachd agad dha-rìribh ...

Nota: Cha tug mi dhut am fìor mhìneachadh air an t-sònrachadh mòr O, dìreach beachd. Faodaidh tu an artaigil seo a leughadh aig Uicipeid airson mìneachadh fìor (asymptotic).

MergeSort

Dè nì thu nuair a dh'fheumas tu cruinneachadh a rèiteachadh? Dè? Canaidh tu an seòrsa () gnìomh… Ceart gu leòr, deagh fhreagairt... Ach airson stòr-dàta, feumaidh tu tuigsinn mar a tha an gnìomh seòrsa () seo ag obair.

Tha grunn algorithms seòrsachaidh math ann, agus mar sin cuiridh mi fòcas air an fheadhainn as cudromaiche: seòrsa cothlamadh. Is dòcha nach eil thu a’ tuigsinn carson a tha seòrsachadh dàta feumail an-dràsta, ach bu chòir dhut às deidh a ’phàirt optimization ceist. A bharrachd air an sin, cuidichidh tuigse air an t-seòrsa aonaidh sinn nas fhaide air adhart le bhith a’ tuigsinn gnìomhachd ceangail stòr-dàta cumanta ris an canar choimeasgadh còmhla (comann aonaidh).

Thig còmhla

Coltach ri mòran algorithms feumail, tha seòrsachadh aonachadh an urra ri cleas: bidh a bhith a’ cothlamadh 2 shreath sheòrsach de mheud N/2 ann an sreath seòrsaichte N-eileamaid a’ cosg gnìomhachd N a-mhàin. Canar aonachadh ris an obair seo.

Chì sinn dè tha seo a’ ciallachadh le eisimpleir shìmplidh:

Tha am figear seo a’ sealltainn, gus an t-sreath dheireannaich de 8-eileamaidean a thogail, nach fheum thu ach ath-aithris aon turas thairis air na h-sreathan 2 4-eileamaidean. Leis gu bheil an dà raon 4-eileamaid air an rèiteachadh mu thràth:

• 1) bidh thu a’ dèanamh coimeas eadar an dà eileamaid làithreach ann an dà shreath (aig an toiseach sruth = an toiseach)
• 2) an uairsin gabh am fear as lugha airson a chuir ann an sreath de 8 eileamaidean
• 3) agus gluais chun ath eileamaid san raon far an do ghabh thu an eileamaid as lugha
• agus ath-aithris 1,2,3 gus an ruig thu an eileamaid mu dheireadh de aon de na h-arrays.
• An uairsin gabhaidh tu na h-eileamaidean eile den t-sreath eile gus an cuir ann an sreath de 8 eileamaidean.

Bidh seo ag obair leis gu bheil an dà shreath 4-eileamaidean air an òrdachadh agus mar sin chan fheum thu “a dhol air ais” anns na h-arrays sin.

A-nis gu bheil sinn a’ tuigsinn a’ chleas, seo am pseudocode agam airson aonadh:

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;

Bidh an seòrsa cothlamadh a ’briseadh duilgheadas gu duilgheadasan nas lugha agus an uairsin a’ lorg toraidhean nan duilgheadasan nas lugha gus toradh na duilgheadas tùsail fhaighinn (nota: canar sgaradh agus ceannsachadh ris an t-seòrsa algairim seo). Mura tuig thu an algairim seo, na gabh dragh; Cha do thuig mi a’ chiad uair a chunnaic mi e. Mas urrainn dha do chuideachadh, tha mi a’ faicinn an algairim seo mar algairim dà-ìre:

• Ìre roinneadh, far a bheil an raon air a roinn ann an arrays nas lugha
• Is e an ìre rèiteachaidh far a bheil arrays beaga air an cur còmhla (a’ cleachdadh aonadh) gus sreath nas motha a chruthachadh.

Ìre roinneadh

Anns an ìre roinneadh, tha an t-sreath air a roinn ann an arrays aonadach ann an 3 ceumannan. Is e an àireamh foirmeil de cheumannan log (N) (bho N = 8, log(N) = 3).

Ciamar a tha fios agam air an seo?

Tha mi genius! Ann am facal - matamataig. Is e am beachd gu bheil gach ceum a 'roinn meud an t-sreath thùsail le 2. Is e an àireamh de cheumannan an àireamh de thursan as urrainn dhut an t-sreath thùsail a roinn na dhà. Is e seo an dearbh mhìneachadh air logarithm (bonn 2).

Ìre seòrsachaidh

Anns an ìre rèiteachaidh, tòisichidh tu le arrays aonadach (aon-eileamaid). Rè gach ceum cuiridh tu an sàs ioma-obair aonaidh agus is e a’ chosgais iomlan N = 8 gnìomhachd:

• Anns a’ chiad ìre tha 4 co-aonaidhean agad a chosgas 2 ghnìomhachd gach fear
• Anns an dàrna ceum tha 2 cho-aonadh agad a chosgas 4 gnìomhachd gach fear
• Anns an treas ceum tha aonadh 1 agad a chosgas 8 obrachaidhean

Leis gu bheil ceumannan log(N) ann, an suim iomlan de na gnothaichean gu lèir le roinn N * obraichean log(N)..

Buannachdan seòrsachadh measgachadh

Carson a tha an algairim seo cho cumhachdach?

Air sgàth:

• Faodaidh tu atharrachadh gus lorg-coise na cuimhne a lughdachadh gus nach cruthaich thu arrays ùra ach gun atharraich thu an raon cuir a-steach gu dìreach.

Thoir an aire: canar an seòrsa algairim seo in-àite (rèiteach gun chuimhne a bharrachd).

• Faodaidh tu atharrachadh gus àite diosc agus beagan cuimhne a chleachdadh aig an aon àm gun a bhith a’ toirt a-steach diosc mòr I / O os an cionn. Is e am beachd a bhith a’ luchdachadh a-steach do chuimhne a-mhàin na pàirtean sin a tha gan giullachd an-dràsta. Tha seo cudromach nuair a dh'fheumas tu clàr ioma-gigabyte a rèiteachadh le dìreach bufair cuimhne 100-megabyte.

Thoir an aire: canar an seòrsa algairim seo seòrsa taobh a-muigh.

• Faodaidh tu atharrachadh gus ruith air grunn phròiseasan / snàithleanan / frithealaichean.

Mar eisimpleir, is e seòrsachadh aonadh sgaoilte aon de na prìomh phàirtean Hadoop (a tha na structar ann an dàta mòr).

• Faodaidh an algairim seo luaidhe a thionndadh gu òr (dha-rìribh!).

Tha an algairim seòrsachaidh seo air a chleachdadh anns a’ mhòr-chuid (mura h-eil uile) stòran-dàta, ach chan e an aon fhear a th’ ann. Ma tha thu airson tuilleadh fhaighinn a-mach, faodaidh tu seo a leughadh obair rannsachaidh, a bhios a’ beachdachadh air na buannachdan agus na h-eas-bhuannachdan a tha an cois algorithms seòrsachaidh stòr-dàta cumanta.

Array, craobh agus clàr hash

A-nis gu bheil sinn a 'tuigsinn a' bheachd air iom-fhillteachd ùine agus rèiteachadh, bu chòir dhomh innse dhut mu 3 structaran dàta. Tha seo cudromach oir tha iad a tha nam bunait airson stòran-dàta an latha an-diugh. Bheir mi a-steach am bun-bheachd cuideachd clàr-amais stòr-dàta.

Массив

Is e raon dà-thaobhach an structar dàta as sìmplidh. Faodar smaoineachadh air bòrd mar chlàr. Mar eisimpleir:

Tha an sreath 2-mheudach seo na chlàr le sreathan agus colbhan:

• Tha gach loidhne a’ riochdachadh eintiteas
• Bidh colbhan a’ stòradh thogalaichean a tha a’ toirt cunntas air an eintiteas.
• Bidh gach colbh a’ stòradh dàta de sheòrsa sònraichte (slàn-ìre, sreang, ceann-latha…).

Tha seo goireasach airson dàta a stòradh agus fhaicinn, ge-tà, nuair a dh’ fheumas tu luach sònraichte a lorg, chan eil seo freagarrach.

Mar eisimpleir, nam biodh tu airson a h-uile duine a tha ag obair san RA a lorg, dh'fheumadh tu coimhead air gach sreath gus faighinn a-mach am buin an loidhne sin don RA. Cosgaidh e N malairt dhutcàite N - àireamh de loidhnichean, rud nach eil dona, ach am faodadh dòigh nas luaithe a bhith ann? A-nis tha an t-àm ann dhuinn eòlas fhaighinn air na craobhan.

Nota: Bidh a’ mhòr-chuid de stòran-dàta an latha an-diugh a’ toirt seachad arrays leudaichte airson clàran a stòradh gu h-èifeachdach: clàran eagraichte agus clàran-amais. Ach chan eil seo ag atharrachadh an duilgheadas a bhith a 'lorg suidheachadh sònraichte gu luath ann am buidheann de cholbhan.

Stòr-dàta craobh agus clàr-amais

Is e craobh dà-chànanach a th 'ann an craobh sgrùdaidh dà-chànanach le seilbh sònraichte, feumaidh an iuchair aig gach nód a bhith:

• nas motha na na h-iuchraichean gu lèir a tha air an stòradh san fho-chraobh chlì
• nas lugha na a h-uile iuchair a tha air a stòradh san fho-chraobh cheart

Feuch sinn a-mach dè tha seo a 'ciallachadh gu lèirsinneach

Idea

Tha N = 15 eileamaidean aig a’ chraoibh seo. Canaidh sinn gu bheil mi a’ coimhead airson 208:

• Bidh mi a' tòiseachadh aig a' bhunait aig a bheil an iuchair 136. Bho 136<208, tha mi a' coimhead air an fho-chraobh cheart de nód 136.
• 398>208 mar sin tha mi a’ coimhead air an fho-chraobh chlì de nód 398
• 250>208 mar sin tha mi a’ coimhead air an fho-chraobh chlì de nód 250
• 200<208, uime sin tha mi ag amharc air an fho-chraobh deas de nòd 200. Ach cha'n 'eil fo-chraobh ceart aig 200. chan eil luach ann (oir ma tha e ann, bidh e san fho-chraobh cheart 200).

A-nis canaidh sinn gu bheil mi a’ coimhead airson 40

• Bidh mi a’ tòiseachadh aig a’ bhunait aig a bheil an iuchair 136. Bho 136 > 40, tha mi a’ coimhead air an fho-chraobh chlì de nód 136.
• 80 > 40, mar sin tha mi a’ coimhead air an fho-chraobh chlì de nód 80
• 40 = 40, node ann. Bidh mi a’ faighinn air ais an ID loidhne taobh a-staigh an nód (nach eil ri fhaicinn san dealbh) agus a’ coimhead sa chlàr airson an ID loidhne a chaidh a thoirt seachad.
• Le bhith eòlach air an ID loidhne leigidh sin dhomh fios a bhith agam càite a bheil an dàta sa chlàr, gus an urrainn dhomh fhaighinn air ais sa bhad.

Aig a 'cheann thall, cosgaidh an dà rannsachadh dhomh an àireamh de ìrean taobh a-staigh na craoibhe. Ma leughas tu am pàirt mu sheòrsachadh aonadh gu faiceallach, bu chòir dhut faicinn gu bheil ìrean log(N). Tha e a' tionndadh a-mach, log cosgais sgrùdaidh (N), Chan eil sin dona!

Tillidh sinn chun duilgheadas againn

Ach tha seo gu math eas-chruthach, mar sin leig dhuinn tilleadh chun duilgheadas againn. An àite slòigh shìmplidh, smaoinich air sreang a tha a’ riochdachadh dùthaich cuideigin sa chlàr roimhe. Canaidh sinn gu bheil craobh agad anns a bheil an raon “dùthaich” (colbh 3) den chlàr:

• Ma tha thu airson faighinn a-mach cò a tha ag obair san RA
• bidh thu a’ coimhead air a’ chraoibh gus an nód a tha a’ riochdachadh Breatainn fhaighinn
• taobh a-staigh "UKnode" gheibh thu far a bheil clàran luchd-obrach na RA.

Cosgaidh an rannsachadh seo gnìomhachd log(N) an àite gnìomhachd N ma chleachdas tu an t-sreath gu dìreach. Bha na tha thu dìreach air a thaisbeanadh clàr-amais stòr-dàta.

Faodaidh tu craobh clàr-amais a thogail airson buidheann raointean sam bith (sreang, àireamh, 2 loidhne, àireamh is sreang, ceann-latha...) fhad ‘s a tha gnìomh agad coimeas a dhèanamh eadar iuchraichean (ie buidhnean achaidh) gus an urrainn dhut suidheachadh òrdugh am measg nan iuchraichean (a tha fìor airson seòrsaichean bunaiteach sam bith san stòr-dàta).

Clàr-innse B+ craobh

Ged a tha a 'chraobh seo ag obair gu math airson luach sònraichte fhaighinn, tha duilgheadas BIG ann nuair a dh' fheumas tu faigh grunn eileamaidean eadar dà luach. Cosgaidh seo O(N) oir feumaidh tu coimhead air gach nód sa chraoibh agus dèanamh cinnteach a bheil e eadar an dà luach seo (m.e. le tar-chur òrdail den chraoibh). A bharrachd air an sin, chan eil an gnìomhachd seo càirdeil do I/O leis gu feum thu an craobh gu lèir a leughadh. Feumaidh sinn dòigh a lorg airson coileanadh èifeachdach iarrtas raon. Gus an duilgheadas seo fhuasgladh, bidh stòran-dàta an latha an-diugh a’ cleachdadh dreach atharraichte den chraobh a bh’ ann roimhe ris an canar B + Tree. Ann an craobh B+:

• dìreach na nodan as ìsle (fàgail) stòradh fiosrachaidh (suidheachadh nan sreathan sa chlàr co-cheangailte)
• tha an còrr de na nodan an seo airson slighe chun an t-slat cheart rè an rannsachaidh.

Mar a chì thu, tha barrachd nodan an seo (dà uair). Gu dearbh, tha nodan a bharrachd agad, "nodan co-dhùnaidh", a chuidicheas tu gus an nód ceart a lorg (a bhios a 'stòradh suidheachadh nan sreathan anns a' chlàr co-cheangailte). Ach tha iom-fhillteachd an sgrùdaidh fhathast O (log (N)) (chan eil ann ach aon ìre eile). Is e an diofar mòr sin tha nodan aig an ìre as ìsle ceangailte ris an fheadhainn a thàinig às a dhèidh.

Leis a’ Chraobh B + seo, ma tha thu a’ coimhead airson luachan eadar 40 agus 100:

• Feumaidh tu dìreach coimhead airson 40 (no an luach as fhaisge às deidh 40 mura h-eil 40 ann) mar a rinn thu leis a’ chraoibh roimhe.
• An uairsin cruinnich 40 oighre a’ cleachdadh ceanglaichean oighrean dìreach gus an ruig thu 100.

Canaidh sinn gun lorg thu luchd-leantainn M agus gu bheil nodan N aig a’ chraobh. Tha lorg nòd sònraichte a’ cosg log(N) mar a’ chraobh roimhe. Ach aon uair ‘s gum faigh thu an nód seo, gheibh thu luchd-leantainn M ann an gnìomhachd M le iomradh air an luchd-leantainn. Cha chosg an rannsachadh seo ach M+log(N) obrachaidhean an coimeas ri gnìomhachd N air a’ chraoibh roimhe. A bharrachd air an sin, cha leig thu leas an craobh slàn a leughadh (nòtaichean M + log (N) a-mhàin), a tha a’ ciallachadh nas lugha de chleachdadh diosc. Ma tha M beag (me 200 sreath) agus N mòr (1 sreathan), bidh eadar-dhealachadh MÒR ann.

Ach tha trioblaidean ùra an seo (a-rithist!). Ma chuireas tu ris no ma sguabas tu às sreath san stòr-dàta (agus mar sin anns a’ chlàr B+ Tree co-cheangailte):

• feumaidh tu òrdugh a chumail eadar na nodan taobh a-staigh craobh B +, air neo cha bhith e comasach dhut na nodan a lorg taobh a-staigh craobh gun sheòrsa.
• feumaidh tu an àireamh as lugha de ìrean a chumail ann am B + Tree, air neo bidh iom-fhillteachd ùine O (log (N)) gu bhith O (N).

Ann am faclan eile, feumaidh B + Tree a bhith fèin-òrdail agus cothromach. Gu fortanach, tha seo comasach le cuir às gu sgiobalta agus cuir a-steach obrachaidhean. Ach thig seo aig cosgais: cosgais cuir a-steach agus cuir às ann an craobh B + O (log (N)). Sin as coireach gu bheil cuid agaibh air sin a chluinntinn chan e deagh bheachd a th’ ann a bhith a’ cleachdadh cus chlàran-amais. dha-rìribh, tha thu a’ slaodadh sìos gu sgiobalta cuir a-steach / ùrachadh / cuir às do shreath ann an clàroir feumaidh an stòr-dàta clàran-amais a’ bhùird ùrachadh a’ cleachdadh gnìomhachd O(log(N)) daor airson gach clàr-amais. A bharrachd air an sin, tha cuir a-steach clàran-amais a’ ciallachadh barrachd eallach obrach airson manaidsear malairt (thèid a mhìneachadh aig deireadh an artaigil).

Airson tuilleadh fiosrachaidh, chì thu an artaigil Wikipedia air B+Craobh. Ma tha thu ag iarraidh eisimpleir de bhith a’ buileachadh B + Tree ann an stòr-dàta, thoir sùil an artaigil seo и an artaigil seo bho phrìomh leasaiche MySQL. Bidh iad le chèile ag amas air mar a làimhsicheas InnoDB (an einnsean MySQL) clàran-amais.

Nota: Dh’ innis leughadair dhomh, mar thoradh air optimizations ìre ìosal, gum bu chòir craobh B + a bhith gu tur cothromach.

Clàr hash

Is e an structar dàta cudromach mu dheireadh againn an clàr hash. Tha seo glè fheumail nuair a tha thu airson luachan a sgrùdadh gu sgiobalta. A bharrachd air an sin, cuidichidh tuigse air clàr hash sinn nas fhaide air adhart le bhith a’ tuigsinn gnìomhachd ceangail stòr-dàta cumanta ris an canar hash join ( hash còmhla). Tha an structar dàta seo cuideachd air a chleachdadh leis an stòr-dàta gus cuid de rudan a-staigh a stòradh (m.e. clàr glasaidh no amar-bufair, chì sinn an dà bhun-bheachd sin nas fhaide air adhart).

Is e structar dàta a th’ ann an clàr hash a lorgas gu sgiobalta eileamaid leis an iuchair aige. Gus clàr hash a thogail feumaidh tu mìneachadh:

• an iuchair airson na h-eileamaidean agad
• gnìomh hash airson iuchraichean. Bheir na prìomh hashes àireamhaichte suidheachadh nan eileamaidean (ris an canar earrannan ).
• gnìomh airson coimeas a dhèanamh eadar iuchraichean. Aon uair ‘s gu bheil thu air an earrann cheart a lorg, feumaidh tu an eileamaid a tha thu a’ lorg a lorg taobh a-staigh na roinne a’ cleachdadh a’ choimeas seo.

Eisimpleir shìmplidh

Gabhamaid eisimpleir soilleir:

Tha 10 earrannan anns a’ chlàr hash seo. Leis gu bheil mi leisg, cha do sheall mi ach 5 earrannan, ach tha fios agam gu bheil thu tapaidh, agus mar sin leigidh mi dhut dealbh a dhèanamh den 5 eile leat fhèin. Chleachd mi modulo gnìomh hash 10 den iuchair. Ann am faclan eile, cha bhith mi a’ stòradh ach an figear mu dheireadh de iuchair an eileamaid gus a roinn a lorg:

• mas e 0 an figear mu dheireadh, tuitidh an eileamaid ann an earrann 0,
• mas e 1 an figear mu dheireadh, tuitidh an eileamaid ann an earrann 1,
• mas e 2 an figear mu dheireadh, tuitidh an eileamaid ann an raon 2,
• ...

Is e an gnìomh coimeas a chleachd mi dìreach co-ionannachd eadar dà shlàn-chunntas.

Canaidh sinn gu bheil thu airson eileamaid 78 fhaighinn:

• Bidh an clàr hash a’ tomhas a’ chòd hash airson 78, is e sin 8.
• Bidh an clàr hash a’ coimhead air earrann 8, agus is e 78 a’ chiad eileamaid a lorgas e.
• Bidh i a’ tilleadh nì 78 thugad
• Cha chosg an rannsachadh ach 2 obair (aon airson luach hash obrachadh a-mach agus am fear eile airson coimhead suas an eileamaid taobh a-staigh na h-earrainn).

A-nis canaidh sinn gu bheil thu airson eileamaid 59 fhaighinn:

• Bidh an clàr hash a’ tomhas a’ chòd hash airson 59, is e sin 9.
• Bidh an clàr hash a’ sgrùdadh ann an earrann 9, is e 99 a’ chiad eileamaid a lorgar. Leis gu bheil 99!=59, chan eil eileamaid 99 na eileamaid dhligheach.
• A 'cleachdadh an aon loidsig, thèid an dàrna eileamaid (9), an treas (79), ..., an tè mu dheireadh (29) a ghabhail.
• Cha deach an eileamaid a lorg.
• Chosg an rannsachadh 7 obrachaidhean.

Deagh gnìomh hash

Mar a chì thu, a rèir an luach a tha thu a’ sireadh, chan eil a’ chosgais an aon rud!

Ma dh’ atharraicheas mi an gnìomh hash modulo 1 den iuchair (is e sin, a’ gabhail na 000 àireamhan mu dheireadh), cha chosg an dàrna lorg ach 000 obrachadh leis nach eil eileamaidean ann an earrann 6. Is e an fhìor dhùbhlan gnìomh hash math a lorg a chruthaicheas bucaidean anns a bheil àireamh glè bheag de eileamaidean.

Anns an eisimpleir agam, tha e furasta gnìomh hash math a lorg. Ach is e eisimpleir sìmplidh a tha seo, tha e nas duilghe gnìomh hash math a lorg nuair a tha an iuchair:

• sreang (mar eisimpleir - an t-ainm mu dheireadh)
• 2 loidhne (mar eisimpleir - ainm mu dheireadh agus ciad ainm)
• 2 loidhne agus ceann-latha (mar eisimpleir - ainm mu dheireadh, ciad ainm agus ceann-latha breith)
• ...

Le gnìomh hash math, tha seallaidhean clàr hash a’ cosg O(1).

Array vs clàr hash

Carson nach cleachd thu sreath?

Hmm, ceist mhath.

• Faodaidh an clàr hash a bhith air a luchdachadh gu ìre ann an cuimhne, agus faodaidh na roinnean a tha air fhàgail fuireach air an diosc.
• Le sreath feumaidh tu àite faisg air làimh a chleachdadh mar chuimhne. Ma tha thu a 'luchdachadh clàr mòr tha e gu math duilich àite leantainneach gu leòr a lorg.
• Airson clàr hash, faodaidh tu an iuchair a tha thu ag iarraidh a thaghadh (mar eisimpleir, ainm mu dheireadh na dùthcha agus an neach).

Airson tuilleadh fiosrachaidh, faodaidh tu an artaigil mu dheidhinn a leughadh JavaHashMap, a tha na bhuileachadh èifeachdach air clàr hash; chan fheum thu Java a thuigsinn gus na bun-bheachdan a tha air an còmhdach san artaigil seo a thuigsinn.

Source: www.habr.com