Hei Habr! Ka whakaatu ahau ki a koutou te whakamaoritanga o te tuhinga
"Me pehea te mahi a te papaunga raraunga hononga".

Ina tae mai ki nga paaunga paaunga kare e taea e au te whakaaro kei te ngaro tetahi mea. Ka whakamahia ki nga waahi katoa. He maha nga papaa raraunga rereke e waatea ana, mai i te SQLite iti me te whai hua ki te Teradata kaha. Engari he iti noa nga tuhinga e whakamarama ana me pehea te mahi a te putunga raraunga. Ka taea e koe te rapu mo koe ma te whakamahi "howdoesarelationaldatabasework" ki te kite i te iti o nga hua. I tua atu, he poto enei tuhinga. Mena kei te rapu koe mo nga hangarau puhoi hou (BigData, NoSQL, JavaScript ranei), ka kitea e koe etahi atu tuhinga hohonu e whakamarama ana me pehea te mahi.

He tawhito rawa, he hoha rawa nga paaunga hononga ki te whakamarama i waho o nga akoranga whare wananga, pepa rangahau me nga pukapuka?

Hei kaiwhakawhanake, e kino ana ahau ki te whakamahi i tetahi mea kaore au i te marama. A, ki te mea kua whakamahia nga papa korero mo nga tau neke atu i te 40, me whai take. I roto i nga tau, kua pau au i nga rau haora ki te mohio pono ki enei pouaka pango rereke ka whakamahia e au ia ra. Nga papaunga raraunga hononga tino whakamere no te mea ko ratou i runga i nga ariā whai hua me te whakamahi ano. Mena kei te pirangi koe ki te mohio ki tetahi putunga raraunga, engari kaore koe i whai wa, i te hiahia ranei ki te ruku ki tenei kaupapa whanui, me pai koe ki tenei tuhinga.

Ahakoa he tino marama te taitara o tenei tuhinga, ko te kaupapa o tenei tuhinga ko te kore e mohio ki te whakamahi i te paataka raraunga. No reira, Me mohio koe ki te tuhi i tetahi tono hononga ngawari me nga patai taketake nanakia; ki te kore kare pea koe e marama ki tenei tuhinga. Koina anake te mea e tika ana kia mohio koe, maku e whakamarama te toenga.

Ka timata ahau ki etahi tikanga putaiao rorohiko, penei i te uaua o te wa o te algorithms (BigO). E mohio ana ahau kei te kino etahi o koutou ki tenei ariā, engari ki te kore e kore e marama ki nga riipene o roto o te papaa raraunga. I te mea he kaupapa nui tenei, Ka arotahi ahau ko taku whakaaro he mea nui: pehea nga tukanga o te papaa raraunga SQL tono. Ka whakaatu noa ahau ariā pātengi raraunga taketakena i te mutunga o te tuhinga ka whai whakaaro koe mo nga mea kei te haere i raro i te hood.

I te mea he tuhinga roa me te hangarau tenei e uru ana ki te maha o nga algorithms me nga hanganga raraunga, tangohia to wa ki te panui i roto. Ko etahi o nga kaupapa he uaua ki te mohio; ka taea e koe te peke i a raatau ka whiwhi tonu i te whakaaro whanui.

Mo te hunga mohio ake i roto i a koutou, kua wehea tenei tuhinga ki nga wahanga e 3:

• Tirohanga o nga waahanga papaarangi taumata iti me te taumata teitei
• Tirohanga o te Tukanga Arotautanga Uiui
• Tirohanga mo te Whakawhitiwhiti me te Whakahaere Poaka Buffer

Hoki ki te kaupapa taketake

I nga tau ki muri (i roto i te tupuni tawhiti, tawhiti...), me tino mohio nga kaiwhakawhanake ki te maha o nga mahi e tohuhia ana e ratou. I mohio ratou ki o raatau algorithm me o raatau hanganga raraunga na te mea kaore e taea e ratou te whakapau i te PTM me te mahara ki o raatau rorohiko puhoi.

