Hey Habr! Wergera gotarê pêşkêşî we dikim
"Dangehek pêwendiyek çawa dixebite".

Dema ku ew tê ser databasên pêwendiyê ez nikarim bifikirim ku tiştek winda ye. Ew li her derê têne bikar anîn. Gelek databasên cihêreng hene, ji SQLite-ya piçûk û bikêr heya Teradata-ya hêzdar. Lê tenê çend gotar hene ku diyar dikin ka databas çawa dixebite. Hûn dikarin ji xwe re bi karanîna "howdoesarelational databasework" bigerin da ku bibînin ka çend encam hene. Wekî din, ev gotar kurt in. Ger hûn li teknolojiyên herî paşîn ên buzzy (BigData, NoSQL an JavaScript) digerin, hûn ê gotarên kûrtir bibînin ku rave dikin ka ew çawa dixebitin.

Ma databasên pêwendiyê pir kevn û bêzar in ku li derveyî qursên zanîngehê, kaxezên lêkolînê û pirtûkan werin ravekirin?

Wekî pêşdebirek, ez ji karanîna tiştek ku ez fêm nakim nefret dikim. Û heke databas ji 40 salan zêdetir hatine bikar anîn, divê sedemek hebe. Bi salan, min bi sedan demjimêr derbas kir da ku bi rastî van qutiyên reş ên xerîb ên ku ez her roj bikar tînim fêm bikim. Daneyên Têkilî pir balkêş ji ber ku ew li ser têgînên kêrhatî û ji nû ve bi kar anîn. Ger hûn bala xwe didin ku databasek fam bikin, lê tu carî dem û meyla we tune ku hûn di vê mijara berfireh de hûr bibin, divê hûn ji vê gotarê kêfê bikin.

Her çend sernavê vê gotarê eşkere be jî, armanca vê gotarê ne ew e ku meriv çawa databasê bikar bîne fêm bike. Ji ber vê yekê, divê hûn berê zanibin ka meriv çawa daxwazek pêwendiyek hêsan û pirsên bingehîn dinivîse ZUDDE; wekî din hûn dikarin vê gotarê fam nekin. Tenê tişta ku divê hûn zanibin ev e, ez ê yên mayî rave bikim.

Ez ê bi hin bingehên zanistiya komputerê dest pê bikim, wek mînak tevliheviya demê ya algorîtmayan (BigO). Ez dizanim ku hin ji we ji vê têgehê nefret dikin, lê bêyî wê hûn ê nikaribin tevliheviyên di hundurê databasê de fam bikin. Ji ber ku ev mijarek mezin e, Ez ê li ser bisekinim tiştê ku ez difikirim girîng e: databas çawa dimeşe SQL pirs. Ez ê tenê bidim nasîn têgehên bingehîn ên databasêda ku di dawiya gotarê de hûn xwediyê ramanek bin ka çi diqewime.

Ji ber ku ev gotarek dirêj û teknîkî ye ku gelek algorîtma û strukturên daneyê vedihewîne, wextê xwe bigirin ku hûn wê bixwînin. Fêmkirina hin têgehan zehmet dibe; hûn dikarin wan berdin û hîn jî ramana giştî bistînin.

Ji bo kesên ku di nav we de zanatir in, ev gotar ji 3 beşan pêk tê:

Nêrînek li ser pêkhateyên databasa-asta nizm û astek bilind
Serpêhatiya Pêvajoya Optimîzasyona Query
Pêşniyara Danûstendin û Rêvebiriya Hewza Buffer

Vegere ser bingehîn

Sal berê (li galaksiyek dûr, dûr ...), pêşdebiran neçar bû ku tam hejmara operasyonên ku wan kod dikirin zanibin. Wan algorîtma û strukturên daneya xwe ji dil dizanibûn ji ber ku wan nedikarî CPU û bîranîna komputerên xwe yên hêdî winda bikin.

Di vê beşê de, ez ê hin ji van têgehan bi bîr bînim ji ber ku ew ji bo têgihiştina databasê bingehîn in. Ez ê têgehê jî bidim nasîn index database.

