Hey Habr! M na-egosi gị ntụgharị asụsụ nke akụkọ ahụ
"Kedu ka nchekwa data mmekọrịta si arụ ọrụ".

Mgbe a bịara na ọdụ data mmekọrịta enweghị m ike ịnyere aka kama iche na ọ dị ihe na-efu. A na-eji ha eme ihe n'ebe niile. Enwere ọtụtụ ọdụ data dị iche iche dị, site na SQLite obere na bara uru ruo Teradata dị ike. Mana enwere naanị akụkọ ole na ole na-akọwa ka nchekwa data si arụ ọrụ. Ị nwere ike ịchọ onwe gị site na iji "howdoesarelationaldatabasework" ka ịhụ nsonaazụ ole na ole enwere. Ọzọkwa, isiokwu ndị a dị mkpụmkpụ. Ọ bụrụ na ị na-achọ teknụzụ buzzy kacha ọhụrụ (BigData, NoSQL ma ọ bụ Javascript), ị ga-ahụ akụkọ ndị ọzọ miri emi na-akọwa etu ha si arụ ọrụ.

Ebe nchekwa data mmekọrịta ọ̀ merela agadi na ọ na-agwụkwa ike ịkọwa ya na mpụga nke ọmụmụ mahadum, akwụkwọ nyocha na akwụkwọ?

Dịka onye nrụpụta, akpọrọ m asị iji ihe m na-aghọtaghị. Ma ọ bụrụ na ejirila ọdụ data ihe karịrị afọ 40, a ga-enwerịrị ihe kpatara ya. N'ime afọ ndị gafeworonụ, ejirila m ọtụtụ narị awa ghọta n'ezie igbe ojii ndị a dị ịtụnanya nke m na-eji kwa ụbọchị. Databases mmekọrịta na-akpali nnọọ mmasị n'ihi na ha dabere na echiche bara uru na reusable. Ọ bụrụ na ị nwere mmasị ịghọta nchekwa data, mana enwebeghị oge ma ọ bụ ọchịchọ ịbanye n'ime isiokwu a sara mbara, ị ga-anụ ụtọ akụkọ a.

Ọ bụ ezie na aha isiokwu a doro anya, ebumnuche nke isiokwu a abụghị ịghọta ka esi eji nchekwa data. N'ihi ya, ị ga-amarịrị ka esi ede arịrịọ njikọ dị mfe na ajụjụ ndị bụ isi RAW; ma ọ bụghị na ị nwere ike ghara ịghọta isiokwu a. Nke ahụ bụ naanị ihe ị kwesịrị ịma, m ga-akọwa nke ọzọ.

Aga m ebido na ụfọdụ ntọala sayensị kọmputa, dị ka mgbagwoju oge nke algọridim (BigO). Amaara m na ụfọdụ n'ime unu kpọrọ echiche a asị, mana na-enweghị ya ị gaghị enwe ike ịghọta mgbagwoju anya dị n'ime nchekwa data. Ebe ọ bụ na nke a bụ nnukwu isiokwu, M ga-elekwasị anya ihe m chere dị mkpa: otú nchekwa data usoro SQL ajuju. Aga m ewebata isi nchekwa data echichenke mere na na njedebe nke isiokwu ị nwere echiche nke ihe na-eme n'okpuru mkpuchi.

Ebe ọ bụ na nke a bụ isiokwu dị ogologo na nka nke na-agụnye ọtụtụ algọridim na usoro data, wepụta oge iji gụọ ya. Ụfọdụ echiche nwere ike isi ike nghọta; ị nwere ike ịwụpụ ha ma nweta echiche izugbe.

Maka ndị maara nke ọma n'etiti gị, ekewara akụkọ a na akụkụ atọ:

• Nchịkọta nke akụrụngwa nchekwa data dị ala na ọkwa dị elu
• Nchịkọta nke Usoro njikarịcha ajụjụ
• Nchịkọta nke njikwa azụmahịa yana njikwa ọdọ mmiri

Back to Basics

Ọtụtụ afọ gara aga (na ụyọkọ kpakpando dị anya, dị anya ...), ndị mmepe kwesịrị ịma kpọmkwem ọnụọgụ ọrụ ha na-etinye koodu. Ha maara algọridim ha na usoro data ha site n'obi n'ihi na ha enweghị ike ịlafu CPU na ebe nchekwa nke kọmputa ha na-adịghị ngwa ngwa.