I tenei wahanga, ka whakamaumahara ahau ki a koe mo etahi o enei ariā i te mea he mea nui ki te mohio ki te paataka raraunga. Ka whakauru ano ahau i te kaupapa taupū pātengi raraunga.

O(1) vs O(n2)

I enei wa, he maha nga kaiwhakawhanake kaore e aro ki te uaua o te waa o nga algorithms ... a ka tika!

Engari i te wa e pa ana koe ki te maha o nga raraunga (kaore au e korero ana i nga mano) mena kei te raru koe i roto i nga manomano, he mea nui kia mohio koe ki tenei kaupapa. A, ka taea e koe te whakaaro, me mahi nga papaunga raraunga ki nga ahuatanga e rua! E kore ahau e tuku i a koe ki te whakapau atu i te wa e tika ana kia puta te korero. Ma tenei ka awhina i a maatau ki te mohio ki te kaupapa o te arotautanga utu i muri mai (utu hāngai arotautanga).

Kaupapa

Te uaua o te wa o te algorithm whakamahia ki te kite pehea te roa o te algorithm ki te whakaoti mo te nui o nga raraunga. Hei whakaahua i tenei uaua, ka whakamahia te tohu pangarau nui O. Ka whakamahia tenei tuhipoka me tetahi mahi e whakaatu ana i te maha o nga mahi e hiahiatia ana e te algorithm mo te maha o nga whakaurunga.

Hei tauira, ina kii ahau "he uaua tenei algorithm O(some_function())", ko te tikanga ka hiahiatia e te algorithm etahi mahi_mahi(a_certain_amount_of_data) hei tukatuka i etahi raraunga.

Ko te kupu Ehara i te nui o nga raraunga te mea nui**, ki te kore ** pehea te pikinga o te maha o nga mahi me te pikinga o te rōrahi raraunga. Ko te uauatanga o te waa kaore e whakaatu i te maha o nga mahi, engari he huarahi pai ki te whakatau tata i te waa mahi.

I roto i tenei kauwhata ka taea e koe te kite i te maha o nga mahi me te nui o nga raraunga whakauru mo nga momo uaua o te waa algorithm. I whakamahia e ahau he tauine taurau hei whakaatu. I etahi atu kupu, ka tere ake te nui o nga raraunga mai i te 1 ki te 1 piriona. Ka kite tatou e:

• O(1) ka noho tonu te uauatanga tonu (mehemea karekau e kiia he uaua tonu).
• O(takiuru(n)) kei te iti tonu ahakoa me nga piriona o nga raraunga.
• Ko te tino uaua - O(n2), ka tere haere te maha o nga mahi.
• Ko etahi atu raruraru e rua ka piki tere.

tauira

Ma te iti o nga raraunga, he iti noa te rereketanga o O(1) me O(n2). Hei tauira, me kii kei a koe he algorithm e hiahia ana ki te tukatuka i nga huānga 2000.

• Ko te O(1) algorithm ka utu koe kia 1 mahi
• Ko te O(log(n)) algorithm ka utu koe e 7 mahi
• Ko te O(n) algorithm ka utu koe 2 mahi
• Ko te O(n*log(n)) algorithm ka utu koe 14 mahi
• E 2 te utu mo te O(n4) algorithm

Ko te rereketanga i waenga i te O(1) me te O(n2) he ahua nui (4 miriona nga mahi) engari ka ngaro koe i te 2 ms morahi, he wa tika ki te kimo ou kanohi. Inaa, ka taea e nga tukatuka hou te tukatuka rau miriona nga mahi mo ia hekona. Koinei te take kaore he take i roto i nga kaupapa IT maha nga mahi me te arotautanga.