O (1) VS O (N2)

Naha, gelek pêşdebiran bala xwe nadin tevliheviya demê ya algorîtmayan ... û ew rast in!

Lê gava ku hûn bi gelek daneyan re mijûl dibin (ez bi hezaran nabêjim) an heke hûn di milîsekoyan de têdikoşin, fêmkirina vê têgehê krîtîk dibe. Û wekî ku hûn difikirin, databas neçar in ku bi her du rewşan re mijûl bibin! Ez ê nehêlim ku hûn ji hewcedariyê bêtir wext derbas bikin da ku hûn xalê bigihînin hev. Ev ê ji me re bibe alîkar ku paşê têgîna xweşbîniya lêçûn-based fam bikin (nirx Bingehîn optimization).

Concept

Tevliheviya demê ya algorîtmayê tê bikaranîn ji bo dîtina ka ew ê çiqas dirêj bigire ku algorîtmayek ji bo mîqdarek daneya dane. Ji bo danasîna vê tevliheviyê, em nîşana matematîkî ya mezin O bikar tînin. Ev nîşan bi fonksiyonek tê bikar anîn ku diyar dike ku algorîtmayek ji bo hejmareke danûstendinê çend operasyonan hewce dike.

Mînakî, gava ku ez dibêjim "ev algorîtma xwedan tevliheviyek O(some_function()) ye", ev tê vê wateyê ku algorîtma ji hin_fonksiyonên (a_certain_amount_of_data) operasyonên hewce dike ku hejmareke diyarkirî ya daneyê bişopîne.

Bi vî awayî Ew ne mîqdara daneyê ye ku girîng e **, wekî din ** bi zêdebûna hêjmara daneyê re hejmara operasyonan çawa zêde dibe. Tevliheviya demê hejmareke rastîn a operasyonan peyda nake, lê rêyek baş e ku meriv dema darvekirinê texmîn bike.

Di vê grafîkê de hûn dikarin jimara operasyonan beramberî mêjera daneya têketinê ji bo cûrbecûr tevliheviyên dema algorîtmayê bibînin. Min pîvanek logarîtmîkî bikar anî da ku wan nîşan bide. Bi gotineke din, mîqdara daneyan zû ji 1 ber 1 milyar zêde dibe. Em dikarin bibînin ku:

O(1) an jî tevlîheviya domdar sabît dimîne (ku nebe wê jê re tevliheviya domdar neyê gotin).
O(rojname(n)) bi mîlyaran daneyan jî kêm dimîne.
Zehmetiya herî xirab - O(n2), ku hejmara operasyonan bi lez mezin dibe.
Du komplîkasyonên din jî bi lez zêde dibin.

wergerandî

Digel hejmareke piçûk a daneyê, cûdahiya di navbera O (1) û O (n2) de nehêl e. Mînakî, em bibêjin algorîtmayek we heye ku hewce dike ku 2000 hêmanan pêvajoyê bike.

Algorîtmaya O (1) dê 1 operasyonê bide we
Algorîtmaya O(log(n)) dê ji we re 7 operasyonan biha bike
Algorîtmaya O(n) dê ji we re 2 operasyonan xerc bike
Algorîtmaya O(n*log(n)) dê ji we re 14 operasiyon lêçû
Algorîtmaya O(n2) dê ji we re 4 operasiyon mesref bike

Cûdahiya di navbera O(1) û O(n2) de mezin xuya dike (4 mîlyon operasyon) lê hûn ê herî zêde 2 ms winda bikin, tenê wextê ku hûn çavên xwe bibiriqînin. Bi rastî, pêvajoyên nûjen dikarin pêvajoyê bikin di çirkeyê de bi sedan mîlyon operasyon. Ji ber vê yekê di gelek projeyên IT-ê de performans û optimîzasyon ne pirsgirêk e.

Wekî ku min got, hîn jî girîng e ku meriv vê têgehê dema ku bi daneyên pir mezin re dixebitin zanibin. Ger vê carê pêdivî ye ku algorîtma 1 hêmanan pêvajoyê bike (ku ji bo databasek ne ew qas e):