N'akụkụ a, m ga-echetara gị ụfọdụ n'ime echiche ndị a dịka ha dị mkpa iji ghọta nchekwa data. M ga-ewebatakwa echiche nchekwa data index.

O(1) vs O(n2)

N'oge a, ọtụtụ ndị mmepe anaghị eche banyere oge mgbagwoju anya nke algọridim ... na ha ziri ezi!

Ma mgbe ị na-emeso ọtụtụ data (Anaghị m ekwu puku kwuru puku) ma ọ bụ ọ bụrụ na ị na-agbasi mbọ ike na milliseconds, ọ ga-adị mkpa ịghọta echiche a. Na dị ka ị nwere ike iche n'echiche, ọdụ data ga-emeso ọnọdụ abụọ ahụ! Agaghị m eme ka ị na-etinye oge karịa ka ọ dị mkpa iji nweta isi okwu ahụ. Nke a ga-enyere anyị aka ịghọta echiche nke njikarịcha dabere na ọnụ ahịa ma emechaa (-eri dabeere njikarịcha).

Echiche

Ihe mgbagwoju anya oge nke algọridim A na-eji hụ ogologo oge ọ ga-ewe iji mezuo algọridim maka ọnụọgụ data enyere. Iji kọwa mgbagwoju anya a, anyị na-eji nnukwu ọkwa mgbakọ na mwepụ O. A na-eji akara ngosi a na-arụ ọrụ na-akọwa ọrụ ole algọridim chọrọ maka ọnụọgụ ntinye.

Dịka ọmụmaatụ, mgbe m kwuru "algọridim a nwere mgbagwoju anya O(some_function())", ọ pụtara na algọridim chọrọ ọrụ ụfọdụ_function(a_certain_amount_of_data) iji hazie ụfọdụ data.

N'ihi ya Ọ bụghị ọnụọgụ data ka ọ dị mkpa ***, ma ọ bụghị ya ** ka ọnụọgụ ọrụ na-abawanye site na ịba ụba data. Mgbagwoju anya oge anaghị enye ọnụọgụ ọrụ kpọmkwem, mana ọ bụ ụzọ dị mma isi tụọ oge igbu.

Na eserese a, ị nwere ike ịhụ ọnụọgụ ọrụ yana ọnụọgụ data ntinye maka ụdị mgbagwoju anya oge algorithm dị iche iche. Eji m akara logarithmic gosi ha. N'ikwu ya n'ụzọ ọzọ, ọnụọgụ data na-abawanye ngwa ngwa site na ijeri 1 ruo 1. Anyị nwere ike ịhụ na:

• O(1) ma ọ bụ mgbagwoju anya na-anọgide na-adịgide adịgide (ma ọ bụghị ya, a gaghị akpọ ya mgbagwoju anya mgbe niile).
• O(abanye(n)) ka dị ala ọbụlagodi na ijeri data.
• Ihe isi ike kacha njọ - O(n2), ebe ọnụọgụ ọrụ na-eto ngwa ngwa.
• Nsogbu abụọ ndị ọzọ na-abawanye ngwa ngwa.

atụ

Site na obere data, ọdịiche dị n'etiti O (1) na O (n2) bụ ihe na-adịghị mma. Dịka ọmụmaatụ, ka anyị kwuo na ị nwere algọridim nke kwesịrị ịhazi ihe 2000.

• Algọridim O(1) ga-efu gị otu ọrụ
• O(log(n)) algọridim ga-eri gị ọrụ 7
• Algọridim O(n) ga-eri gị ọrụ 2
• O(n*log(n)) algọridim ga-eri gị ọrụ 14
• Algọridim O(n2) ga-eri gị ọrụ 4

Ọdịiche dị n'etiti O (1) na O (n2) dị ka nnukwu (ọrụ nde 4) mana ị ga-atụfu oke nke 2 ms, naanị oge iji gbuchapụ anya gị. N'ezie, oge a processors nwere ike hazie ọtụtụ narị nde ọrụ kwa sekọnd. Nke a bụ ya mere ịrụ ọrụ na njikarịcha abụghị okwu n'ọtụtụ ọrụ IT.

Dị ka m kwuru, ọ ka dị mkpa ịmara echiche a mgbe ị na-arụ ọrụ na nnukwu data. Ọ bụrụ na oge a, algọridim ga-edozi ihe 1 (nke na-abụghị nke ukwuu maka nchekwa data):

