Habari Habr! Ninawasilisha kwa mawazo yako tafsiri ya makala
"Database ya uhusiano inafanyaje kazi".

Linapokuja suala la hifadhidata za uhusiano siwezi kusaidia lakini nadhani kuna kitu kinakosekana. Zinatumika kila mahali. Kuna hifadhidata nyingi tofauti zinazopatikana, kutoka kwa SQLite ndogo na muhimu hadi Teradata yenye nguvu. Lakini kuna nakala chache tu zinazoelezea jinsi hifadhidata inavyofanya kazi. Unaweza kujitafuta kwa kutumia "howdoesarelationaldatabasework" ili kuona ni matokeo machache. Aidha, makala hizi ni fupi. Ikiwa unatafuta teknolojia za hivi punde za buzzy (BigData, NoSQL au JavaScript), utapata nakala za kina zaidi zinazoelezea jinsi zinavyofanya kazi.

Je, hifadhidata za uhusiano ni za zamani sana na zinachosha kuelezewa nje ya kozi za chuo kikuu, karatasi za utafiti na vitabu?

Kama msanidi programu, sipendi kutumia kitu ambacho sielewi. Na ikiwa hifadhidata zimetumika kwa zaidi ya miaka 40, lazima kuwe na sababu. Kwa miaka mingi, nimetumia mamia ya saa kuelewa kwa kweli visanduku hivi vyeusi vya ajabu ambavyo mimi hutumia kila siku. Hifadhidata za uhusiano kuvutia sana kwa sababu wao kwa kuzingatia dhana zinazofaa na zinazoweza kutumika tena. Ikiwa ungependa kuelewa hifadhidata, lakini hujawahi kuwa na wakati au mwelekeo wa kutafakari mada hii pana, unapaswa kufurahia makala hii.

Ingawa kichwa cha kifungu hiki kiko wazi, Madhumuni ya kifungu hiki sio kuelewa jinsi ya kutumia hifadhidata. Kwa hivyo, unapaswa kujua jinsi ya kuandika ombi rahisi la uunganisho na maswali ya msingi MBICHI; vinginevyo unaweza usiielewi makala hii. Hilo ndilo jambo pekee unalohitaji kujua, nitaeleza mengine.

Nitaanza na misingi ya sayansi ya kompyuta, kama vile ugumu wa wakati wa algorithms (BigO). Najua baadhi yenu mnachukia dhana hii, lakini bila hiyo hutaweza kuelewa ugumu ndani ya hifadhidata. Kwa kuwa hii ni mada kubwa, Nitazingatia kile nadhani ni muhimu: jinsi hifadhidata inavyochakata SQL uchunguzi. Nitatambulisha tu dhana za msingi za hifadhidataili mwisho wa kifungu uwe na wazo la nini kinaendelea chini ya kofia.

Kwa kuwa hili ni makala ndefu na ya kiufundi ambayo inahusisha algoriti nyingi na miundo ya data, chukua muda wako kuisoma. Baadhi ya dhana inaweza kuwa ngumu kuelewa; unaweza kuziruka na bado ukapata wazo la jumla.

Kwa wenye ujuzi zaidi kati yenu, makala hii imegawanywa katika sehemu 3:

• Muhtasari wa vipengele vya hifadhidata vya kiwango cha chini na cha juu
• Muhtasari wa Mchakato wa Kuboresha Hoja
• Muhtasari wa Shughuli na Usimamizi wa Dimbwi la Buffer

Rudi kwenye misingi

Miaka iliyopita (katika galaksi ya mbali, mbali...), watengenezaji walipaswa kujua haswa idadi ya shughuli waliyokuwa wakiandika. Walijua algoriti zao na miundo ya data kwa moyo kwa sababu hawakuweza kumudu kupoteza CPU na kumbukumbu ya kompyuta zao polepole.

Katika sehemu hii, nitakukumbusha baadhi ya dhana hizi kwani ni muhimu kuelewa hifadhidata. Pia nitaanzisha dhana index database.

O(1) dhidi ya O(n2)

Siku hizi, watengenezaji wengi hawajali ugumu wa wakati wa algoriti... na wako sawa!

Lakini unaposhughulika na data nyingi (sizungumzi maelfu) au ikiwa unajitahidi katika milisekunde, inakuwa muhimu kuelewa wazo hili. Na kama unavyoweza kufikiria, hifadhidata zinapaswa kushughulika na hali zote mbili! Sitakufanya utumie muda zaidi ya lazima kupata uhakika. Hii itatusaidia kuelewa dhana ya uboreshaji kulingana na gharama baadaye (gharama msingi optimization).