Algorîtmaya O (1) dê 1 operasyonê bide we
Algorîtmaya O(log(n)) dê ji we re 14 operasyonan biha bike
Algorîtmaya O(n) dê ji we re 1 operasyonan lêçûn
Algorîtmaya O(n*log(n)) dê ji we re 14 operasyonan xerc bike.
Algorîtmaya O(n2) dê ji we re 1 operasiyon mesref bike.

Min matematîkî nekiriye, lê ez dibêm ku bi algorîtmaya O(n2) wextê we heye ku hûn qehweyek vexwin (heta du jî!). Ger hûn 0-yek din li hêjmara daneyê zêde bikin, dê wextê we hebe ku hûn xewê bikin.

Em kûrtir biçin

Ji bo referansa

Lêgerînek maseya hash a baş di O(1) de hêmanek dibîne.
Lêgerîna dara baş-hevseng di O(log(n)) de encam dide.
Lêgerîna arrayek di O(n) de encam dide.
Algorîtmayên cûrbecûr yên çêtirîn xwedan tevliheviya O(n*log(n)) ne.
Algorîtmayek rêzkirina xirab O(n2) tevlihev e.

Nîşe: Di beşên jêrîn de em ê van algorîtmayan û avahiyên daneyê bibînin.

Gelek celebên tevliheviya dema algorîtmayê hene:

senaryoya doza navîn
senaryoya herî baş
û senaryoya herî xirab

Tevliheviya demê bi gelemperî senaryoya herî xirab e.

Min tenê behsa tevliheviya demê ya algorîtmayê kir, lê tevlihevî di heman demê de jî derbas dibe:

mezaxtina bîra algorîtmayê
algorîtmaya xerckirina I/O ya dîskê

Bê guman, tevliheviyên ji n2 xirabtir hene, mînakî:

n4: ev tirsnak e! Hin algorîtmayên navborî xwedî vê tevliheviyê ne.
3n: ev hê xerabtir e! Yek ji algorîtmayên ku em ê di nîvê vê gotarê de bibînin ev tevlihevî heye (û ew bi rastî di gelek databasan de tê bikar anîn).
n faktorî: hûn ê çu carî encamên xwe bi daneya piçûk jî negirin.
nn: Ger hûn bi vê tevliheviyê re rû bi rû bimînin, divê hûn ji xwe bipirsin gelo ev bi rastî qada çalakiya we ye…

Nîşe: Min pênaseya rastîn a binavkirina O ya mezin neda we, tenê ramanek. Hûn dikarin vê gotarê li ser bixwînin Wikipedia ji bo pênaseya rastîn (asîmptotîk).

MergeSort

Dema ku hûn hewce ne ku berhevokek birêkûpêk bikin hûn çi dikin? Çi? Hûn gazî fonksiyona sort() dikin... Baş e, bersivek baş e... Lê ji bo databasek, divê hûn fam bikin ka ev fonksiyona sort() çawa dixebite.

Gelek algorîtmayên cûrbecûr yên baş hene, ji ber vê yekê ez ê li ser ya herî girîng bisekinim: merge sort. Dibe ku hûn fêm nekin ka çima dabeşkirina daneyan niha bikêr e, lê divê hûn li dû beşa xweşbînkirina pirsê bigerin. Wekî din, têgihîştina celebê hevgirtinê dê ji me re bibe alîkar ku paşê operasyona tevlêbûna databasa hevpar a ku jê re tê gotin fam bikin bihevkelyan bihevgirêdan (komela yekbûnê).

Bihevkelyan

Mîna gelek algorîtmayên bikêr, rêzkirina hevgirtinê xwe dispêre hîleyekê: berhevkirina 2 rêzikên rêzkirî yên mezinahiya N/2 di nav rêzek rêzkirî ya N-hêman de tenê N operasyonê lê dike. Ji vê operasyonê re hevgirtin tê gotin.