Ka rite ki taku korero, he mea nui tonu te mohio ki tenei kaupapa i te wa e mahi ana me te nui o nga raraunga. Mena i tenei wa ka tukatukahia e te algorithm te 1 huānga (ehara i te mea he nui mo te putunga raraunga):

• Ko te O(1) algorithm ka utu koe kia 1 mahi
• Ko te O(log(n)) algorithm ka utu koe e 14 mahi
• Ko te O(n) algorithm ka utu koe 1 mahi
• Ko te O(n*log(n)) algorithm ka utu koe 14 mahi
• Ko te O(n2) algorithm ka 1 nga mahi.

Kaore au i mahi i te pangarau, engari ka kii ahau me te O(n2) algorithm ka whai wa koe ki te inu kawhe (ara e rua!). Mena ka taapirihia e koe tetahi atu 0 ki te rōrahi raraunga, ka whai wa koe ki te moe.

Kia hohonu ake

Mo te tohutoro:

• Ka kitea he huānga i te O(1) ma te rapu ripanga hash pai.
• Ko te rapu i te rakau taurite pai ka puta nga hua i roto i te O(log(n)).
• Ko te rapu i te huānga ka puta he hua ki O(n).
• Ko te tino pai o te whakatakoto algorithm he uaua O(n*log(n)).
• He whīwhiwhi O(n2) te kōmaka hātepe hātepe.

Tuhipoka: I nga waahanga e whai ake nei ka kite tatou i enei algorithms me nga hanganga raraunga.

He maha nga momo uaua o te wa algorithm:

• te ahua o te keehi toharite
• te ahua pai rawa atu
• me te ahua kino rawa atu

Ko te uaua o te waa ko te ahua kino rawa atu.

I korero noa ahau mo te uaua o te wa o te algorithm, engari ka pa ano te uaua ki:

• kohi mahara o te algorithm
• kōpae I/O kohi hātepe

Ae ra, he raruraru kino atu i te n2, hei tauira:

• n4: he whakamataku tenei! Ko etahi o nga algorithms kua whakahuahia he uaua tenei.
• 3n: he kino rawa atu tenei! Ko tetahi o nga algorithms ka kitea e tatou i waenganui o tenei tuhinga he uaua tenei (a kei te whakamahia i roto i te maha o nga papaa raraunga).
• factorial n: e kore koe e whiwhi hua ahakoa he iti noa nga raraunga.
• nn: Mena ka tupono koe ki tenei uauatanga, me patai koe ki a koe ano mena koinei to waahi mahi...

Tuhipoka: Kaore au i whakaatu ki a koe te tino whakamaramatanga o te tohu O nui, he whakaaro noa. Ka taea e koe te panui i tenei tuhinga i Wikipedia mo te tino (asymptotic) whakamāramatanga.

HanumiKomaka

Ka aha koe ina hiahia koe ki te kōmaka kohinga? He aha? Ka karanga koe i te mahi sort()... Ok, pai te whakautu... Engari mo te putunga raraunga, me mohio koe ki te mahi o tenei momo () mahi.

He maha nga waahanga pai o te whakariterite, no reira ka aro ahau ki nga mea tino nui: hanumi momo. Kaore pea koe e mohio he aha te take e whai hua ai te tohatoha raraunga i tenei wa, engari me whai muri koe i te waahanga arotautanga patai. I tua atu, ma te mohio ki te momo hanumi ka awhina i a maatau ki te mohio ki te mahi hono paparangi e kiia nei hanumi uru (hononga hanumi).

Hanumi

Pērā i te maha o ngā hātepe hātepe whaihua, ko te whakakotahitanga ka whakawhirinaki ki te mahi tinihanga: ko te whakakotahi i nga huānga kōmaka e 2 o te rahi N/2 ki roto i te huānga kōmaka-N ka utu N noa nga mahi. Ka kiia tenei mahi ko te hanumi.

Kia kite tatou he aha te tikanga o tenei ma te tauira ngawari:

E whakaatu ana te ahua nei ki te hanga i te huinga huānga 8 kua oti te whakariterite, me huri kotahi koe i runga i nga huinga huānga 2 4. I te mea kua tohua kee nga huinga huānga-4 e rua:

• 1) ka whakatauritehia e koe nga mea e rua o naianei i roto i nga raupapa e rua (i te timatanga o naianei = tuatahi)
• 2) katahi ka tango i te mea iti rawa hei whakauru ki roto i te huinga huānga 8
• 3) ka neke ki te huānga e whai ake nei i te huinga i tangohia e koe te huānga iti rawa atu
• ka tuaruatia te 1,2,3 kia tae ra ano koe ki te waahanga whakamutunga o tetahi o nga rarangi.
• Na ka tango koe i nga toenga o nga huānga o tetahi atu huinga hei whakauru ki roto i te huinga huānga 8.

Ka whai hua tenei na te mea kua tohua nga huinga huānga-4 e rua, no reira kare koe e "hoki" ki aua rarangi.

Inaianei kua mohio tatou ki te tinihanga, koinei taku pseudocode mo te hanumi:

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;

Ko te whakakotahi i te ahua ka wahia he rapanga ki nga rapanga iti ake ka kitea nga hua o nga rapanga iti kia puta ai te hua o te rapanga tuatahi (whakatupato: ka kiia tenei momo algorithm he wehewehe me te raupatu). Ki te kore koe e marama ki tenei algorithm, kaua e manukanuka; Kare au i marama i te wa tuatahi ka kite ahau. Mena ka taea e koe te awhina, ka kite ahau i tenei algorithm hei waahanga e rua nga waahanga:

• Wāhanga wehenga, i reira ka wehewehea te huinga ki nga rarangi iti
• Ko te wahanga tohatoha ko te waahi ka whakakotahihia nga rarangi iti (ma te whakamahi i te uniana) hei hanga i tetahi huinga nui ake.

Wāhanga wehenga

I roto i te wahanga wehenga, ka wehea te huinga ki nga rarangi kotahitanga i roto i nga waahanga e 3. Ko te tau ōkawa o ngā kaupae he rangitaki(N) (mai i te N=8, rangitaki(N) = 3).

Me pehea taku mohio ki tenei?

He tohunga ahau! I roto i te kupu - pangarau. Ko te whakaaro ko ia taahiraa ka wehewehe i te rahi o te huinga taketake ki te 2. Ko te maha o nga hikoinga ko te maha o nga wa ka taea e koe te wehewehe i te huinga taketake kia rua. Koinei te tino whakamāramatanga o te taukohiko (papa 2).

Wāhanga kōmaka

I roto i te wahanga tohatoha, ka timata koe me nga huānga kotahitanga (kotahi-huānga). I ia taahiraa ka tono koe i nga mahi hanumi maha me te utu katoa ko N = 8 nga mahi:

• I te wahanga tuatahi e 4 nga hanumi e utu ana e 2 nga mahi mo ia mahi
• I te taahiraa tuarua he 2 nga hanumi e utu ana e 4 nga mahi mo ia mahi
• I te taahiraa tuatoru kei a koe te 1 hanumi e 8 nga mahi

I te mea he raarangi (N) kaupae, utu katoa N * takiuru(N) mahi.

Nga painga o te momo hanumi

He aha te kaha o tenei algorithm?

Nā te mea:

• Ka taea e koe te huri ki te whakaiti i te tapuwae mahara kia kore ai koe e hanga huranga hou engari ka whakarereke tika i te huinga whakauru.

Kia mahara: ka kiia tenei momo algorithm in-wahi (whakaraupapa me te kore mahara taapiri).