Dhana

Utata wa wakati wa algorithm kutumika kuona itachukua muda gani kutekeleza algoriti kwa kiasi fulani cha data. Ili kuelezea uchangamano huu, tunatumia nukuu kubwa ya hisabati ya O. Nukuu hii inatumiwa na chaguo za kukokotoa zinazoelezea ni shughuli ngapi za algoriti inahitaji kwa idadi fulani ya ingizo.

Kwa mfano, ninaposema "algorithm hii ina utata O(some_function())", inamaanisha kwamba algoriti inahitaji utendakazi fulani(a_certain_amount_of_data) ili kuchakata kiasi fulani cha data.

Katika kesi hiyo, Sio idadi ya data ambayo ni muhimu **, vinginevyo ** jinsi idadi ya shughuli inavyoongezeka kwa kuongezeka kwa kiasi cha data. Utata wa muda hautoi idadi kamili ya shughuli, lakini ni njia nzuri ya kukadiria muda wa utekelezaji.

Katika grafu hii unaweza kuona idadi ya shughuli dhidi ya kiasi cha data ya ingizo kwa aina tofauti za ugumu wa wakati wa algorithm. Nilitumia kiwango cha logarithmic kuzionyesha. Kwa maneno mengine, kiasi cha data huongezeka haraka kutoka bilioni 1 hadi 1. Tunaweza kuona kwamba:

• O (1) au utata wa mara kwa mara unabaki kuwa sawa (vinginevyo haungeitwa ugumu wa kila wakati).
• O(logi(n)) inabaki kuwa chini hata na mabilioni ya data.
• Ugumu mbaya zaidi - O(n2), ambapo idadi ya shughuli hukua haraka.
• Shida zingine mbili huongezeka haraka sana.

mifano

Kwa kiasi kidogo cha data, tofauti kati ya O(1) na O(n2) haitumiki. Kwa mfano, tuseme una algoriti ambayo inahitaji kuchakata vipengele 2000.

• Algorithm ya O (1) itakugharimu operesheni 1
• Algorithm ya O(logi(n)) itakugharimu shughuli 7
• Kanuni ya O(n) itakugharimu utendakazi 2
• Kanuni ya O(n*logi(n)) itakugharimu utendakazi 14
• Kanuni ya O(n2) itakugharimu shughuli 4

Tofauti kati ya O(1) na O(n2) inaonekana kuwa kubwa (operesheni milioni 4) lakini utapoteza upeo wa ms 2, wakati tu wa kupepesa macho yako. Hakika, wasindikaji wa kisasa wanaweza kusindika mamia ya mamilioni ya shughuli kwa sekunde. Hii ndiyo sababu utendaji na uboreshaji si suala katika miradi mingi ya IT.

Kama nilivyosema, bado ni muhimu kujua wazo hili wakati wa kufanya kazi na idadi kubwa ya data. Ikiwa wakati huu algorithm italazimika kusindika vitu 1 (ambayo sio nyingi kwa hifadhidata):

• Algorithm ya O (1) itakugharimu operesheni 1
• Algorithm ya O(logi(n)) itakugharimu shughuli 14
• Kanuni ya O(n) itakugharimu utendakazi 1
• Algorithm ya O(n*logi(n)) itakugharimu utendakazi 14
• Kanuni ya O(n2) itakugharimu shughuli 1

Sijafanya hesabu, lakini ningesema kwamba kwa algorithm ya O (n2) unayo wakati wa kunywa kahawa (hata mbili!). Ukiongeza 0 nyingine kwa kiasi cha data, utakuwa na wakati wa kuchukua nap.

Hebu tuingie ndani zaidi

Kwa taarifa yako:

• Utaftaji mzuri wa jedwali la hashi hupata kipengee katika O(1).
• Kutafuta mti uliosawazishwa vizuri hutoa matokeo katika O(logi(n)).
• Kutafuta safu hutoa matokeo katika O(n).
• Algorithms bora zaidi za kupanga zina utata O(n*logi(n)).
• Algorithm mbaya ya kupanga ina utata O(n2).

Kumbuka: Katika sehemu zifuatazo tutaona algoriti hizi na miundo ya data.