• Algọridim O(1) ga-efu gị otu ọrụ
• O(log(n)) algọridim ga-eri gị ọrụ 14
• Algọridim O(n) ga-eri gị ọrụ 1
• O(n*log(n)) algọridim ga-eri gị ọrụ 14
• Algọridim O(n2) ga-eri gị ọrụ 1

Emebeghị m mgbakọ na mwepụ, mana m ga-ekwu na na O (n2) algọridim ị nwere oge ịṅụ kọfị (ọbụlagodi abụọ!). Ọ bụrụ na ị gbakwunye 0 ọzọ na olu data, ị ga-enwe oge iji hie ụra.

Ka anyị gakwuo omimi

Maka ama aka:

• Nchọcha tebulu hash dị mma na-achọta ihe dị na O(1).
• Ịchọ osisi dabara nke ọma na-arụpụta ihe na O(log(n)).
• Ịchọ n'usoro na-arụpụta nsonaazụ na O(n).
• Usoro nhazi kacha mma nwere mgbagwoju anya O(n*log(n)).
• Ajọ nhazi algọridim nwere mgbagwoju anya O(n2).

Mara: N'akụkụ ndị a, anyị ga-ahụ algọridim ndị a na usoro data.

E nwere ọtụtụ ụdị nke mgbagwoju oge algọridim:

• nkezi ikpe dịruru ná njọ
• ihe kacha mma
• na nke kacha njọ

Mgbagwoju anya oge na-abụkarị ọnọdụ kacha njọ.

Naanị m na-ekwu maka mgbagwoju oge nke algọridim, mana mgbagwoju anya na-emetụtakwa:

• ebe nchekwa oriri nke algọridim
• disk I/O oriri algọridim

N'ezie, enwere nsogbu dị njọ karịa n2, dịka ọmụmaatụ:

• n4: ihe a di egwu! Ụfọdụ algọridim ndị a kpọtụrụ aha nwere mgbagwoju anya a.
• 3n: nke a ka njọ! Otu n'ime algọridim anyị ga-ahụ n'etiti isiokwu a nwere mgbagwoju anya a (ma na-eji ya n'ezie na ọtụtụ ọdụ data).
• factorial n: ị gaghị enweta nsonaazụ gị ọbụlagodi na obere data.
• nn: Ọ bụrụ na ị zutere mgbagwoju anya a, ị kwesịrị ịjụ onwe gị ma nke a bụ n'ezie ubi ọrụ gị ...

Mara: E nyeghị m gị nkọwapụta nke nnukwu aha O, naanị otu echiche. Ị nwere ike ịgụ akụkọ a na Wikipedia maka nkọwa n'ezie (asymptotic).

JikotaSort

Kedu ihe ị ga-eme mgbe ịchọrọ ịhazi mkpokọta? Kedu? Ị na-akpọ ụdị () ọrụ ... Ọ dị mma, azịza dị mma ... Mana maka nchekwa data, ị ga-aghọta ka ụdị ọrụ a si arụ ọrụ.

Enwere ọtụtụ algorithms nhazi dị mma, yabụ m ga-elekwasị anya na nke kachasị mkpa: jikota ụdị. O nwere ike ị gaghị aghọta ihe kpatara nhazi data ji baa uru ugbu a, mana ị ga-emecha akụkụ njikarịcha ajụjụ. Ọzọkwa, ịghọta ụdị nchikota ga-enyere anyị aka ka anyị mechaa ghọta njikọ njikọ nchekwa data nkịtị a na-akpọ jikota iso (mmekọrịta njikọ).

Jikota

Dị ka ọtụtụ algọridim bara uru, ụdị ngwakọta na-adabere na aghụghọ: ijikọta ụdị nha nha N/2 2 n'usoro N-emebere nhazi na-efu naanị ọrụ N. A na-akpọ ọrụ a merging.

Ka anyị lee ihe nke a pụtara n'iji atụ dị mfe:

Ọnụọgụ a na-egosi na iji wuo usoro nhazi nke 8 nke ikpeazụ, naanị ị ga-emerịrị otu ugboro n'usoro ihe omume 2 4. Ebe ọ bụ na ahazilarị usoro ihe omume anọ:

• 1) ị na-atụnyere ihe abụọ dị ugbu a n'usoro abụọ (na mmalite nke ugbu a = nke mbụ)
• 2) wee were nke kacha nta tinye ya n'usoro ihe 8
• 3) wee gaa na ihe na-esote na nhazi ebe ị were ihe kacha nta
• ma kwugharịa 1,2,3 ruo mgbe ị ruru ihe ikpeazụ nke otu n'ime usoro.
• Mgbe ahụ, ị ​​ga-ewere ihe ndị fọdụrụ na nhazi nke ọzọ iji tinye ha n'usoro ihe 8.