• Ka taea e koe te huri ki te whakamahi i te mokowā kōpae me te iti o te pūmahara i te wa kotahi me te kore e nui te utu o te kōpae I/O. Ko te whakaaro ko te utaina ki roto i te mahara ko nga waahanga anake e mahia ana i tenei wa. He mea nui tenei ina hiahia koe ki te whakariterite i tetahi ripanga maha-kikapaita me te 100-megabyte putunga mahara anake.

Kia mahara: ka kiia tenei momo algorithm ahua o waho.

• Ka taea e koe te whakarereke kia rere i runga i nga tukanga maha / miro / tūmau.

Hei tauira, ko te momo hanumi tohatoha tetahi o nga waahanga matua Hadoop (he hanganga i roto i nga raraunga nui).

• Ka taea e tenei algorithm te huri i te mata ki te koura (tino!).

Ka whakamahia tenei raupapa algorithm i roto i te nuinga (mehemea ehara i te katoa), engari ehara i te mea anake. Ki te hiahia koe ki te mohio atu, ka taea e koe te panui i tenei mahi rangahau, e matapaki ana i nga pai me nga huakore o nga mahinga algorithms tohatoha raraunga.

Huanga, Rakau me te Ripanga Hash

Inaianei kua maarama taatau ki te whakaaro o te uaua o te waa me te tohatoha, me korero atu ahau ki a koe mo nga hanganga raraunga e 3. He mea nui tenei na ratou ko te putake o nga papaa raraunga hou. Ka whakauru ano ahau i te kaupapa taupū pātengi raraunga.

Tuhinga

Ko te huinga ahu-rua te hanganga raraunga ngawari rawa atu. Ka taea te whakaaro he ripanga he huinga. Hei tauira:

Ko tenei huinga ahu-2 he ripanga me nga rarangi me nga pou:

• Ko ia raina he tohu hinonga
• Pupuri taonga nga pou e whakaatu ana i te hinonga.
• Kei ia tīwae nga raraunga o tetahi momo motuhake (tauoti, aho, ra...).

He watea tenei mo te penapena me te whakaata i nga raraunga, heoi, ka hiahia koe ki te rapu i tetahi uara motuhake, kaore e pai.

Hei tauira, ki te hiahia koe ki te kimi i nga taangata katoa e mahi ana i te UK, me titiro koe ki ia rarangi kia mohio ai no te UK tera rarangi. Ka utu koe N nga whakawhitingate wahi N - te maha o nga raina, kaore i te kino, engari tera pea he huarahi tere ake? Inaianei kua tae ki te wa kia mohio tatou ki nga rakau.

Tuhipoka: Ko te nuinga o nga papaa raraunga hou e whakarato ana i nga raupapatanga roa mo te penapena i nga ripanga pai: heap-organizedtables and index-organizedtables. Engari kaore tenei e whakarereke i te raru o te rapu tere i tetahi ahuatanga motuhake i roto i te roopu o nga pou.

Rakau pātengi raraunga me te taupū

Ko te rakau rapu-rua he rakau rua me tetahi taonga motuhake, ko te ki o ia pona ko:

• nui ake i nga taviri katoa e rongoa ana ki te rakau iti maui
• iti iho i nga taviri katoa e rongoa ana ki te rakauroto matau

Kia kite tatou he aha te tikanga o tenei ahua

Idea

He N = 15 nga huānga o tenei rakau. Me kii kei te rapu ahau mo te 208:

• Ka timata ahau i te putake ko te 136 tana matua. Mai i te 136<208, ka titiro ahau ki te riiroto matau o te node 136.
• 398>208 no reira kei te titiro au ki te taha maui o te rakau iti o te node 398
• 250>208 no reira kei te titiro au ki te taha maui o te rakau iti o te node 250
• 200<208, no reira kei te titiro au ki te rakau-iti matau o te node 200. Engari ko te 200 kaore he rakau-iti tika, karekau he uara (no te mea kei te noho tonu, kei te taha matau o te rakau iti 200).

Inaianei me kii kei te rapu ahau mo te 40

