Pa Habr! Ndikupereka kwa inu kumasulira kwa nkhaniyi
"Kodi database yolumikizana imagwira ntchito bwanji".

Zikafika pazosungidwa zaubwenzi sindingachitire mwina koma kuganiza kuti china chake chikusowa. Amagwiritsidwa ntchito paliponse. Pali nkhokwe zambiri zosiyanasiyana zomwe zilipo, kuchokera ku SQLite yaying'ono komanso yothandiza mpaka Teradata yamphamvu. Koma pali zolemba zochepa zomwe zimafotokoza momwe database imagwirira ntchito. Mutha kudzifufuza nokha pogwiritsa ntchito "momwe mungagwirizanitse ntchito zosunga zobwezeretsera" kuti muwone zotsatira zomwe zilipo zochepa. Komanso, nkhanizi ndi zazifupi. Ngati mukuyang'ana matekinoloje aposachedwa kwambiri (BigData, NoSQL kapena JavaScript), mupeza zolemba zakuya zofotokozera momwe zimagwirira ntchito.

Kodi nkhokwe zaubale zakale kwambiri komanso zotopetsa kuti sizingafotokozedwe kunja kwa maphunziro akuyunivesite, mapepala ofufuza ndi mabuku?

Monga wopanga, ndimadana ndi kugwiritsa ntchito zomwe sindimamvetsetsa. Ndipo ngati nkhokwe zakhala zikugwiritsidwa ntchito kwa zaka zopitilira 40, payenera kukhala chifukwa. Kwa zaka zambiri, ndakhala maola mazana ambiri kuti ndimvetsetse mabokosi akuda achilendo awa omwe ndimagwiritsa ntchito tsiku lililonse. Zogwirizana ndi database zosangalatsa kwambiri chifukwa iwo kutengera malingaliro othandiza komanso osinthika. Ngati mukufuna kumvetsetsa nkhokwe, koma simunakhalepo ndi nthawi kapena malingaliro oti mufufuze pamutu waukuluwu, muyenera kusangalala ndi nkhaniyi.

Ngakhale mutu wa nkhaniyi ukumveka bwino, cholinga cha nkhaniyi sikumvetsetsa momwe mungagwiritsire ntchito nkhokwe. Chifukwa chake, muyenera kudziwa kale kulemba pempho losavuta lolumikizana ndi mafunso oyambira CHIWALO; mwinamwake simungamvetse nkhaniyi. Ndi chinthu chokha chomwe muyenera kudziwa, ndikufotokozerani zina.

Ndiyamba ndi zoyambira za sayansi yamakompyuta, monga nthawi yovuta yama algorithms (BigO). Ndikudziwa kuti ena mwa inu mumadana ndi lingaliro ili, koma popanda izo simudzatha kumvetsetsa zovuta zomwe zili mkati mwa database. Popeza uwu ndi mutu waukulu, Ndiyang'ana kwambiri zomwe ndikuganiza kuti ndizofunikira: momwe database imayendera SQL kufunsa. Ndingofotokoza mfundo zazikulu za databasekotero kuti kumapeto kwa nkhaniyo muli ndi lingaliro la zomwe zikuchitika pansi pa hood.

Popeza iyi ndi nkhani yayitali komanso yaukadaulo yomwe imaphatikizapo ma aligorivimu ambiri ndi mapangidwe a data, tengani nthawi yanu kuti muwerenge. Mfundo zina zingakhale zovuta kuzimvetsa; mukhoza kuwadumpha ndikupeza lingaliro lonse.

Kwa odziwa zambiri pakati panu, nkhaniyi yagawidwa m'magawo atatu:

• Chidule cha magawo otsika komanso apamwamba kwambiri a database
• Chidule cha Query Optimization Process
• Chidule cha Transaction ndi Buffer Pool Management

Bwererani ku zoyambira