Nke a na-arụ ọrụ n'ihi na a na-ahazi ihe abụọ 4-element arrays na n'ihi ya ị gaghị "laghachi azụ" n'usoro ndị ahụ.

Ugbu a anyị ghọtara aghụghọ ahụ, nke a bụ pseudocode m maka ijikọ:

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;

Ngwakọta ụdị na-agbaji nsogbu n'ime obere nsogbu wee chọta nsonaazụ nke obere nsogbu iji nweta nsonaazụ nke mbụ nsogbu (mara: ụdị algọridim a na-akpọ nkewa na imeri). Ọ bụrụ na ị ghọtaghị algọridim a, echegbula; Aghọtaghị m ya oge mbụ m hụrụ ya. Ọ bụrụ na ọ nwere ike inyere gị aka, ana m ahụ algọridim a dị ka algọridim nke abụọ:

• Usoro nkewa, ebe a na-ekewa n'usoro n'usoro dị nta
• Usoro nhazi bụ ebe a na-ejikọta obere arrays (iji otu) mepụta nnukwu nhazi.

Usoro nkewa

N'ọkwa nkewa, a na-ekewa n'usoro n'usoro n'otu n'ime usoro atọ. Ọnụọgụ usoro nke usoro bụ log (N) (ebe N=3, log(N) = 8).

Kedu ka m ga-esi mara nke a?

Abụ m onye amamihe! Na okwu - mgbakọ na mwepụ. Echiche bụ na nzọụkwụ ọ bụla na-ekewa nha nke nhazi mbụ site na 2. Ọnụ ọgụgụ nke nzọụkwụ bụ ugboro ole ị nwere ike kewaa nhazi mbụ ụzọ abụọ. Nke a bụ nkọwa zuru oke nke logarithm (base 2).

Usoro nhazi

N'oge nhazi, ị ga-amalite n'usoro n'otu (otu ihe). N'ime usoro nke ọ bụla, ị na-etinye ọtụtụ ọrụ njikọ ọnụ na ọnụ ahịa ya bụ N = 8 arụmọrụ:

• Na ọkwa mbụ ị nwere 4 merges na-eri 2 arụmọrụ ọ bụla
• Na nzọụkwụ nke abụọ ị nwere 2 merges na-eri 4 arụmọrụ ọ bụla
• Na nzọụkwụ nke atọ ị nwere 1 jikọrọ ọnụ nke na-efu 8 arụmọrụ

Ebe ọ bụ na e nwere usoro log (N), ngụkọta ọnụ N * log (N) arụ ọrụ.

Uru nke ụdị ngwakọta

Gịnị kpatara algọridim a ji dị ike?

N'ihi na:

• Ị nwere ike ịgbanwe ya ka ibelata akara ukwu ebe nchekwa ka ị ghara ịmepụta usoro ọhụrụ kama gbanwee usoro ntinye ozugbo.

Mara: a na-akpọ ụdị algọridim a in-ebe (ịhazi na-enweghị ebe nchekwa ọzọ).

• Ị nwere ike ịgbanwe ya ka iji ohere diski na obere ebe nchekwa n'otu oge na-enweghị ibubata I/O diski dị mkpa. Echiche bụ ịkwanye na ebe nchekwa naanị akụkụ ndị a na-ahazi ugbu a. Nke a dị mkpa mgbe ịchọrọ ịhazi tebụl multi-gigabyte nwere naanị ihe nchekwa nchekwa 100-megabyte.

Mara: a na-akpọ ụdị algọridim a ụdị mpụga.

• Ị nwere ike ịgbanwe ya ka ọ na-agba ọsọ na ọtụtụ usoro / eri / sava.

Dịka ọmụmaatụ, ụdị ngwakọta ekesara ekesa bụ otu n'ime ihe ndị bụ isi Hadoop (nke bụ nhazi na nnukwu data).