• Ka timata ahau i te putake ko te 136 tana ki. Mai i te 136 > 40, ka titiro ahau ki te taha maui o te rakau iti o te node 136.
• 80 > 40, no reira kei te titiro au ki te taha maui o te riu 80
• 40= 40, kei te noho. Ka tikina e ahau te ID rarangi kei roto i te node (kaore e whakaatuhia i te pikitia) ka titiro ki te ripanga mo te ID rarangi kua homai.
• Ma te mohio ki te rarangi ID ka taea e au te mohio kei hea nga raraunga kei roto i te ripanga, na reira ka taea e au te tiki tonu.

I te mutunga, ko nga rapunga e rua ka utu ahau i te maha o nga taumata kei roto i te rakau. Mena ka ata panui koe i te waahanga mo te whakakotahitanga, me kite koe kei reira nga reanga (N). Ka puta, rangitaki utu rapu(N), ehara i te kino!

Kia hoki tatou ki to tatou raruraru

Engari he tino maamaa tenei, no reira me hoki ano ki to tatou raru. Engari i te tauoti noa, whakaarohia he aho e tohu ana i te whenua o tetahi i te ripanga o mua. Me kii he rakau kei a koe te mara "whenua" (tatau 3) o te ripanga:

• Mena kei te hiahia koe ki te mohio ko wai e mahi ana i te UK
• ka titiro koe ki te rakau ki te tiki i te node e tohu ana i a Great Britain
• kei roto "UKnode" ka kitea e koe te waahi o nga rekoata kaimahi UK.

Ko tenei rapunga ka utu mo nga mahi rangitaki(N) hei utu mo nga mahinga N mena ka whakamahi tika koe i te hurangi. Ko ta koe i whakaatu ake nei taupū pātengi raraunga.

Ka taea e koe te hanga rakau taurangi mo nga roopu apure (aho, tau, 2 rarangi, tau me te aho, ra...) mena kei a koe he mahi ki te whakatairite i nga taviri (ara nga roopu mara) kia taea ai e koe te whakarite. raupapa i waenganui i nga ki (koinei te ahua o nga momo taketake kei roto i te paataka raraunga).

B+TatauRakau

Ahakoa he pai te mahi o tenei rakau mo te whiwhi uara motuhake, he raru nui ina hiahia koe whiwhi huānga maha i waenga i nga uara e rua. Ko te utu O(N) tenei na te mea me titiro koe ki ia node o te rakau ka tirohia mena kei waenga i enei uara e rua (hei tauira me te haere o te rakau). I tua atu, ehara tenei mahi i te kōpae I/O hoa na te mea me panui koe i te rakau katoa. Me kimi huarahi e tika ana te mahi tono awhe. Hei whakaoti i tenei rapanga, ka whakamahia e nga papaunga raraunga hou he putanga whakarereke o te rakau o mua ko B+Tree. I roto i te rakau B+Rākau:

• ko nga pona iti rawa (rau) rokiroki korero (te waahi o nga rarangi kei te ripanga e pa ana)
• kei konei te toenga o nga pona mo te ararere ki te node tika i te wa e rapu ana.

Ka kite koe, he maha ake nga pona kei konei (e rua). Inaa, kei a koe etahi atu pona, "nodes whakatau", hei awhina i a koe ki te kimi i te pona tika (e pupuri ana i te waahi o nga rarangi kei roto i te ripanga hono). Engari ko te uaua o te rapu he O(log(N)) (kotahi ano te taumata). Ko te rereketanga nui ko tera Ko nga pona kei te taumata o raro e hono ana ki o raatau whakakapi.

Ma tenei B+Rakau, mena kei te rapu koe mo nga uara i waenga i te 40 me te 100:

• Me rapu noa koe mo te 40 (te uara tata ranei i muri i te 40 mena karekau te 40) penei i a koe ki te rakau o mua.
• Ka kohia nga uri 40 ma te whakamahi i nga hononga tuku iho kia eke ra ano koe ki te 100.