Ka em bibînin ka ev tê çi wateyê bi mînakek hêsan:

Ev jimar nîşan dide ku ji bo avakirina rêzika dawîn a 8-hêman, hûn tenê hewce ne ku carekê li ser 2 rêzikên 4-hêmanan dubare bikin. Ji ber ku her du rêzikên 4-hêman berê hatine rêz kirin:

1) hûn her du hêmanên heyî di du rêzan de didin ber hev (li destpêkê niha = yekem)
2) dûv re ya herî piçûk hildin ku wê têxin nav rêzek 8 hêmanan
3) û di rêza ku we hêmana herî piçûk girtiye de biçin hêmana din
û 1,2,3 dubare bikin heya ku hûn bigihîjin hêmana paşîn a yek ji rêzan.
Dûv re hûn hêmanên mayî yên rêzika din digirin da ku wan têxin nav rêzek 8 hêmanan.

Ev kar dike ji ber ku her du rêzikên 4-hêman têne rêz kirin û ji ber vê yekê hûn ne hewce ne ku hûn di wan rêzan de "vegerin".

Naha ku em hîleyê fam dikin, li vir pseudokoda min a yekbûnê ye:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

Merge sort pirsgirêkek di nav pirsgirêkên piçûktir de vediqetîne û dûv re encamên pirsgirêkên piçûktir dibîne da ku encama pirsgirêka orîjînal bigire (têbînî: ji vî celebê algorîtmayê re tê gotin dabeş bike û bidest bixe). Heke hûn vê algorîtmê fam nakin, xem nekin; Cara ewil min ew dît min fêm nekir. Ger ew dikare ji we re bibe alîkar, ez vê algorîtmayê wekî algorîtmayek du qonax dibînim:

Qonaxa dabeşkirinê, ku li wê derê rêzik li rêzikên piçûktir tê dabeş kirin
Qonaxa birêkûpêkkirinê ew e ku rêzikên piçûk têne berhev kirin (bikaranîna yekîtiyê) da ku komek mezin ava bikin.

Qonaxa dabeşkirinê

Di qonaxa dabeşkirinê de, rêzik di 3 gavan de li rêzikên yekbûyî tê dabeş kirin. Hejmara fermî ya gavan log(N) ye (ji ber ku N=8, log(N) = 3).

Ez çawa vê yekê dizanim?

Ez genî me! Bi gotinek - matematîk. Fikir ev e ku her gav mezinahiya array orjînal bi 2-an dabeş dike. Hejmara gavan ew çend caran e ku hûn dikarin rêzika orîjînal bikin du. Ev pênaseya rast a logarîtmê ye (bingeh 2).

Qonaxa sorkirinê

Di qonaxa dabeşkirinê de, hûn bi rêzikên yekbûyî (yek-hêman) dest pê dikin. Di her gavê de hûn gelek operasyonên yekbûnê bicîh dikin û lêçûna giştî N = 8 operasyon e:

Di qonaxa yekem de we 4 hevgirtin hene ku her yek 2 operasyonan lê didin
Di gava duyemîn de we 2 hevgirtin hene ku her yek 4 operasyonan lê didin
Di gava sêyemîn de we 1 hevgirtin heye ku 8 operasyonan lê dike

Ji ber ku gavên têketinê (N) hene, lêçûna giştî N * log (N) operasyonên.

Avantajên cûrbecûr merge

Çima ev algorîtma ewqas bi hêz e?

Bo:

Hûn dikarin wê biguhezînin da ku şopa bîranînê kêm bikin da ku hûn rêzikên nû neafirînin lê rasterast rêzika têketinê biguhezînin.

Nîşe: ji vê cureyê algorîtmê re tê gotin in-cîh (Bêyî bîranîna zêde dabeşkirin).

Hûn dikarin wê biguhezînin da ku di heman demê de cîhê dîskê û mîqdarek piçûk a bîranînê bikar bînin bêyî ku giraniya I/O ya dîskê zêde bike. Fikir ev e ku meriv tenê wan beşên ku niha têne hilanîn di bîranînê de bar bike. Dema ku hûn hewce ne ku tabloyek pir-gigabyte bi tenê tamponek bîranîna 100-megabyte veqetînin ev girîng e.