Zaka zapitazo (mu mlalang'amba wakutali, kutali ...), opanga adayenera kudziwa ndendende kuchuluka kwa ntchito zomwe amalemba. Amadziwa ma aligorivimu awo ndi mapangidwe a data pamtima chifukwa sakanatha kuwononga CPU ndikukumbukira makompyuta awo pang'onopang'ono.

Mugawoli, ndikukumbutsani ena mwa mfundozi chifukwa ndizofunika kumvetsetsa nkhokwe. Ndikuwonetsanso lingaliro database index.

O(1) vs O(n2)

Masiku ano, opanga ambiri sasamala za nthawi yovuta ya ma algorithms ... ndipo akulondola!

Koma pamene mukulimbana ndi deta zambiri (sindikulankhula zikwi) kapena ngati mukulimbana ndi milliseconds, zimakhala zovuta kumvetsa mfundoyi. Ndipo monga momwe mungaganizire, nkhokwe ziyenera kuthana ndi zochitika zonsezi! Sindikupangani kuti muwononge nthawi yochulukirapo kuposa yofunikira kuti mumvetsetse mfundoyo. Izi zitithandiza kumvetsetsa lingaliro la kukhathamiritsa kotengera mtengo pambuyo pake (mtengo potengera kukhathamiritsa).

Concept

Kuvuta kwa nthawi kwa algorithm amagwiritsidwa ntchito kuwona kuti zidzatenga nthawi yayitali bwanji kuti achite ma algorithm pamtundu womwe waperekedwa. Pofotokoza zovutazi, timagwiritsa ntchito notation yayikulu ya O. Mawuwa amagwiritsidwa ntchito ndi ntchito yomwe imafotokoza kuchuluka kwa ma aligorivimu omwe amafunikira pazolowera zingapo.

Mwachitsanzo, ndimati "chiwerengerochi chili ndi zovuta O(some_function())", zikutanthauza kuti ndondomekoyi imafuna ntchito zina_zochita (a_certain_amount_of_data) kuti zithetse kuchuluka kwa deta.

Motero Si kuchuluka kwa data komwe kuli kofunikira **, mwinamwake ** momwe kuchuluka kwa ntchito kumachulukira ndi kuchuluka kwa data. Kuvuta kwa nthawi sikumapereka kuchuluka kwenikweni kwa ntchito, koma ndi njira yabwino yowerengera nthawi yogwirira ntchito.

Mu graph iyi mutha kuwona kuchuluka kwa magwiridwe antchito motsutsana ndi kuchuluka kwa zolowetsa zamitundu yosiyanasiyana ya zovuta za nthawi ya algorithm. Ndinagwiritsa ntchito sikelo ya logarithmic kuti ndiwonetse. Mwa kuyankhula kwina, kuchuluka kwa deta kumawonjezeka mwamsanga kuchokera ku 1 kufika ku 1 biliyoni. Titha kuona kuti:

• O (1) kapena kusinthasintha kosalekeza kumakhalabe kosasintha (kupanda kutero sikungatchulidwe kuti ndizovuta nthawi zonse).
• O(fufuzani(n)) imakhalabe yotsika ngakhale ndi mabiliyoni a data.
• Chovuta kwambiri - O(n2), pomwe kuchuluka kwa ntchito kumakula mwachangu.
• Mavuto ena awiriwa amawonjezeka mofulumira.

zitsanzo

Ndi chiwerengero chochepa cha deta, kusiyana pakati pa O (1) ndi O (n2) n'kosavuta. Mwachitsanzo, tiyerekeze kuti muli ndi algorithm yomwe ikufunika kukonza zinthu 2000.

• The O (1) aligorivimu idzakutengerani ntchito imodzi
• The O(log(n)) aligorivimu idzakutengerani ntchito 7
• Ma algorithm a O(n) adzakuwonongerani ntchito 2
• Ma algorithm a O(n*log(n)) adzakudyerani ndalama zokwana 14
• Ma algorithm a O(n2) adzakudyerani ndalama zokwana 4

Kusiyana pakati pa O(1) ndi O(n2) kumawoneka ngati kwakukulu (ntchito 4 miliyoni) koma mutha kutaya ma 2 ms, nthawi yoti muphethire maso anu. Zowonadi, mapurosesa amakono amatha kukonza mazana mamiliyoni a ntchito pa sekondi iliyonse. Ichi ndichifukwa chake magwiridwe antchito ndi kukhathamiritsa sizovuta pama projekiti ambiri a IT.

Monga ndanenera, ndikofunikirabe kudziwa lingaliro ili pogwira ntchito ndi data yambiri. Ngati nthawi ino aligorivimu iyenera kukonza zinthu 1 (zomwe sizochuluka pa database):

• The O (1) aligorivimu idzakutengerani ntchito imodzi
• The O(log(n)) aligorivimu idzakutengerani ntchito 14
• Ma algorithm a O(n) adzakudyerani ndalama zokwana 1
• Ma algorithm a O(n*log(n)) adzakudyerani ndalama zokwana 14.
• Ma algorithm a O(n2) adzakudyerani ndalama zokwana 1.

Sindinachite masamu, koma ndinganene kuti ndi O(n2) algorithm muli ndi nthawi yomwa khofi (ngakhale awiri!). Ngati muwonjezeranso 0 ku voliyumu ya data, mudzakhala ndi nthawi yoti mugone.

Tiyeni tipite mozama

Kuti muwerenge:

• Kuyang'ana bwino kwa tebulo la hashi kumapeza chinthu mu O (1).
• Kusaka mtengo wokhazikika bwino kumabweretsa zotsatira mu O(logi(n)).
• Kusaka gulu kumabweretsa zotsatira mu O(n).
• Ma algorithms abwino kwambiri osankhira amakhala ndi zovuta O(n*log(n)).
• Kusanja koyipa kumakhala ndi zovuta O(n2).

Chidziwitso: M'magawo otsatirawa tiwona ma aligorivimu ndi ma data.

Pali mitundu ingapo ya zovuta za nthawi ya algorithm:

• pafupifupi zochitika
• nkhani yabwino kwambiri
• ndi zochitika zoyipa kwambiri

Kuvuta kwa nthawi nthawi zambiri kumakhala koyipa kwambiri.

Ndimangolankhula za zovuta za nthawi ya algorithm, koma zovuta zimagwiranso ntchito ku:

• kukumbukira kukumbukira kwa algorithm
• disk I/O kugwiritsa ntchito algorithm

Zachidziwikire, pali zovuta zoyipa kuposa n2, mwachitsanzo:

• n4: izi ndi zoopsa! Ena mwa ma algorithms otchulidwa ali ndi zovuta izi.
• 3n: izi ndizoyipa kwambiri! Imodzi mwama algorithms omwe tiwona pakati pa nkhaniyi ili ndi zovuta izi (ndipo imagwiritsidwa ntchito m'ma database ambiri).
• factorial n: simudzapeza zotsatira zanu ngakhale ndi data yochepa.
• nn: Mukakumana ndi zovuta izi, muyenera kudzifunsa ngati ili ndi gawo lanu lomwe mumachita ...

Chidziwitso: Sindinakupatseni tanthauzo lenileni la dzina lalikulu la O, lingaliro lokha. Mukhoza kuwerenga nkhaniyi pa Wikipedia kwa tanthauzo lenileni (la asymptotic).

MergeSort

Kodi mumatani mukafuna kusanja zosonkhanitsira? Chani? Mumatchula ntchito ya mtundu () ... Chabwino, yankho labwino ... Koma kwa database, muyenera kumvetsetsa momwe izi () ntchito zimagwirira ntchito.

Pali ma aligorivimu angapo abwino osankhira, ndiye ndimayang'ana kwambiri zofunika kwambiri: kuphatikiza mtundu. Mwina simungamvetse chifukwa chake kusanja deta kuli kothandiza pakali pano, koma muyenera pambuyo pa gawo lokonzekera mafunso. Kuphatikiza apo, kumvetsetsa merge sort kudzatithandiza kumvetsetsa ntchito yolumikizana ndi database yomwe imatchedwa kuphatikiza Funsani (mgwirizano wamagulu).

Gwirizanitsani

Monga ma algorithms ambiri othandiza, kuphatikiza mtundu kumadalira chinyengo: kuphatikiza mindandanda iwiri yosanja ya kukula N/2 kukhala gulu losanjidwa la N kumangotengera ntchito za N. Ntchitoyi imatchedwa kuphatikiza.

Tiyeni tiwone tanthauzo la izi ndi chitsanzo chosavuta:

Chiwerengerochi chikuwonetsa kuti kuti mupange gulu lomaliza la 8-element, muyenera kungobwereza kamodzi pazotsatira za 2 4-element. Popeza magulu onse a 4 asankhidwa kale:

• 1) mumayerekezera zinthu zonse ziwiri zomwe zilipo m'magulu awiri (pa chiyambi panopa = choyamba)
• 2) kenako tengani kakang'ono kwambiri kuti muyike mumagulu 8
• 3) ndikusunthira ku chinthu chotsatira pamndandanda womwe mudatenga chinthu chaching'ono kwambiri
• ndikubwereza 1,2,3 mpaka mufikire gawo lomaliza la gulu limodzi.
• Kenako mumatenga zinthu zotsala za gulu lina kuti muwaike mumagulu 8.