Me kii ka kitea e koe nga kairiiwhi M me te rakau he N node. Te kimi i tetahi poronga utu node motuhake (N) penei i te rakau o mua. Engari ka whiwhi koe i tenei node, ka whiwhi koe i nga kaiwhakakapi M i roto i nga mahi M me nga tohutoro ki o raatau whakakapi. M+rau(N) anake te utu mo tenei rapunga i whakaritea ki nga mahi N i runga i te rakau o mua. I tua atu, kaore koe e hiahia ki te panui i te rakau katoa (anake M+log(N) node), he iti ake te whakamahinga o te kōpae. Mena he iti te M (hei tauira, 200 rarangi) me te nui o N (1 rarangi), ka puta he rereketanga NUI.

Engari he raru hou kei konei (ano!). Mēnā ka tāpirihia, ka mukua rānei he haupae i te pātengi raraunga (nā reira kei roto i te taupū B+Tree e pā ana):

• me mau tonu te ota i waenga i nga pona i roto i te Rakau B+, ki te kore ka kore e kitea e koe nga pona i roto i tetahi rakau kaore i tohua.
• me pupuri e koe te iti rawa o nga taumata e taea ana i te B+Rakau, ki te kore te O(takiuru(N)) uaua ka huri hei O(N).

Arā, ko te B+Tree me noho whakatau me te taurite. Waimarie, ka taea tenei ma te whakakore atamai me te whakauru i nga mahi. Engari he utu tenei: ko te whakauru me te whakakore i te utu rakau B+ O(rakau(N)). Koira te take i rongo ai etahi o koutou te whakamahi i te maha rawa o nga tohu kaore i te pai. Tena, kei te pōturi koe ki te whakauru tere/whakahou/muku i tetahi rarangi i roto i te ripangana te mea me whakahōu te pātengi raraunga i ngā taupū o te ripanga mā te whakamahi i te mahinga O(takiuru(N)) utu nui mō ia taupū. I tua atu, ko te taapiri i nga tohu tohu he nui ake te mahi mo kaiwhakahaere tauwhitinga (ka korerohia i te mutunga o te tuhinga).

Mo etahi atu korero, ka taea e koe te kite i te tuhinga Wikipedia i runga B+Rakau. Mena kei te pirangi koe ki tetahi tauira o te whakatinana i te B+Tree ki roto i te papanga raraunga, tirohia tenei tuhinga и tenei tuhinga mai i tetahi kaiwhakawhanake MySQL rangatira. Ka aro atu raua ki te whakahaere a InnoDB (te miihini MySQL) ki nga tohu tohu.

Tuhipoka: I kii mai tetahi kaipanui ki a au, na te iti o te arotautanga, me tino taurite te rakau B+.

Hashtable

Ko ta matou hanganga raraunga nui whakamutunga ko te ripanga hash. He tino whai hua tenei ina hiahia koe ki te rapu tere i nga uara. I tua atu, ma te mohio ki te ripanga hash ka awhina i a maatau ki te mohio ki tetahi mahi honohono putunga korero e kiia nei ko te hono hash ( urunga hash). Ka whakamahia hoki tenei hanganga raraunga e te papaaarangi ki te penapena i etahi mea o roto (hei tauira. tepu raka ranei puna kaukau, ka kite tatou i enei kaupapa e rua i muri mai).

Ko te ripanga hash he hanganga raraunga ka kitea tere he huānga i runga i tana matua. Hei hanga ripanga hash me tautuhi koe:

• tohu mo o huānga
• mahi hash mo nga taviri. Ko nga hashes matua kua tohua te waahi o nga huānga (e kiia ana nga wahanga ).
• mahi hei whakatairite i nga taviri. Ina kitea e koe te waahanga tika, me rapu koe i te huānga e rapu ana koe i roto i te waahanga ma te whakamahi i tenei whakataurite.