Kuna aina kadhaa za ugumu wa wakati wa algorithm:

• wastani wa kesi
• bora kesi scenario
• na hali mbaya zaidi

Ugumu wa wakati mara nyingi ndio hali mbaya zaidi.

Nilikuwa nikizungumza tu juu ya ugumu wa wakati wa algorithm, lakini ugumu pia unatumika kwa:

• matumizi ya kumbukumbu ya algorithm
• algorithm ya matumizi ya diski I/O

Kwa kweli, kuna shida mbaya zaidi kuliko n2, kwa mfano:

• n4: hii ni mbaya! Baadhi ya algorithms zilizotajwa zina ugumu huu.
• 3n: hii ni mbaya zaidi! Moja ya algorithms tutakayoona katikati ya makala hii ina utata huu (na kwa kweli hutumiwa katika hifadhidata nyingi).
• factorial n: hutawahi kupata matokeo yako hata kwa kiasi kidogo cha data.
• nn: Ukikutana na ugumu huu, unapaswa kujiuliza ikiwa hii ni uwanja wako wa shughuli ...

Kumbuka: Sikukupa ufafanuzi halisi wa jina kubwa la O, wazo tu. Unaweza kusoma makala hii kwa Wikipedia kwa ufafanuzi halisi (asymptotic).

MergeSort

Unafanya nini unapohitaji kupanga mkusanyiko? Nini? Unaita kazi ya sort()... Sawa, jibu zuri... Lakini kwa hifadhidata, lazima uelewe jinsi aina hii () kazi inavyofanya kazi.

Kuna algorithms kadhaa nzuri za kupanga, kwa hivyo nitazingatia muhimu zaidi: kuunganisha aina. Huenda usielewe kwa nini kupanga data ni muhimu kwa sasa, lakini unapaswa baada ya sehemu ya uboreshaji wa hoja. Zaidi ya hayo, kuelewa unganisha aina kutatusaidia baadaye kuelewa operesheni ya kawaida ya kuunganisha hifadhidata inayoitwa kuunganisha kujiunga na (chama cha kuunganisha).

Unganisha

Kama algoriti nyingi muhimu, aina ya kuunganisha inategemea hila: kuchanganya safu 2 zilizopangwa za ukubwa N/2 hadi safu iliyopangwa ya kipengele cha N hugharimu utendakazi wa N pekee. Operesheni hii inaitwa kuunganisha.

Wacha tuone hii inamaanisha nini kwa mfano rahisi:

Takwimu hii inaonyesha kwamba ili kuunda safu ya mwisho ya vipengele 8, unahitaji tu kurudia mara moja zaidi ya safu 2 za vipengele 4. Kwa kuwa safu zote mbili za vipengele 4 tayari zimepangwa:

• 1) unalinganisha vitu vyote viwili vya sasa katika safu mbili (mwanzoni sasa = kwanza)
• 2) kisha chukua ndogo zaidi ili kuiweka katika safu ya vipengele 8
• 3) na uende kwa kipengee kinachofuata kwenye safu ambapo ulichukua kipengee kidogo zaidi
• na kurudia 1,2,3 hadi ufikie kipengele cha mwisho cha mojawapo ya safu.
• Kisha unachukua vipengele vilivyobaki vya safu nyingine ili kuziweka kwenye safu ya vipengele 8.

Hii inafanya kazi kwa sababu safu zote za vipengele 4 zimepangwa na kwa hivyo sio lazima "kurudi nyuma" katika safu hizo.

Sasa kwa kuwa tunaelewa hila, hapa kuna pseudocode yangu ya kuunganisha:

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 huvunja tatizo katika matatizo madogo na kisha hupata matokeo ya matatizo madogo ili kupata matokeo ya tatizo la awali (kumbuka: aina hii ya algorithm inaitwa divide and conquer). Ikiwa huelewi algorithm hii, usijali; Sikuielewa mara ya kwanza nilipoiona. Ikiwa inaweza kukusaidia, naona algorithm hii kama algorithm ya awamu mbili:

• Awamu ya mgawanyiko, ambapo safu imegawanywa katika safu ndogo
• Awamu ya kupanga ni ambapo safu ndogo huunganishwa (kwa kutumia muungano) kuunda safu kubwa.

Awamu ya mgawanyiko

Katika hatua ya mgawanyiko, safu imegawanywa katika safu za umoja katika hatua 3. Nambari rasmi ya hatua ni logi (N) (tangu N = 8, logi (N) = 3).