Izi zimagwira ntchito chifukwa magulu onse a 4 amasankhidwa ndipo simuyenera "kubwerera" m'magulu amenewo.

Tsopano popeza tamvetsetsa zachinyengo, nayi pseudocode yanga yophatikiza:

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 imaphwanya vuto kukhala zovuta zing'onozing'ono kenako amapeza zotsatira zazovuta zazing'ono kuti apeze zotsatira za vuto loyambirira (zindikirani: mtundu uwu wa algorithm umatchedwa kugawa ndi kugonjetsa). Ngati simukumvetsa algorithm iyi, musadandaule; Sindinachimvetse nthawi yoyamba yomwe ndinachiwona. Ngati ingakuthandizeni, ndikuwona algorithm iyi ngati algorithm yamagawo awiri:

• Gawo la magawo, pomwe gululi limagawidwa m'magulu ang'onoang'ono
• Gawo losankhira ndi pomwe magulu ang'onoang'ono amaphatikizidwa (pogwiritsa ntchito mgwirizano) kuti apange gulu lalikulu.

Gawo gawo

Mu gawo la magawo, gululi limagawidwa m'magulu amodzi mu masitepe atatu. Nambala yokhazikika ya masitepe ndi log(N) (kuyambira N=3, chipika(N) = 8).