Nîşe: ji vê cureyê algorîtmê re tê gotin dabeşkirina derveyî.

Hûn dikarin wê biguhezînin da ku li ser gelek pêvajoyên / mijarên / pêşkêşkeran bixebitin.

Mînakî, cûrbecûr hevgirtina belavbûyî yek ji hêmanên sereke ye Hadoop (ku di daneyên mezin de avahiyek e).

Ev algorîtma dikare rê li zêr veguherîne (bi rastî!).

Ev algorîtmaya dabeşkirinê di piraniya databasan de (heke ne hemî) tê bikar anîn, lê ew ne tenê ye. Heke hûn dixwazin bêtir zanibin, hûn dikarin vê bixwînin xebata lêkolînê, ku li ser erênî û neyînîyên algorîtmayên dabeşkirina databasa hevpar nîqaş dike.

Tabloya Array, Dar û Haş

Naha ku em ramana tevlihevî û birêkûpêkkirina demê fam dikin, divê ez ji we re li ser 3 strukturên daneyê bibêjim. Ev girîng e ji ber ku ew bingeha databasên nûjen in. Ez ê têgehê jî bidim nasîn index database.

Rêzî

Rêzeya du-dimensî avaniya daneyê ya herî hêsan e. Tabloyek dikare wekî rêzek were fikirîn. Bo nimûne:

Ev rêzika 2-alî tabloyek bi rêz û stûnan e:

Her rêzek hebûnekê temsîl dike
Stûn taybetiyên ku hebûnê rave dikin hilîne.
Her stûn daneyên cûreyek taybetî (hejmar, rêz, tarîx...) hilîne.

Ev ji bo hilanîn û dîtina daneyan hêsan e, di heman demê de, gava ku hûn hewce ne ku nirxek taybetî bibînin, ev ne maqûl e.

Mînakî, heke we xwest ku hûn hemî xortên ku li Keyaniya Yekbûyî dixebitin bibînin, hûn hewce ne ku li her rêzê binihêrin da ku hûn diyar bikin ka ew rêz girêdayî Keyaniya Yekbûyî ye. Ew ê ji we re N danûstendinan bideko N - hejmara rêzan, ku ne xirab e, lê gelo rêyek zûtir heye? Êdî dem hatiye ku em bi daran re bên naskirin.

Nîşe: Pir databasên nûjen ji bo hilanîna tabloyên bi bandor rêzikên dirêjkirî peyda dikin: tabloyên birêkûpêk û tabloyên birêkûpêkkirî. Lê ev pirsgirêka ku di komek stûnan de zû peydakirina şertek taybetî nayê guheztin.

Dara databasê û index

Dara lêgerînê ya binary darek binary e ku xwedan taybetmendiyek taybetî ye, divê mifteya her girêk ev be:

ji hemû kilîtên ku di binê dara çepê de hatine hilanîn mezintir e
kêmtir ji hemû bişkokên ku di bindara rastê de hatine hilanîn

Ka em bibînin ka ev bi dîtbarî tê çi wateyê

Idea

Di vê darê de N = 15 hêman hene. Ka em bibêjin ez li 208 digerim:

Ez ji koka ku mifteya wê 136 e dest pê dikim. Ji sala 136<208 de, ez li binê dara rastê ya girêka 136-ê dinêrim.
398>208 ji ber vê yekê ez li binê dara çepê ya girêka 398 digerim
250>208 ji ber vê yekê ez li binê dara çepê ya girêka 250 digerim
200<208, ji ber vê yekê ez li binê dara rastê ya girêka 200-ê dinêrim. nirx nîne (ji ber ku heke hebe, ew ê di binê dara rastê 200 de be).

Niha em bêjin ez li 40 digerim