Ninajuaje hili?

Mimi ni genius! Kwa neno - hisabati. Wazo ni kwamba kila hatua inagawanya saizi ya safu asili kwa 2. Idadi ya hatua ni idadi ya nyakati ambazo unaweza kugawanya safu ya asili kuwa mbili. Huu ndio ufafanuzi kamili wa logarithm (msingi 2).

Awamu ya kupanga

Katika awamu ya kupanga, unaanza na safu za umoja (kipengele kimoja). Wakati wa kila hatua unatumia shughuli nyingi za kuunganisha na jumla ya gharama ni N = shughuli 8:

• Katika hatua ya kwanza una miunganisho 4 ambayo inagharimu shughuli 2 kila moja
• Katika hatua ya pili unayo viunganisho 2 ambavyo vinagharimu shughuli 4 kila moja
• Katika hatua ya tatu unayo unganisha 1 ambayo inagharimu shughuli 8

Kwa kuwa kuna hatua za logi(N), jumla ya gharama N * logi (N) shughuli.

Faida za kuunganisha aina

Kwa nini algorithm hii ina nguvu sana?

Kwa sababu:

• Unaweza kuibadilisha ili kupunguza alama ya kumbukumbu ili usitengeneze safu mpya lakini urekebishe moja kwa moja safu ya ingizo.

Kumbuka: aina hii ya algorithm inaitwa in-mahali (kupanga bila kumbukumbu ya ziada).

• Unaweza kuibadilisha ili kutumia nafasi ya diski na kiasi kidogo cha kumbukumbu kwa wakati mmoja bila kuingiza diski muhimu ya I/O. Wazo ni kupakia kwenye kumbukumbu sehemu zile tu ambazo zinachakatwa kwa sasa. Hii ni muhimu wakati unahitaji kupanga jedwali la gigabaiti nyingi na bafa ya kumbukumbu ya megabyte 100 pekee.

Kumbuka: aina hii ya algorithm inaitwa upangaji wa nje.

• Unaweza kuibadilisha ili iendeshe kwa michakato/nyuzi/seva nyingi.

Kwa mfano, aina ya kuunganisha iliyosambazwa ni mojawapo ya vipengele muhimu Hadoop (ambayo ni muundo katika data kubwa).

• Algorithm hii inaweza kugeuza risasi kuwa dhahabu (kweli!).

Algorithm hii ya kupanga hutumiwa katika hifadhidata nyingi (ikiwa sio zote), lakini sio pekee. Ikiwa unataka kujua zaidi, unaweza kusoma hii kazi ya utafiti, ambayo inajadili faida na hasara za algoriti za kawaida za kupanga hifadhidata.

Mpangilio, Mti na Jedwali la Hash

Sasa kwa kuwa tunaelewa wazo la ugumu wa wakati na kupanga, ninapaswa kukuambia kuhusu miundo 3 ya data. Hii ni muhimu kwa sababu wao ndio msingi wa hifadhidata za kisasa. Pia nitaanzisha dhana index database.

Mpangilio

Mkusanyiko wa pande mbili ndio muundo rahisi zaidi wa data. Jedwali linaweza kuzingatiwa kama safu. Kwa mfano:

Safu hii ya 2-dimensional ni jedwali iliyo na safu na safu:

• Kila mstari unawakilisha huluki
• Safu wima huhifadhi sifa zinazoelezea huluki.
• Kila safu huhifadhi data ya aina mahususi (jumla, mfuatano, tarehe...).

Hii ni rahisi kwa kuhifadhi na kuibua data, hata hivyo, wakati unahitaji kupata thamani maalum, hii haifai.

Kwa mfano, ikiwa ungetaka kupata watu wote wanaofanya kazi nchini Uingereza, ungehitaji kuangalia kila safu ili kubaini kama safu hiyo ni ya Uingereza. Itakugharimu miamala ya NAmbapo N - idadi ya mistari, ambayo sio mbaya, lakini kunaweza kuwa na njia ya haraka? Sasa ni wakati wa sisi kufahamu miti.

Kumbuka: Hifadhidata nyingi za kisasa hutoa safu zilizopanuliwa za kuhifadhi majedwali kwa ufanisi: majedwali yaliyopangwa-lundo na jedwali-zilizopangwa. Lakini hii haibadilishi tatizo la kupata haraka hali maalum katika kundi la nguzo.