Kodi ndikudziwa bwanji izi?

Ndine genius! M'mawu amodzi - masamu. Lingaliro ndiloti sitepe iliyonse imagawaniza kukula kwa mndandanda wapachiyambi ndi 2. Chiwerengero cha masitepe ndi chiwerengero cha nthawi zomwe mungathe kugawanitsa zoyambazo kukhala ziwiri. Uku ndiye tanthauzo lenileni la logarithm (base 2).

Kusanja gawo

Mu gawo losankhira, mumayamba ndi magulu amodzi (chinthu chimodzi). Pa sitepe iliyonse mumagwiritsa ntchito maphatikizidwe angapo ndipo mtengo wake ndi N = 8 ntchito:

• Mugawo loyamba muli ndi zophatikizira 4 zomwe zimawononga ma opareshoni awiri chilichonse
• Mugawo lachiwiri muli ndi kuphatikiza 2 komwe kumawononga ma opareshoni 4 aliwonse
• Mugawo lachitatu muli ndi kuphatikiza 1 komwe kumawononga ntchito 8

Popeza pali log(N) masitepe, mtengo wonse N * log (N) ntchito.

Ubwino wa kuphatikiza mtundu

Chifukwa chiyani algorithm iyi ili yamphamvu kwambiri?

Chifukwa:

• Mutha kuyisintha kuti muchepetse kukumbukira kukumbukira kuti musapange zosefera zatsopano koma musinthe mwachindunji magawo olowera.

Zindikirani: mtundu uwu wa algorithm umatchedwa in-malo (kusanja popanda kukumbukira kowonjezera).