He tauira ngawari

Me tango he tauira marama:

He 10 nga wahanga o tenei ripanga hash. No te mea he mangere ahau, e 5 noa iho nga wahanga i whakaahuahia, engari e mohio ana ahau he mohio koe, no reira ka tukuna e au te pikitia e 5 ki a koe ake. I whakamahia e ahau he mahinga hash modulo 10 o te matua. Arā, ka penapenahia e ahau te mati whakamutunga o te kī o te huānga ki te kimi i tōna wāhanga:

• ki te 0 te mati whakamutunga, ka taka te huānga ki te wahanga 0,
• ki te 1 te mati whakamutunga, ka taka te huānga ki te wahanga 1,
• ki te 2 te mati whakamutunga, ka taka te huānga ki te horahanga 2,
• ...

Ko te mahi whakatairite i whakamahia e au he taurite noa i waenga i nga tauoti e rua.

Me kii e hiahia ana koe ki te tiki huānga 78:

• Ka tātaihia e te ripanga hash te waehere hash mo te 78, ko te 8.
• Ka titiro te ripanga hash ki te wahanga 8, ko te huānga tuatahi ka kitea ko te 78.
• Ka whakahokia e ia te nama 78 ki a koe
• Ko nga utu rapu 2 anake nga mahi (kotahi hei tatau i te uara hash me tetahi hei titiro ake i te huānga i roto i te wahanga).

Inaianei me kii e hiahia ana koe ki te tiki huānga 59:

• Ka tātaihia e te ripanga hash te waehere hash mo te 59, ko te 9.
• Ka rapu te ripanga hash i te wahanga 9, ko te huānga tuatahi i kitea ko te 99. Mai i te 99!=59, ehara te huānga 99 i te huānga whaimana.
• Ma te whakamahi i te arorau ano, ka tangohia te waahanga tuarua (9), te tuatoru (79), ..., te whakamutunga (29).
• Kāore i kitea te huānga.
• E 7 nga utu mo te rapu.

Mahi hash pai

Ka taea e koe te kite, i runga i te uara e rapu ana koe, kaore i te rite te utu!

Mena ka huri au i te mahi hash modulo 1 o te matua (ara, te tango i nga mati 000 whakamutunga), 000 anake te utu mo te rapu tuarua i te mea karekau he huānga o te wahanga 6. Ko te tino wero ko te kimi i tetahi mahi hash pai ka hanga peere he iti rawa nga huānga kei roto.

I roto i taku tauira, he ngawari te rapu i te mahi hash pai. Engari he tauira ngawari tenei, he uaua ake te rapu mahi hash pai ina ko te mea matua:

• aho (hei tauira - ingoa whanau)
• 2 rarangi (hei tauira - ingoa whakamutunga me te ingoa tuatahi)
• 2 rarangi me te ra (hei tauira - ingoa whakamutunga, ingoa tuatahi me te ra whanau)
• ...

Ma te pai o te mahi hash, te utu o nga rapunga ripanga hash O(1).

Huanga me te ripanga hash

He aha e kore ai e whakamahi i te huānga?

Hmm, pai te patai.

• Ka taea te ripanga hash kua utaina ki te mahara, ka noho tonu nga wahanga e toe ana ki te kōpae.
• Ma te huānga me whakamahi koe i te mokowā piri ki te mahara. Mena kei te utaina e koe he tepu nui he tino uaua ki te kimi i te waahi tonu.
• Mo te ripanga hash, ka taea e koe te kowhiri i te taviri e hiahia ana koe (hei tauira, te whenua me te ingoa whakamutunga o te tangata).

Mo etahi atu korero, ka taea e koe te panui i te tuhinga mo JavaMahereTohu, he whakatinanatanga pai o te ripanga hash; e kore koe e hiahia ki te matau Java ki te matau i te ariā hipoki i roto i tenei tuhinga.

Source: will.com