Mti wa hifadhidata na faharisi

Mti wa utaftaji wa binary ni mti wa binary na mali maalum, ufunguo katika kila nodi lazima iwe:

• kubwa kuliko vitufe vyote vilivyohifadhiwa kwenye mti mdogo wa kushoto
• chini ya vitufe vyote vilivyohifadhiwa kwenye mti mdogo wa kulia

Wacha tuone hii inamaanisha nini kwa macho

Wazo

Mti huu una N = 15 vipengele. Wacha tuseme natafuta 208:

• Ninaanza kwenye mzizi ambao ufunguo wake ni 136. Tangu 136<208, ninaangalia subtree sahihi ya nodi 136.
• 398>208 kwa hivyo ninaangalia sehemu ndogo ya kushoto ya nodi 398
• 250>208 kwa hivyo ninaangalia sehemu ndogo ya kushoto ya nodi 250
• 200<208, kwa hivyo ninaangalia subtree sahihi ya nodi 200. Lakini 200 haina subtree sahihi, thamani haipo (kwa sababu ikiwa iko, itakuwa katika mti mdogo wa 200).

Sasa tuseme natafuta 40

• Ninaanzia kwenye mzizi ambao ufunguo wake ni 136. Tangu 136 > 40, ninatazama mti mdogo wa kushoto wa nodi 136.
• 80 > 40, kwa hivyo ninatazama sehemu ndogo ya kushoto ya nodi 80
• 40= 40, nodi ipo. Ninarudisha kitambulisho cha safu ndani ya nodi (haijaonyeshwa kwenye picha) na angalia kwenye jedwali kwa kitambulisho cha safu uliyopewa.
• Kujua kitambulisho cha safu mlalo huniruhusu kujua ni wapi data iko kwenye jedwali, ili niweze kuipata papo hapo.

Mwishowe, utafutaji wote utanigharimu idadi ya viwango ndani ya mti. Ikiwa unasoma sehemu kuhusu unganisha kwa uangalifu, unapaswa kuona kuwa kuna viwango vya logi(N). Inageuka, logi ya gharama ya utafutaji (N), Sio mbaya!

Turudi kwenye tatizo letu

Lakini hii ni ya kufikirika sana, kwa hivyo wacha turudi kwenye shida yetu. Badala ya nambari kamili, fikiria mfuatano unaowakilisha nchi ya mtu kwenye jedwali lililotangulia. Wacha tuseme una mti ambao una uwanja wa "nchi" (safu 3) ya jedwali:

• Ikiwa unataka kujua ni nani anayefanya kazi nchini Uingereza
• unatazama mti ili kupata nodi inayowakilisha Uingereza
• ndani ya "UKnode" utapata eneo la rekodi za mfanyakazi wa Uingereza.

Utafutaji huu utagharimu utendakazi wa logi(N) badala ya utendakazi wa N ikiwa unatumia safu moja kwa moja. Ulichowasilisha hivi punde kilikuwa index database.

Unaweza kuunda mti wa faharasa kwa kundi lolote la sehemu (kamba, nambari, mistari 2, nambari na mfuatano, tarehe...) mradi tu una chaguo la kukokotoa la kulinganisha vitufe (yaani vikundi vya sehemu) ili uweze kuweka. kuagiza kati ya funguo (ambayo ni kesi kwa aina yoyote ya msingi katika hifadhidata).

B+TreeIndex

Wakati mti huu unafanya kazi vizuri kwa kupata thamani maalum, kuna shida kubwa wakati unahitaji pata vitu vingi kati ya maadili mawili. Hii itagharimu O(N) kwa sababu itabidi uangalie kila nodi kwenye mti na uangalie ikiwa iko kati ya maadili haya mawili (k.m. na upitishaji ulioamuru wa mti). Kwa kuongezea, operesheni hii sio ya kirafiki ya diski I/O kwani lazima usome mti mzima. Tunahitaji kutafuta njia ya kutekeleza kwa ufanisi ombi la anuwai. Ili kutatua tatizo hili, hifadhidata za kisasa hutumia toleo lililobadilishwa la mti uliopita unaoitwa B + Tree. Katika mti B+:

• nodi za chini tu (majani) kuhifadhi habari (mahali pa safu mlalo kwenye jedwali linalohusiana)
• nodi zingine ziko hapa kwa uelekezaji kwa nodi sahihi wakati wa utafutaji.