• Mutha kusintha kuti mugwiritse ntchito danga la disk ndi kukumbukira pang'ono nthawi imodzi popanda kubweretsa diski yayikulu I / O pamwamba. Lingaliro ndikulowetsa mu kukumbukira magawo omwe akukonzedwa pano. Izi ndizofunikira mukafuna kusanja tebulo la ma gigabyte angapo ndi 100-megabyte memory buffer yokha.

Zindikirani: mtundu uwu wa algorithm umatchedwa kusanja kwakunja.

• Mutha kuyisintha kuti igwire ntchito zingapo / ulusi / maseva.

Mwachitsanzo, kugawa kuphatikiza mtundu ndi chimodzi mwazinthu zofunika kwambiri Hadoop (chomwe chiri mawonekedwe mu data yayikulu).

• Algorithm iyi imatha kusandutsa lead kukhala golide (kwenikweni!).

Algorithm yosankha iyi imagwiritsidwa ntchito m'malo ambiri (ngati si onse), koma si yokhayo. Ngati mukufuna kudziwa zambiri, mutha kuwerenga izi ntchito yofufuza, yomwe imakambirana zabwino ndi zoyipa za ma aligorivimu wamba a database.

Array, Tree ndi Hash Table

Tsopano popeza tamvetsetsa lingaliro lakuvuta kwa nthawi ndikusanja, ndikuuzeni zamitundu itatu ya data. Izi ndi zofunika chifukwa iwo ndiwo maziko a nkhokwe zamakono. Ndikuwonetsanso lingaliro database index.

Mzere

Awiri-dimensional array ndi yosavuta deta dongosolo. Gome likhoza kuganiziridwa ngati gulu. Mwachitsanzo:

Gulu la 2-dimensional ili ndi tebulo lomwe lili ndi mizere ndi mizati:

• Mzere uliwonse umayimira chinthu
• Mizati imasunga zinthu zomwe zimafotokoza za bungwe.
• Mzere uliwonse umasunga deta yamtundu wake (intaneti, zingwe, deti...).

Izi ndizosavuta kusunga ndikuwonera deta, komabe, mukafuna kupeza mtengo wake, izi sizoyenera.

Mwachitsanzo, ngati mukufuna kupeza anyamata onse ogwira ntchito ku UK, muyenera kuyang'ana mzere uliwonse kuti muwone ngati mzerewo ndi wa UK. Zidzakutengerani ndalama za Nkumene N - chiwerengero cha mizere, chomwe sichili choipa, koma kodi pangakhale njira yachangu? Tsopano ndi nthawi yoti tidziŵe mitengo.

Zindikirani: Malo ambiri amakono amakono amapereka mndandanda wowonjezereka wosungira matebulo moyenera: milu-organidtables ndi index-organizedtables. Koma izi sizisintha vuto lopeza msanga chikhalidwe china mu gulu la mizati.

Mtengo wa database ndi index

Mtengo wosakira wa binary ndi mtengo wa binary wokhala ndi katundu wapadera, fungulo pa node iliyonse liyenera kukhala:

• chachikulu kuposa makiyi onse osungidwa mumzere wamanzere
• zochepa kuposa makiyi onse osungidwa mumzere waung'ono wolondola

Tiyeni tiwone chomwe izi zikutanthauza zowoneka

Maganizo

Mtengo uwu uli ndi N = 15 zinthu. Tiyerekeze kuti ndikuyang'ana 208:

• Ndikuyamba pa muzu womwe fungulo lake ndi 136. Kuyambira 136<208, ndimayang'ana pamtundu woyenera wa node 136.
• 398>208 chifukwa chake ndikuyang'ana kumanzere kwa node 398
• 250>208 chifukwa chake ndikuyang'ana kumanzere kwa node 250
• 200<208, kotero ndikuyang'ana pamtundu woyenera wa node 200. Koma 200 ilibe subtree yoyenera, mtengo palibe (chifukwa ngati ilipo, idzakhala mumzere wolondola wa 200).

Tsopano tinene kuti ndikufuna 40