Ez ji koka ku mifteya wê 136 e dest pê dikim. Ji 136 > 40, ez li binê dara çepê ya girêka 136-ê dinêrim.
80 > 40, ji ber vê yekê ez li binê dara çepê ya node 80 digerim
40 = 40, nodek heye. Ez nasnameya rêzê di hundurê girêkê de vedigirim (di wêneyê de nayê xuyang kirin) û li tabloyê li nasnameya rêza diyar digerim.
Nasîna nasnameya rêzê dihêle ku ez bi rastî bizanibim ku dane li ku derê tabloyê ne, ji ber vê yekê ez dikarim wê tavilê bistînim.

Di dawiyê de, her du lêgerîn dê ji min re hejmara astên hundurê darê mesref bikin. Ger hûn beşê li ser cûrbecûrhevkirinê bi baldarî bixwînin, divê hûn bibînin ku astên têketin (N) hene. Derket holê, lêçûna lêçûnên lêgerînê (N), xerab nîne!

Ka em vegerin ser pirsgirêka xwe

Lê ev pir razber e, ji ber vê yekê em vegerin ser pirsgirêka xwe. Li şûna hejmareke sade, rêzek ku di tabloya berê de welatê kesekî temsîl dike, bifikirin. Ka em bibêjin darek we heye ku tê de qada "welat" (stûna 3) ya tabloyê heye:

Heke hûn dixwazin bizanibin kî li Brîtanyayê dixebite
tu li darê dinêrî ku girêka ku Brîtanyaya Mezin temsîl dike bistînî
di hundurê "UKnode" de hûn ê cîhê tomarên karkerên Keyaniya Yekbûyî bibînin.

Heke hûn rasterast array bikar bînin dê ev lêgerîn li şûna operasyonên N-yê log (N) xerc bike. Ya ku we tenê pêşkêş kir bû index database.

Hûn dikarin ji bo her komek qadan dara nîşanekê ava bikin (xêz, hejmar, 2 rêz, hejmar û rêz, tarîx...) heya ku fonksiyonek we hebe ku hûn bişkokan bidin ber hev (ango komên zeviyê) da ku hûn bikarin saz bikin. siparîş di nav keys (ku ji bo her cûreyên bingehîn di databasê de ye).

B + TreeIndex

Dema ku ev dar ji bo bidestxistina nirxek taybetî baş dixebite, gava ku hûn hewce ne pirsgirêkek MEZIN heye di navbera du nirxan de gelek hêmanan bistînin. Ev ê mesrefa O(N) bike ji ber ku hûn neçar in ku li her girêkek darê binihêrin û kontrol bikin ka ew di navbera van her du nirxan de ye (mînak. bi gerîdeyek rêzkirî ya darê). Digel vê yekê, ev operasyon ne dostê dîskê I/O ye ji ber ku hûn neçar in ku tevahiya darê bixwînin. Divê em rêyek ji bo pêkanîna bi bandor bibînin daxwaza range. Ji bo çareserkirina vê pirsgirêkê, databasên nûjen guhertoyek guhezbar a dara berê ya bi navê B + Tree bikar tînin. Di dara B + Darê de:

tenê girêkên herî jêrîn (pel) agahî hilanîn (cihê rêzan di tabloya têkildar de)
girêkên mayî li vir in ji bo rêgirtinê ber bi girêka rast di dema lêgerînê de.

Wekî ku hûn dikarin bibînin, li vir (du caran) bêtir girêk hene. Bi rastî, we girêkên din hene, "girêkên biryarê", ku dê ji we re bibe alîkar ku hûn girêka rast bibînin (ku cîhê rêzan di tabloya têkildar de hilîne). Lê tevliheviya lêgerînê hîn jî O(log(N)) ye (tenê astek din heye). Cûdahiya mezin ew e girêkên di asta jêrîn de bi paşgirên xwe ve girêdayî ne.

Bi vê B + Darê, heke hûn li nirxên di navbera 40 û 100 de digerin:

Hûn tenê hewce ne ku li 40-ê (an nirxa herî nêzîk a piştî 40-ê heke 40 tune) bigerin mîna ku we bi dara berê re kir.
Dûv re 40 mîrasgirên bi karanîna girêdanên mîrasgirên rasterast berhev bikin heya ku hûn bigihîjin 100.