Kama unaweza kuona, kuna nodi zaidi hapa (mara mbili). Hakika, una nodes za ziada, "node za uamuzi", ambazo zitakusaidia kupata node sahihi (ambayo huhifadhi eneo la safu kwenye meza inayohusishwa). Lakini ugumu wa utaftaji bado ni O(logi(N)) (kuna kiwango kimoja tu). Tofauti kubwa ni hiyo nodi katika ngazi ya chini zimeunganishwa na warithi wao.

Na Mti huu wa B+, ikiwa unatafuta maadili kati ya 40 na 100:

• Unahitaji tu kutafuta 40 (au dhamana ya karibu zaidi baada ya 40 ikiwa 40 haipo) kama ulivyofanya na mti uliopita.
• Kisha kukusanya warithi 40 kwa kutumia viungo vya mrithi wa moja kwa moja hadi ufikie 100.

Wacha tuseme unapata warithi wa M na mti una nodi za N. Kupata nodi maalum ya gharama ya logi (N) kama mti uliopita. Lakini mara tu unapopata nodi hii, utapata warithi wa M katika Operesheni za M na marejeleo ya warithi wao. Utafutaji huu unagharimu M+logi(N) pekee. shughuli ikilinganishwa na shughuli za N kwenye mti uliopita. Kwa kuongezea, sio lazima usome mti kamili (nodi za M + logi (N) pekee), ambayo inamaanisha utumiaji mdogo wa diski. Ikiwa M ni ndogo (kwa mfano safu 200) na N ni kubwa (safu 1), kutakuwa na tofauti KUBWA.

Lakini kuna matatizo mapya hapa (tena!). Ukiongeza au kufuta safu mlalo kwenye hifadhidata (na kwa hivyo katika faharasa inayohusika ya B+Tree):

• lazima udumishe mpangilio kati ya nodi ndani ya B+Tree, vinginevyo hutaweza kupata nodi ndani ya mti ambao haujapangwa.
• lazima uweke idadi ya chini iwezekanavyo ya viwango katika B+Tree, vinginevyo utata wa wakati wa O(logi(N)) unakuwa O(N).

Kwa maneno mengine, B + Tree lazima iwe ya kujitegemea na yenye usawa. Kwa bahati nzuri, hii inawezekana kwa utendakazi wa kufuta na kuingiza mahiri. Lakini hii inakuja kwa gharama: uingizaji na ufutaji katika mti wa B+ unagharimu O(logi(N)). Ndio maana baadhi yenu mmesikia hivyo kutumia faharisi nyingi sio wazo zuri. Kweli, unapunguza kasi ya kuingiza/kusasisha/kufuta safu mlalo kwenye jedwalikwa sababu hifadhidata inahitaji kusasisha faharisi za jedwali kwa kutumia operesheni ghali ya O(logi(N)) kwa kila faharisi. Zaidi ya hayo, kuongeza faharisi kunamaanisha mzigo zaidi wa kazi kwa meneja wa shughuli (itaelezewa mwishoni mwa kifungu).

Kwa maelezo zaidi, unaweza kuona nakala ya Wikipedia B+Mti. Ikiwa unataka mfano wa kutekeleza B+Tree kwenye hifadhidata, angalia nakala hii и nakala hii kutoka kwa msanidi programu anayeongoza wa MySQL. Wote wawili wanazingatia jinsi InnoDB (injini ya MySQL) inashughulikia faharisi.

Kumbuka: Msomaji aliniambia kuwa, kwa sababu ya uboreshaji wa kiwango cha chini, mti wa B+ unapaswa kusawazishwa kabisa.

Hashtable

Muundo wetu wa mwisho muhimu wa data ni jedwali la hashi. Hii ni muhimu sana unapotaka kutafuta thamani haraka. Zaidi ya hayo, kuelewa jedwali la hashi kutatusaidia baadaye kuelewa operesheni ya kawaida ya kuunganisha hifadhidata inayoitwa hash join ( Hash kujiunga) Muundo huu wa data pia hutumiwa na hifadhidata kuhifadhi baadhi ya vitu vya ndani (k.m. meza ya kufuli au bwawa la buffer, tutaona dhana hizi zote mbili baadaye).

Jedwali la hashi ni muundo wa data ambao hupata kipengele haraka kwa ufunguo wake. Ili kuunda meza ya hashi unahitaji kufafanua:

• ufunguo kwa vipengele vyako
• kazi ya hashi kwa funguo. Heshi muhimu zilizokokotwa hutoa eneo la vitu (vinaitwa sehemu ).
• kazi kwa kulinganisha funguo. Mara tu unapopata sehemu sahihi, lazima upate kipengee unachotafuta ndani ya sehemu kwa kutumia ulinganisho huu.

Mfano rahisi

Hebu tuchukue mfano wazi:

Jedwali hili la hashi lina sehemu 10. Kwa sababu mimi ni mvivu, nilipiga picha sehemu 5 tu, lakini najua wewe ni mwerevu, kwa hivyo nitakupa picha zingine 5 peke yako. Nilitumia kitendakazi cha hashi modulo 10 ya ufunguo. Kwa maneno mengine, mimi huhifadhi nambari ya mwisho tu ya kitufe cha kitu kupata sehemu yake:

• ikiwa nambari ya mwisho ni 0, kipengele kinaanguka katika sehemu 0,
• ikiwa nambari ya mwisho ni 1, kipengele kinaanguka katika sehemu 1,
• ikiwa nambari ya mwisho ni 2, kipengele kinaanguka katika eneo la 2,
• ...

Kazi ya kulinganisha niliyotumia ni usawa kati ya nambari mbili kamili.

Wacha tuseme unataka kupata kipengele cha 78:

• Jedwali la hashi hukokotoa msimbo wa hashi kwa 78, ambayo ni 8.
• Jedwali la hashi linaangalia sehemu ya 8, na kipengele cha kwanza kinachopata ni 78.
• Anakurudishia kipengee cha 78
• Utafutaji unagharimu shughuli 2 tu (moja kukokotoa thamani ya heshi na nyingine kutafuta kipengele ndani ya sehemu).

Sasa tuseme unataka kupata kipengele cha 59:

• Jedwali la hashi hukokotoa msimbo wa hashi kwa 59, ambayo ni 9.
• Jedwali la hashi hutafuta katika sehemu ya 9, kipengele cha kwanza kilichopatikana ni 99. Tangu 99!=59, kipengele cha 99 si kipengele halali.
• Kwa kutumia mantiki sawa, kipengele cha pili (9), cha tatu (79), ..., cha mwisho (29) kinachukuliwa.
• Kipengele hakijapatikana.
• Utafutaji uligharimu shughuli 7.

Utendaji mzuri wa hashi

Kama unavyoona, kulingana na thamani unayotafuta, gharama sio sawa!

Ikiwa sasa nitabadilisha moduli ya utendakazi wa hashi 1 ya ufunguo (yaani, kuchukua tarakimu 000 za mwisho), utafutaji wa pili unagharimu operesheni 000 pekee kwani hakuna vipengele katika sehemu 6. Changamoto halisi ni kupata utendaji mzuri wa heshi ambao utaunda ndoo zilizo na idadi ndogo sana ya vipengee.

Katika mfano wangu, kupata kazi nzuri ya hashi ni rahisi. Lakini huu ni mfano rahisi, kupata kazi nzuri ya hashi ni ngumu zaidi wakati ufunguo ni:

• kamba (kwa mfano - jina la mwisho)
• Mistari 2 (kwa mfano - jina la mwisho na jina la kwanza)
• Mistari 2 na tarehe (kwa mfano - jina la mwisho, jina la kwanza na tarehe ya kuzaliwa)
• ...

Kwa utendaji mzuri wa heshi, ukaguzi wa jedwali la hashi hugharimu O(1).

Mkusanyiko dhidi ya jedwali la hashi

Kwa nini usitumie safu?

Hmm, swali zuri.

• Jedwali la hashi linaweza kuwa imejaa kwa sehemu kwenye kumbukumbu, na sehemu zilizobaki zinaweza kubaki kwenye diski.
• Kwa safu lazima utumie nafasi iliyounganishwa kwenye kumbukumbu. Ikiwa unapakia meza kubwa ni vigumu sana kupata nafasi endelevu ya kutosha.
• Kwa jedwali la hashi, unaweza kuchagua ufunguo unaotaka (kwa mfano, nchi na jina la mwisho la mtu).

Kwa habari zaidi, unaweza kusoma makala kuhusu JavaHashMap, ambayo ni utekelezaji mzuri wa jedwali la hashi; hauitaji kuelewa Java ili kuelewa dhana zilizofunikwa katika nakala hii.

Chanzo: mapenzi.com