• Ndimayambira pa muzu womwe makiyi ake ndi 136. Kuyambira 136> 40, ndimayang'ana kumanzere kwa node 136.
• 80> 40, chifukwa chake ndikuyang'ana kumanzere kwa node 80
• 40 = 40, node ilipo. Ndimatenganso ID ya mzere mkati mwa node (yosawonetsedwa pachithunzichi) ndikuyang'ana patebulo la ID ya mzere womwe wapatsidwa.
• Kudziwa ID ya mzere kumandilola kudziwa komwe deta ili patebulo, kuti nditha kuyipeza nthawi yomweyo.

Pamapeto pake, kusaka kulikonse kudzandiwonongera kuchuluka kwa milingo mkati mwa mtengo. Mukawerenga gawo la kuphatikiza mtundu mosamala, muyenera kuwona kuti pali milingo ya log(N). Zikuoneka kuti, kusaka mtengo (N), osayipa kwenikweni!

Tiyeni tibwerere ku vuto lathu

Koma izi ndizovuta kwambiri, choncho tiyeni tibwerere ku vuto lathu. M'malo mwa chiwerengero chosavuta, ganizirani chingwe chomwe chikuyimira dziko la munthu pa tebulo lapitalo. Tiyerekeze kuti muli ndi mtengo womwe uli ndi gawo la "dziko" (gawo 3) patebulo:

• Ngati mukufuna kudziwa omwe amagwira ntchito ku UK
• mumayang'ana mtengo kuti mupeze mfundo yomwe ikuyimira Great Britain
• mkati mwa "UKnode" mudzapeza malo a UK worker records.

Kusakaku kudzawononga mtengo wa log(N) m'malo mwa ntchito za N ngati mugwiritsa ntchito molunjika. Zomwe mwangoperekazo zinali database index.