Ka em bibêjin hûn M-yê peykeran dibînin û darê N girêk hene. Dîtina girêkek taybetî ya lêçûnek têketinê (N) mîna dara berê. Lê gava ku hûn vê nodê bi dest bixin, hûn ê di operasyonên M-yê de bi referansên li dûvên wan de serfirazên M-yê bistînin. Mesrefa vê lêgerînê tenê M+log(N) operasyonên li gorî N operasyonên li ser dara berê. Wekî din, hûn ne hewce ne ku hûn dara tevahî bixwînin (tenê girêkên M + log (N)), ku tê vê wateyê ku kêm karanîna dîskê ye. Ger M piçûk be (mînak 200 rêz) û N mezin be (1 rêz), dê cûdahiyek MEZIN hebe.

Lê li vir (dîsa!) pirsgirêkên nû hene. Ger hûn rêzek di databasê de zêde bikin an jêbikin (û ji ber vê yekê di navnîşana B + Tree ya têkildar de):

divê hûn rêzê di navbera girêkên di hundurê B+Dreyekê de biparêzin, wekî din hûn ê nikaribin girêkan di hundurê darek nesûrtî de bibînin.
divê hûn di B+Tree de herî kêm hejmara astên gengaz biparêzin, wekî din tevliheviya dema O(log(N)) dibe O(N).

Bi gotinek din, B + Tree divê xwe-rêkûpêk û hevseng be. Xwezî, ev bi operasyonên jêbirin û têxistina biaqil gengaz e. Lê ev bi lêçûnek tê: lêçûn û jêbirinên di dara B+ de lêçûn O(log(N)). Ji ber vê yekê hinekan ji we ev bihîstiye bikaranîna pir indexan ne fikrek baş e. Bicî, hûn hêdî hêdî dikin ku rêzek di tabloyekê de têxin/nûvekirin/ jêbirinji ber ku databas hewce dike ku ji bo her indexek bi karekî giranbiha O(log(N)) indexên tabloyê nûve bike. Digel vê yekê, lêzêdekirina îndeksan tê wateya bargiraniya xebatê gerînendeyê danûstendinê (dê di dawiya gotarê de bête diyar kirin).

Ji bo bêtir agahdarî, hûn dikarin gotara Wîkîpediya li ser bibînin B+Dar. Ger hûn mînakek bicîhkirina B + Tree di databasê de dixwazin, lê binêrin vê gotarê и vê gotarê ji pêşdebirek pêşeng MySQL. Ew her du jî balê dikişînin ser ka InnoDB (motorê MySQL) çawa indexan dike.

Nîşe: Xwendevanek ji min re got ku, ji ber xweşbîniyên nizm, divê dara B+ bi tevahî hevseng be.

Hashtable

Struktura meya daneya girîng a paşîn tabloya hash e. Dema ku hûn dixwazin zû li nirxan bigerin ev pir bikêr e. Wekî din, têgihîştina tabloyek hash dê ji me re bibe alîkar ku paşê operasyonek tevlêbûna databasa hevpar a ku jê re tê gotin tevlêbûna hash ( hash tevlî bibin). Ev avahiya daneyê jî ji hêla databasê ve tê bikar anîn da ku hin tiştên hundurîn hilîne (mînak. sifrê lock an hewza tampon, em ê van herdu têgehan paşê bibînin).

Tabloyek hash avahiyek daneyê ye ku zû hêmanek bi kilîta xwe dibîne. Ji bo avakirina tabloyek hash divê hûn diyar bikin:

en.wiktionary.org ключ (Noun) ji bo hêmanên xwe
fonksiyona hash ji bo keys. Hêsanên mifteyê yên hesabkirî cîhê hêmanan dide (navê beşên ).
fonksiyona ji bo berhevdana keys. Gava ku we beşa rast dît, divê hûn bi karanîna vê berhevdanê de hêmana ku hûn lê digerin bibînin.