• Nke a algọridim nwere ike gbanwee ndu ka ọ bụrụ ọla edo (n'ezie!).

A na-eji nhazi usoro nhazi a n'ọtụtụ (ma ọ bụrụ na ọ bụghị ihe niile) ọdụ data, mana ọ bụghị naanị ya. Ọ bụrụ na ị chọrọ ịmatakwu, ị nwere ike ịgụ nke a ọrụ nyocha, nke na-atụle uru na ọghọm dị na usoro nhazi nchekwa data nkịtị.

Array, Osisi na Tebụl Hash

Ugbu a anyị ghọtara echiche nke mgbagwoju anya na nhazi oge, m ga-agwa gị gbasara usoro data 3. Nke a dị mkpa n'ihi na ha bụ ntọala nke ọdụ data ọgbara ọhụrụ. M ga-ewebatakwa echiche nchekwa data index.

Hazie

N'usoro akụkụ abụọ bụ usoro data kachasị mfe. Enwere ike iche tebụl dị ka nhazi. Ọmụmaatụ:

Nhazi akụkụ abụọ a bụ tebụl nwere ahịrị na kọlụm:

• Ahịrị ọ bụla na-anọchi anya otu ihe
• Ogidi na-echekwa akụrụngwa na-akọwa ihe ahụ.
• Kọlụm ọ bụla na-echekwa data nke otu ụdị (integer, eriri, ụbọchị...).

Nke a dị mma maka ịchekwa na ịhụ anya data, Otú ọ dị, mgbe ịchọrọ ịchọta otu uru, nke a adịghị mma.

Dịka ọmụmaatụ, ọ bụrụ na ịchọrọ ịchọta ụmụ okorobịa niile na-arụ ọrụ na UK, ị ga-achọ ileba anya n'ahịrị nke ọ bụla iji chọpụta ma ahịrị ahụ ọ bụ nke UK. Ọ ga-eri gị N azụmahịaebe N - ọnụọgụ nke ahịrị, nke na-adịghị njọ, mana enwere ike ịnwe ụzọ ngwa ngwa? Ugbu a, oge eruola ka anyị mata osisi ndị ahụ.

Rịba ama: Ọtụtụ ọdụ data ọgbara ọhụrụ na-enye usoro dị ogologo maka ịchekwa tebụl nke ọma: ihe a haziri nke obo na index-ahazi. Ma nke a anaghị agbanwe nsogbu nke ịchọta ngwa ngwa kpọmkwem ọnọdụ na otu ogidi.

Osisi nchekwa data na ndeksi

Osisi ọchụchọ ọnụọgụ abụọ bụ osisi ọnụọgụ abụọ nwere akụrụngwa pụrụ iche, igodo dị na ọnụ ọ bụla ga-abụrịrị:

• kariri igodo niile echekwara na osisi aka ekpe
• erughị igodo niile echekwara na osisi subtree ziri ezi

Ka anyị hụ ihe nke a pụtara anya

Echiche

Osisi a nwere N = 15 ọcha. Ka anyị kwuo na m na-achọ 208:

• M na-amalite na mgbọrọgwụ nke igodo ya bụ 136. Ebe ọ bụ na 136 <208, m na-ele anya na subtree nke ọma nke ọnụ 136.
• 398>208 Ya mere, m na-ele anya n'akụkụ aka ekpe nke ọnụ 398
• 250>208 Ya mere, m na-ele anya n'akụkụ aka ekpe nke ọnụ 250
• 200<208, Ya mere, m na-ele anya na nri subtree nke ọnụ 200. Ma 200 enweghị ikike subtree, uru adịghị adị (n'ihi na ọ bụrụ na ọ dị, ọ ga-abụ na nri subtree 200).

Ugbu a, ka anyị kwuo na m na-achọ 40

• M na-amalite na mgbọrọgwụ nke igodo ya bụ 136. Ebe ọ bụ na 136> 40, m na-ele anya n'akụkụ aka ekpe nke ọnụ 136.
• 80> 40, n'ihi ya, m na-ele anya na akụkụ aka ekpe nke ọnụ 80
• 40= 40, ọnụ dị. Ana m eweghachi ID ahịrị n'ime ọnụ (anaghị egosi na foto a) wee lelee tebụl maka ID ahịrị enyere.
• Ịmara ID ahịrị na-enye m ohere ịmata kpọmkwem ebe data dị na tebụl, ka m nwee ike weghachite ya ozugbo.

N'ikpeazụ, ọchụchọ abụọ ahụ ga-efu m ọnụ ọgụgụ ọkwa dị n'ime osisi ahụ. Ọ bụrụ na ị gụọ akụkụ gbasara ụdị ngwakọta nke ọma, ị ga-ahụ na enwere ọkwa log(N). Ọ tụgharịrị, ihe ndekọ ego ọchụchọ (N), ọ dịghị njọ!

Ka anyị laghachi na nsogbu anyị

Mana nke a bụ ihe nkịtị, yabụ ka anyị laghachi na nsogbu anyị. Kama integer dị mfe, were ya na eriri na-anọchi anya obodo mmadụ na tebụl gara aga. Ka anyị kwuo na ị nwere osisi nwere mpaghara "mba" (kọlụm 3) nke tebụl:

• Ọ bụrụ na ịchọrọ ịma onye na-arụ ọrụ na UK
• ị na-ele osisi ahụ anya iji nweta ọnụ nke na-anọchi anya Great Britain
• N'ime "UKnode" ị ga-ahụ ebe ndekọ ndị ọrụ UK dị.

Ọchịchọ a ga-efu ọrụ log(N) kama ịrụ ọrụ N ma ọ bụrụ na ị na-eji array ozugbo. Ihe ị gosipụtara bụ nchekwa data index.

Ị nwere ike wuo osisi index maka otu ubi ọ bụla (eriri, nọmba, ahịrị abụọ, nọmba na eriri, ụbọchị ...) ọ bụrụhaala na ị nwere ọrụ iji tụnyere igodo (ya bụ otu ubi) ka ị nwee ike ịtọ ịtụ n'etiti igodo (nke bụ ikpe maka ụdị isi ọ bụla na nchekwa data).

B+TreeIndex

Ọ bụ ezie na osisi a na-arụ ọrụ nke ọma maka ịnweta otu uru, enwere nnukwu nsogbu mgbe ịchọrọ nweta otutu ihe n'etiti ụkpụrụ abụọ. Nke a ga-efu O (N) n'ihi na ị ga-eleba anya na ọnụ ụzọ ọ bụla n'ime osisi ahụ wee chọpụta ma ọ dị n'etiti ụkpụrụ abụọ a (dịka ọmụmaatụ na iwu na-agafe osisi). Ọzọkwa, ọrụ a abụghị diski I / O enyi na enyi ebe ị ga-agụ osisi ahụ dum. Anyị kwesịrị ịchọta ụzọ iji rụọ ọrụ nke ọma arịrịọ nso. Iji dozie nsogbu a, ọdụ data ọgbara ọhụrụ na-eji ụdị osisi gara aga emezigharị nke a na-akpọ B+ Tree. N'ime osisi B+ Osisi:

• naanị ọnụ ọnụ kacha ala (akwụkwọ) na-echekwa ozi (ebe ahịrị dị na tebụl yiri ya)
• ọnụ ụzọ ndị ọzọ dị ebe a maka okporo ụzọ gaa n'ọnụ ziri ezi n'oge search.

Dị ka ị pụrụ ịhụ, e nwere ndị ọzọ ọnụ ebe a (ugboro abụọ). N'ezie, ị nwere ọnụ ụzọ ndị ọzọ, "ọnụ ọnụ mkpebi", nke ga-enyere gị aka ịchọta ọnụ ụzọ ziri ezi (nke na-echekwa ọnọdụ nke ahịrị na tebụl jikọtara). Mana mgbagwoju anya ọchụchọ ka bụ O(log(N)) (enwere naanị otu ọkwa ọzọ). Nnukwu ihe dị iche bụ nke ahụ ọnụ ọnụ na ọkwa dị ala jikọtara ndị na-anọchi ha.

Na B + Osisi a, ọ bụrụ na ị na-achọ ụkpụrụ n'etiti 40 na 100:

• Naanị ị ga-achọ 40 (ma ọ bụ uru kacha nso mgbe 40 ma ọ bụrụ na 40 adịghị) dị ka i mere na osisi gara aga.
• Wee chịkọta ndị nketa 40 site na iji njikọ ndị nketa ozugbo ruo mgbe ị ruru 100.

Ka anyị kwuo na ịchọta ndị nọchiri M na osisi ahụ nwere ọnụ N. Ịchọta kpọmkwem ọnụ ọnụ ọnụ log(N) dị ka osisi gara aga. Mana ozugbo ị nwetara ọnụ ọnụ a, ị ga-enweta ndị ga-anọchi M na arụrụ ọrụ na ntụnyere ndị ga-anọchi ha. Ọchụchọ a na-efu naanị M+log(N) arụmọrụ tụnyere N arụmọrụ na osisi gara aga. Ọzọkwa, ịgaghị agụ osisi zuru oke (naanị M+log(N) ọnụ), nke pụtara obere ojiji diski. Ọ bụrụ na M dị ntakịrị (dịka ahịrị 200) yana N buru ibu (ahịrị 1), a ga-enwe nnukwu ọdịiche.

Ma enwere nsogbu ọhụrụ ebe a (ọzọ!). Ọ bụrụ na ị gbakwunye ma ọ bụ hichapụ ahịrị na nchekwa data (ya mere na ntinye aha B+ Osisi):

• ị ga-edobe n'usoro n'etiti ọnụ ọnụ n'ime osisi B+, ma ọ bụghị ya, ị gaghị enwe ike ịchọta ọnụ ọnụ n'ime osisi na-adịghị edozi.
• ị ga-edobe opekempe ọnụọgụ ọkwa dị na B+ Osisi, ma ọ bụghị ya, mgbagwoju oge O(log(N)) na-aghọ O(N).

N'ikwu ya n'ụzọ ọzọ, B + Osisi ga-abụrịrị onye na-ahazi onwe ya na nke ziri ezi. Luckily, nke a ga-ekwe omume na smart ihichapụ na fanye arụmọrụ. Mana nke a na-abịa na ọnụ ahịa: ntinye na nhichapụ na ọnụ ahịa osisi B+ O(log(N)). Ọ bụ ya mere ụfọdụ n’ime unu nụrụ ihe ahụ iji ọtụtụ ndeksi eme ihe abụghị ezigbo echiche. N'ezie, ị na-ebelata ntinye ngwa ngwa / melite / ihichapụ ahịrị na tebụln'ihi na nchekwa data kwesịrị imelite ndepụta nke tebụl site na iji ọrụ O(log(N)) dị oke ọnụ maka ndeksi ọ bụla. Ọzọkwa, ịgbakwụnye index pụtara ọtụtụ ọrụ maka njikwa azụmahịa (a ga-akọwa ya na njedebe nke isiokwu).

Maka nkọwa ndị ọzọ, ị nwere ike ịhụ akụkọ Wikipedia na B+Osisi. Ọ bụrụ na ịchọrọ ịma atụ nke imejuputa B+ Osisi na nchekwa data, lee anya Akụkọ a и Akụkọ a site na onye nrụpụta MySQL na-eduga. Ha abụọ lekwasịrị anya ka InnoDB (njin MySQL) si ejikwa ndeksi.

Rịba ama: Onye na-agụ gwara m na, n'ihi nhazi ọkwa dị ala, osisi B+ kwesịrị ịdị na-edozi kpamkpam.

Hashtable

Nhazi data ikpeazụ anyị dị mkpa bụ tebụl hash. Nke a bara ezigbo uru mgbe ịchọrọ ilele ụkpụrụ ngwa ngwa. Ọzọkwa, ịghọta tebụl hash ga-enyere anyị aka ka anyị mechaa ghọta otu ọrụ njikọta nchekwa data a na-akpọ hash join ( hash sonyere). Ebe nchekwa data na-ejikwa nhazi data a iji chekwaa ụfọdụ ihe dị n'ime (dịka. okpokoro mkpọchi ma ọ bụ ọdọ mmiri buffer, anyị ga-ahụ echiche abụọ a ma emechaa).

Tebụl hash bụ nhazi data nke na-achọta ngwa ngwa site na igodo ya. Iji wuo tebụl hash ị ga-akọwapụta:

• ihe ngosi maka ihe gị
• ọrụ hash maka igodo. Hashes igodo agbakọtara na-enye ọnọdụ nke ihe ndị ahụ (a na-akpọ akụkụ ).
• ọrụ maka atụnyere igodo. Ozugbo ịchọtara akụkụ ziri ezi, ị ga-achọtarịrị ihe ị na-achọ n'ime akụkụ ahụ site na iji ntụnyere a.

Ihe atụ dị mfe

Ka anyị were ihe atụ doro anya:

Tebụl hash a nwere akụkụ iri. N'ihi na m dị umengwụ, m na-ese foto naanị akụkụ ise, mana amaara m na ị mara mma, yabụ m ga-ahapụ gị ka ị were foto nke ọzọ 10 n'onwe gị. Eji m ọrụ hash modulo 5 nke igodo ahụ. N'ikwu ya n'ụzọ ọzọ, ana m echekwa naanị ọnụọgụ ikpeazụ nke igodo mmewere iji chọta akụkụ ya:

• ọ bụrụ na ọnụọgụ ikpeazụ bụ 0, mmewere ahụ dabara na nkebi 0,
• ọ bụrụ na ọnụọgụ ikpeazụ bụ 1, mmewere ahụ dabara na nkebi 1,
• ọ bụrụ na ọnụọgụ ikpeazụ bụ 2, mmewere ahụ dabara na mpaghara 2,
• ...

Ọrụ ntụnyere m jiri bụ naanị nha nha n'etiti ọnụọgụ abụọ.

Ka anyị kwuo na ịchọrọ ịnweta element 78:

• Tebụl hash na-agbakọ koodu hash maka 78, nke bụ 8.
• Tebụl hash na-ele anya na akụkụ 8, ihe mbụ ọ chọtara bụ 78.
• Ọ na-eweghachiri gị ihe 78
• Ọchụchọ na-efu naanị ọrụ 2 (otu iji gbakọọ uru hash na nke ọzọ iji lelee mmewere n'ime akụkụ ahụ).

Ugbu a, ka anyị kwuo na ịchọrọ ịnweta element 59:

• Tebụl hash na-agbakọ koodu hash maka 59, nke bụ 9.
• Tebụl hash na-achọ na mpaghara 9, ihe mbụ achọtara bụ 99. Ebe ọ bụ na 99!=59, element 99 abụghị ezigbo mmewere.
• N'iji otu mgbagha ahụ, a na-ewere akụkụ nke abụọ (9), nke atọ (79), ..., nke ikpeazụ (29).
• Ahụghị ihe.
• Ihe nchọta ahụ na-efu ọrụ 7.

Ọrụ hash dị mma

Dị ka ị pụrụ ịhụ, dabere na uru ị na-achọ, ọnụ ahịa abụghị otu!

Ọ bụrụ na m na-agbanwe ugbu a na hash ọrụ modulo 1 nke igodo (ya bụ, na-na ikpeazụ 000 digits), nke abụọ na-achọ naanị 000 ọrụ ebe ọ bụ na e nweghị ọcha na nkebi 6. Ezigbo ihe ịma aka bụ ịchọta ezigbo ọrụ hash nke ga-emepụta bọket nwere ọnụ ọgụgụ dị nta nke ihe.

N'ihe atụ m, ịchọta ezigbo ọrụ hash dị mfe. Mana nke a bụ ọmụmaatụ dị mfe, ịchọta ezigbo ọrụ hash siri ike karị mgbe isi ihe bụ:

• eriri (dịka ọmụmaatụ - aha ikpeazụ)
• Ahịrị 2 (dịka ọmụmaatụ - aha ikpeazụ na aha mbụ)
• Ahịrị 2 na ụbọchị (dịka ọmụmaatụ - aha ikpeazụ, aha mbụ na ụbọchị ọmụmụ)
• ...

Site na ọrụ hash dị mma, nlele tebụl hash na-efu O(1).

Array vs tebụl hash

Gịnị mere na ị gaghị eji n'usoro?

Hmm, ajuju di nma.

• Tebụl hash nwere ike ịbụ etinyere ya n'ime ebe nchekwa, na akụkụ ndị fọdụrụ nwere ike ịnọgide na diski ahụ.
• Site n'usoro ị ga-eji oghere contiguous na ebe nchekwa. Ọ bụrụ na ị na-ebu nnukwu tebụl ọ na-esiri ike ịchọta oghere zuru oke na-aga n'ihu.
• Maka tebụl hash, ị nwere ike họrọ igodo ịchọrọ (dịka ọmụmaatụ, obodo na aha ikpeazụ mmadụ).

Maka ozi ndị ọzọ, ị nwere ike ịgụ akụkọ banyere ya JavaHashMap, nke bụ mmejuputa nke ọma nke tebụl hash; ọ dịghị mkpa ka ị ghọta Java ka ị ghọta echiche ndị e kwuru n'isiokwu a.

isi: www.habr.com