Mutha kupanga mtengo wolozera gulu lililonse la magawo (chingwe, nambala, mizere 2, nambala ndi chingwe, deti...) bola ngati muli ndi ntchito yofananiza makiyi (ie magulu am'munda) kuti mutha kukhazikitsa. dongosolo pakati pa makiyi (zomwe zili choncho pamitundu iliyonse yoyambira mu database).

B+TreeIndex

Ngakhale mtengo uwu umagwira ntchito bwino kuti upeze mtengo weniweni, pali vuto lalikulu pamene mukufunikira pezani zinthu zingapo pakati pa zinthu ziwiri. Izi zidzawononga O(N) chifukwa muyenera kuyang'ana node iliyonse mumtengo ndikuwunika ngati ili pakati pazikhalidwe ziwirizi (mwachitsanzo, ndikudutsa mtengo). Komanso, opaleshoniyi si disk I / O ochezeka popeza muyenera kuwerenga mtengo wonse. Tiyenera kupeza njira yochitira bwino osiyanasiyana pempho. Kuti athetse vutoli, zolemba zamakono zimagwiritsa ntchito mtundu wosinthidwa wa mtengo wam'mbuyo wotchedwa B + Tree. Mumtengo wa B+Tree:

• ma node otsika kwambiri (masamba) sungani zambiri (malo amizere mu tebulo logwirizana)
• ma node ena onse ali pano za mayendedwe ku node yolondola pakusaka.

Monga mukuonera, pali mfundo zambiri pano (kawiri). Zowonadi, muli ndi ma node owonjezera, "zosankha", zomwe zingakuthandizeni kupeza mfundo yolondola (yomwe imasunga malo amizere patebulo logwirizana). Koma zovuta zofufuzira zikadali O(logi(N)) (pali mulingo umodzi wokha). Kusiyana kwakukulu ndiko node pamlingo wapansi amalumikizidwa ndi olowa m'malo awo.

Ndi Mtengo wa B + uwu, ngati mukuyang'ana zapakati pa 40 ndi 100:

• Mukungoyenera kuyang'ana 40 (kapena mtengo wapafupi pambuyo pa 40 ngati 40 kulibe) monga momwe munachitira ndi mtengo wam'mbuyo.
• Kenako sonkhanitsani olowa 40 pogwiritsa ntchito maulalo olowa mwachindunji mpaka mutafika 100.

Tiyerekeze kuti mwapeza olowa m'malo mwa M ndipo mtengowo uli ndi ma nodi a N. Kupeza mfundo yotsika mtengo (N) monga mtengo wam'mbuyomu. Koma mukapeza node iyi, mupeza olowa m'malo mwa M m'machitidwe okhudzana ndi omwe adalowa m'malo mwawo. Kusakaku kumangotengera M+ chipika(N) ntchito poyerekeza ndi ntchito za N pamtengo wam'mbuyo. Komanso, simuyenera kuwerenga mtengo wathunthu (node ​​za M + log (N) zokha, zomwe zikutanthauza kuti kugwiritsa ntchito disk kuchepera. Ngati M ali wamng'ono (mwachitsanzo mizere 200) ndipo N ndi yaikulu (mizere 1), padzakhala kusiyana KWAKULU.

Koma pali mavuto atsopano pano (kachiwiri!). Ngati muwonjezera kapena kufufuta mzere mu nkhokwe (ndipo chifukwa chake mumlozera wogwirizana wa B+Tree):

• muyenera kusunga dongosolo pakati pa node mkati mwa B + Tree, apo ayi simudzatha kupeza mfundo mkati mwa mtengo wosasankhidwa.
• muyenera kusunga milingo yocheperako mu B+ Tree, apo ayi nthawi ya O(logi(N)) imakhala O(N).

Mwa kuyankhula kwina, B + Tree iyenera kukhala yodzilamulira komanso yolinganiza. Mwamwayi, izi ndizotheka ndikuchotsa mwanzeru ndikuyika ntchito. Koma izi zimabwera pamtengo wake: zoyikapo ndikuzichotsa mumtengo wa B+ zimawononga O(logi(N)). N’chifukwa chake ena a inu mwamva zimenezo kugwiritsa ntchito ma index ambiri sikuli bwino. Zowona, mukuchedwa kuyika/kusintha/kuchotsa mzere patebulochifukwa nkhokweyo ikufunika kukonzanso ma index a tebulo pogwiritsa ntchito mtengo wa O(log(N)) pa index iliyonse. Kuphatikiza apo, kuwonjezera ma index kumatanthauza kuchuluka kwa ntchito transaction manager (zidzafotokozedwa kumapeto kwa nkhaniyo).

Kuti mumve zambiri, mutha kuwona nkhani ya Wikipedia B+Mtengo. Ngati mukufuna chitsanzo chokhazikitsa B + Tree mu database, yang'anani nkhaniyi и nkhaniyi kuchokera kwa wopanga wamkulu wa MySQL. Onse amayang'ana momwe InnoDB (injini ya MySQL) imagwirira ntchito ma index.

Zindikirani: Wowerenga anandiuza kuti, chifukwa cha kukhathamiritsa kwapang'onopang'ono, mtengo wa B + uyenera kukhala wokwanira.

Hashtable

Dongosolo lathu lomaliza la data ndi tebulo la hashi. Izi ndizothandiza kwambiri mukafuna kuyang'ana mwachangu zomwe zili zofunika. Kuphatikiza apo, kumvetsetsa tebulo la hashi kudzatithandiza kumvetsetsa ntchito yolumikizana ndi database yomwe imatchedwa hash join ( kujowina hash). Dongosolo la datali limagwiritsidwanso ntchito ndi nkhokwe kusunga zinthu zina zamkati (mwachitsanzo. loko tebulo kapena dziwe losungira, tiwona malingaliro onse awiriwa pambuyo pake).

Gome la hashi ndi dongosolo la data lomwe limapeza mwachangu chinthu chotengera fungulo lake. Kuti mupange tebulo la hash muyenera kufotokozera:

• fungulo za zinthu zanu
• ntchito ya hash za makiyi. Ma hashes ophatikizika amakupatsirani malo azinthu (zotchedwa magawo ).
• ntchito yofananiza makiyi. Mukapeza gawo lolondola, muyenera kupeza chinthu chomwe mukufuna m'gawolo pogwiritsa ntchito kufananitsa uku.

Chitsanzo chosavuta

Tiyeni titenge chitsanzo chomveka bwino:

Gome ili la hashi lili ndi magawo 10. Chifukwa ndine waulesi, ndimangojambula magawo 5 okha, koma ndikudziwa kuti ndinu anzeru, kotero ndikuloleni kuti mufanizire ena asanu nokha. Ndinagwiritsa ntchito hashi modulo 5 ya kiyi. Mwanjira ina, ndimasunga manambala omaliza a kiyi ya chinthucho kuti ndipeze gawo lake:

• ngati nambala yomaliza ndi 0, chinthucho chikugwera mu gawo 0,
• ngati nambala yomaliza ndi 1, chinthucho chikugwera mu gawo 1,
• ngati nambala yomaliza ndi 2, chinthucho chimagwera m'gawo 2,
• ...

Kuyerekeza komwe ndidagwiritsa ntchito ndikungofanana pakati pa magawo awiri.

Tiyerekeze kuti mukufuna kupeza gawo 78:

• Tebulo la hashi limawerengera nambala ya hashi ya 78, yomwe ndi 8.
• Gome la hashi limayang'ana gawo 8, ndipo chinthu choyamba chomwe amapeza ndi 78.
• Amakubwezerani chinthu 78
• Kusaka kumangotengera ntchito ziwiri zokha (imodzi kuwerengera mtengo wa hashi ndi ina kuyang'ana chinthu chomwe chili mkati mwa gawolo).

Tsopano tinene kuti mukufuna kupeza gawo 59:

• Tebulo la hashi limawerengera nambala ya hashi ya 59, yomwe ndi 9.
• Tsamba la hashi likufufuza mu gawo 9, chinthu choyamba chopezeka ndi 99. Popeza 99!=59, element 99 si chinthu chovomerezeka.
• Pogwiritsa ntchito malingaliro omwewo, chinthu chachiwiri (9), chachitatu (79), ..., chomaliza (29) chatengedwa.
• Chinthu sichinapezeke.
• Kusakaku kunawononga ntchito 7.

Ntchito yabwino ya hash

Monga mukuonera, kutengera mtengo womwe mukuyang'ana, mtengo wake siwofanana!

Ngati ine tsopano ndisintha hashi ntchito modulo 1 ya kiyi (ndiko, kutenga manambala 000 otsiriza), kuyang'ana kwachiwiri kumangotengera ntchito imodzi chifukwa mulibe zinthu mu gawo 000. Chovuta chenicheni ndicho kupeza ntchito yabwino ya hashi yomwe imapanga zidebe zomwe zili ndi zinthu zochepa kwambiri.

Mu chitsanzo changa, kupeza ntchito yabwino ya hashi ndikosavuta. Koma ichi ndi chitsanzo chophweka, kupeza ntchito yabwino ya hashi kumakhala kovuta kwambiri pamene fungulo lili:

• chingwe (mwachitsanzo - dzina lomaliza)
• Mizere iwiri (mwachitsanzo - dzina lomaliza ndi dzina loyamba)
• 2 mizere ndi tsiku (mwachitsanzo - dzina lomaliza, dzina loyamba ndi tsiku lobadwa)
• ...

Ndi ntchito yabwino ya hashi, kuyang'ana kwa tebulo la hashi kumawononga O(1).

Array vs tebulo la hashi

Bwanji osagwiritsa ntchito gulu?

Hmm, funso labwino.

• The hashi tebulo akhoza kukhala zodzaza pang'ono mu kukumbukira, ndipo magawo otsalawo akhoza kukhala pa disk.
• Ndi gulu muyenera kugwiritsa ntchito malo contiguous kukumbukira. Ngati mukukweza tebulo lalikulu ndizovuta kwambiri kupeza malo okwanira opitilira.
• Pa tebulo la hashi, mutha kusankha fungulo lomwe mukufuna (mwachitsanzo, dziko ndi dzina la munthu).

Kuti mudziwe zambiri, mukhoza kuwerenga nkhani za JavaHashMap, yomwe ndi kukhazikitsa bwino kwa tebulo la hashi; simuyenera kumvetsetsa Java kuti mumvetsetse mfundo zomwe zili m'nkhaniyi.

Source: www.habr.com