Mînakek hêsan

Werin em mînakek zelal bistînin:

Ev tabloya hash 10 beşan hene. Ji ber ku ez tembel im, min tenê 5 beşan wêne kişand, lê ez dizanim ku hûn jîr î, ji ber vê yekê ez ê bihêlim ku hûn 5ên din bi serê xwe wêne bikin. Min modulek fonksiyonek hash 10 ya mifteyê bikar anî. Bi gotinek din, ez tenê jimareya paşîn a mifteya hêmanê hildibijêrim da ku beşa wê bibînim:

heke reqema dawî 0 be, hêman dikeve beşa 0,
heke reqema dawî 1 be, hêman dikeve beşa 1,
heke reqema dawî 2 be, hêman dikeve qada 2,
...

Fonksiyona berhevdanê ya ku min bikar anî bi tenê wekheviya di navbera du jimaran de ye.

Ka em bibêjin ku hûn dixwazin hêmana 78-ê bistînin:

Tabloya hash ji bo 78, ku 8 e, koda hash hesab dike.
Tabloya hash li beşa 8-ê dinêre, û yekem hêmana ku ew dibîne 78 e.
Ew babete 78 ji we re vedigerîne
Lêçûna lêgerînê tenê 2 operasyonan e (yek ji bo hesabkirina nirxa hash û ya din ji bo lêgerîna hêmanê di hundurê beşê de).

Naha em bibêjin ku hûn dixwazin element 59 bistînin:

Tabloya hash ji bo 59, ku 9 e, koda hash hesab dike.
Tabloya haş di beşa 9. de digere, hêmana yekem a ku hatiye dîtin 99 e. Ji ber ku 99!=59, hêmana 99 ne hêmanek derbasdar e.
Bi heman mantiqê hêmana duyemîn (9), ya sêyemîn (79), ..., ya dawî (29) têne girtin.
Element nehat dîtin.
Lêgerîn 7 operasyon lê hat kirin.

Fonksiyona hash baş

Wekî ku hûn dikarin bibînin, li gorî nirxa ku hûn lê digerin, lêçûn ne yek e!

Ger ez nuha fonksiyona hash-ê modula 1 ya mifteyê biguhezînim (ango, 000 reqemên paşîn bigirim), lêgera duyemîn tenê 000 operasyonê lê dike ji ber ku di beşa 6 de hêmanek tune. Pirsgirêka rastîn ev e ku meriv fonksiyonek hash a baş bibîne ku dê kelûpelên ku hejmareke pir piçûk a hêmanan vedihewîne biafirîne.

Di mînaka min de, dîtina fonksiyonek hash a baş hêsan e. Lê ev mînakek hêsan e, dîtina fonksiyonek hash a baş dijwartir e dema ku kilît e:

string (mînak - paşnav)
2 rêz (mînak - paşnav û paşnav)
2 rêz û dîrok (mînak - paşnav, paşnav û dîroka jidayikbûnê)
...

Bi fonksiyonek hash a baş, lêçûnên tabloya hash O (1).

Array vs maseya hash

Çima array bikar neynin?

Hmm, pirsek baş.

Tabloya hash dikare bibe qismî li bîra barkirin, û beşên mayî dikarin li ser dîskê bimînin.
Bi arrayek re divê hûn cîhê hevgirtî di bîranînê de bikar bînin. Ger hûn tabloyek mezin bar dikin pir zehmet e ku meriv cîhê domdar têra xwe bibîne.
Ji bo tabloyek hash, hûn dikarin mifteya ku hûn dixwazin hilbijêrin (mînak, paşnavê welat û kesê).

Ji bo bêtir agahdarî, hûn dikarin gotara li ser bixwînin JavaHashmap, ku pêkanîna bikêrhatî ya tabloyek hash e; hûn ne hewce ne ku Java-yê fêm bikin da ku hûn têgînên ku di vê gotarê de têne destnîşan kirin fam bikin.

Source: www.habr.com

Daneyên Têkilî Çawa Kar Dikin (Beş 1)