Ħej Habr! Nippreżenta għall-attenzjoni tiegħek it-traduzzjoni tal-artiklu
"Kif taħdem database relazzjonali".

Fejn jidħlu databases relazzjonali ma nistax ma naħseb li hemm xi ħaġa nieqsa. Jintużaw kullimkien. Hemm ħafna databases differenti disponibbli, mill-SQLite żgħir u utli sa Teradata qawwija. Iżda hemm biss ftit artikoli li jispjegaw kif taħdem id-database. Tista' tfittex għalik innifsek billi tuża "howdoesarelationaldatabasework" biex tara kemm hemm ftit riżultati. Barra minn hekk, dawn l-artikoli huma qosra. Jekk qed tfittex l-aħħar teknoloġiji buzzy (BigData, NoSQL jew JavaScript), issib artikli aktar fil-fond li jispjegaw kif jaħdmu.

Id-databases relazzjonali huma qodma wisq u wisq boring biex jiġu spjegati barra mill-korsijiet universitarji, karti ta’ riċerka u kotba?

Bħala żviluppatur, ddejjaqni nuża xi ħaġa li ma nifhimx. U jekk id-databases ilhom jintużaw għal aktar minn 40 sena, għandu jkun hemm raġuni. Matul is-snin, qattajt mijiet ta’ sigħat biex nifhem tassew dawn il-kaxxi suwed strambi li nuża kuljum. Databases relazzjonali interessanti ħafna għax huma ibbażata fuq kunċetti utli u li jistgħu jerġgħu jintużaw. Jekk int interessat li tifhem database, iżda qatt ma kellek il-ħin jew l-inklinazzjoni biex tidħol f'dan is-suġġett wiesa ', għandek tgawdi dan l-artikolu.

Għalkemm it-titlu ta’ dan l-artikolu huwa espliċitu, l-iskop ta' dan l-artikolu mhuwiex li tifhem kif tuża d-database. Għalhekk, diġà għandek tkun taf kif tikteb talba ta 'konnessjoni sempliċi u mistoqsijiet bażiċi MHUX RAFFINAT; inkella tista' ma tifhimx dan l-artikolu. Dik hija l-unika ħaġa li trid tkun taf, nispjega l-bqija.

Nibda b'xi punti bażiċi tax-xjenza tal-kompjuter, bħall-kumplessità tal-ħin tal-algoritmi (BigO). Naf li xi wħud minnkom tobgħodu dan il-kunċett, iżda mingħajru ma tkunx tista' tifhem l-intricacies ġewwa d-database. Peress li dan huwa suġġett kbir, Niffoka fuq dak li naħseb li huwa importanti: kif tipproċessa d-database SQL inkjesta. Se nintroduċi biss kunċetti bażiċi tad-databasesabiex fl-aħħar ta 'l-artiklu ikollok idea ta' x'qed jiġri taħt il-barnuża.

Peress li dan huwa artikolu twil u tekniku li jinvolvi ħafna algoritmi u strutturi tad-dejta, ħu l-ħin tiegħek biex taqrah. Xi kunċetti jistgħu jkunu diffiċli biex jinftiehmu; tista' taqbeżhom u xorta tikseb l-idea ġenerali.

Għal dawk l-aktar infurmati fostkom, dan l-artikolu huwa maqsum fi 3 partijiet:

Ħarsa ġenerali tal-komponenti tad-database ta 'livell baxx u ta' livell għoli
Ħarsa ġenerali lejn il-Proċess ta' Ottimizzazzjoni tal-Mistoqsijiet
Ħarsa ġenerali lejn il-Ġestjoni ta' Transazzjonijiet u Buffer Pool

Lura għall-affarijiet bażiċi

Snin ilu (f'galaxie 'l bogħod, 'il bogħod...), l-iżviluppaturi kellhom ikunu jafu eżattament in-numru ta' operazzjonijiet li kienu qed jikkodifikaw. Huma kienu jafu bl-amment l-algoritmi u l-istrutturi tad-dejta tagħhom għax ma setgħux jaffordjaw li jaħlu s-CPU u l-memorja tal-kompjuters bil-mod tagħhom.

F'din il-parti, infakkarkom f'xi wħud minn dawn il-kunċetti peress li huma essenzjali biex tifhem id-database. Se nintroduċi wkoll il-kunċett indiċi tad-database.

O(1) vs O(n2)

Illum il-ġurnata, ħafna żviluppaturi ma jimpurtahomx mill-kumplessità tal-ħin tal-algoritmi... u għandhom raġun!

Imma meta tkun qed tittratta ma 'ħafna dejta (ma nkunx qed nitkellem eluf) jew jekk qed titħabat f'millisekondi, isir kritiku li tifhem dan il-kunċett. U kif tista' timmaġina, id-databases għandhom jittrattaw iż-żewġ sitwazzjonijiet! Mhux se nġiegħlek tqatta’ aktar ħin milli meħtieġ biex tgħaddi l-punt. Dan se jgħinna nifhmu l-kunċett ta 'ottimizzazzjoni bbażata fuq l-ispiża aktar tard (ispiża bbażata ottimizzazzjoni).

Kunċett

Il-kumplessità tal-ħin tal-algoritmu użati biex tara kemm algoritmu se jieħu biex jitlesta għal ammont partikolari ta 'data. Biex niddeskrivu din il-kumplessità, nużaw notazzjoni matematika kbira O. Din in-notazzjoni tintuża b'funzjoni li tiddeskrivi kemm-il operazzjonijiet jeħtieġ algoritmu għal numru partikolari ta' inputs.

Pereżempju, meta ngħid "dan l-algoritmu għandu kumplessità O(some_function())", dan ifisser li l-algoritmu jeħtieġ xi operazzjonijiet (a_certain_amount_of_data) biex jipproċessa ċertu ammont ta 'data.

F'dan il-każ, Mhux l-ammont ta' data li jgħodd**, inkella ** kif in-numru ta' operazzjonijiet jiżdied maż-żieda fil-volum tad-dejta. Il-kumplessità tal-ħin ma tipprovdix numru eżatt ta’ operazzjonijiet, iżda hija mod tajjeb biex jiġi stmat il-ħin tal-eżekuzzjoni.

F'dan il-graff tista 'tara n-numru ta' operazzjonijiet kontra l-ammont ta 'dejta ta' input għal tipi differenti ta 'kumplessitajiet tal-ħin tal-algoritmu. Jien użajt skala logaritmika biex nurihom. Fi kliem ieħor, l-ammont ta 'dejta malajr jiżdied minn biljun għal 1. Nistgħu naraw li:

O(1) jew kumplessità kostanti tibqa' kostanti (inkella ma tissejjaħx kumplessità kostanti).
O(log(n)) jibqa’ baxx anke b’biljuni ta’ data.
L-agħar diffikultà - O(n2), fejn in-numru ta' operazzjonijiet jikber malajr.
Iż-żewġ kumplikazzjonijiet l-oħra jiżdiedu daqstant malajr.

eżempji

B'ammont żgħir ta 'dejta, id-differenza bejn O (1) u O (n2) hija negliġibbli. Pereżempju, ejja ngħidu li għandek algoritmu li jeħtieġ li jipproċessa 2000 element.

L-algoritmu O(1) jiswik operazzjoni waħda
L-algoritmu O(log(n)) jiswik 7 operazzjonijiet
L-algoritmu O(n) jiswik 2 operazzjoni
L-algoritmu O(n*log(n)) jiswik 14 operazzjoni
L-algoritmu O(n2) jiswik 4 operazzjoni

Id-differenza bejn O(1) u O(n2) tidher kbira (4 miljun operazzjoni) iżda titlef massimu ta’ 2 ms, ħin biss biex teptip għajnejk. Tabilħaqq, proċessuri moderni jistgħu jipproċessaw mijiet ta’ miljuni ta’ operazzjonijiet kull sekonda. Huwa għalhekk li l-prestazzjoni u l-ottimizzazzjoni mhumiex kwistjoni f'ħafna proġetti tal-IT.

Kif għedt, xorta huwa importanti li tkun taf dan il-kunċett meta taħdem ma 'ammonti kbar ta' dejta. Jekk din id-darba l-algoritmu jrid jipproċessa 1 element (li mhux daqshekk għal database):

L-algoritmu O(1) jiswik operazzjoni waħda
L-algoritmu O(log(n)) jiswik 14 operazzjonijiet
L-algoritmu O(n) jiswik 1 operazzjoni
L-algoritmu O(n*log(n)) jiswik 14 operazzjoni
L-algoritmu O(n2) jiswik 1 operazzjoni

Il-matematika ma għamiltx, imma ngħid li bl-algoritmu O(n2) għandek ħin biex tixrob kafè (anke tnejn!). Jekk iżżid 0 ieħor mal-volum tad-dejta, ser ikollok ħin biex tieħu nap.

Ejja mmorru aktar fil-fond

Għall-informazzjoni tiegħek:

Lookup ta 'tabella hash tajba ssib element f'O(1).
It-tfittxija ta' siġra bbilanċjata tajjeb tipproduċi riżultati f'O(log(n)).
It-tfittxija ta' firxa tipproduċi riżultati f'O(n).
L-aħjar algoritmi ta' għażla għandhom kumplessità O(n*log(n)).
Algoritmu ta' għażla ħażina għandu kumplessità O(n2).

Nota: Fil-partijiet li ġejjin se naraw dawn l-algoritmi u l-istrutturi tad-dejta.

Hemm diversi tipi ta' kumplessità tal-ħin tal-algoritmu:

xenarju tal-każ medju
l-aħjar xenarju
u l-agħar xenarju

Il-kumplessità tal-ħin hija ħafna drabi l-agħar xenarju.

Kont qed nitkellem biss dwar il-kumplessità tal-ħin tal-algoritmu, iżda l-kumplessità tapplika wkoll għal:

konsum tal-memorja tal-algoritmu
algoritmu tal-konsum tad-disk I/O

Naturalment, hemm kumplikazzjonijiet agħar minn n2, pereżempju:

n4: dan huwa terribbli! Uħud mill-algoritmi msemmija għandhom din il-kumplessità.
3n: dan huwa saħansitra agħar! Wieħed mill-algoritmi li se naraw f'nofs dan l-artikolu għandu din il-kumplessità (u fil-fatt jintuża f'ħafna databases).
factorial n: qatt mhu se tikseb ir-riżultati tiegħek anki b'ammont żgħir ta 'data.
nn: Jekk tiltaqa' ma' din il-kumplessità, għandek tistaqsi lilek innifsek jekk dan hux verament il-qasam ta' attività tiegħek...

Nota: I ma tajtx id-definizzjoni attwali tad-denominazzjoni O kbira, biss idea. Tista' taqra dan l-artikolu fuq Wikipedija għad-definizzjoni reali (asintotika).

MergeSort

X'tagħmel meta jkollok bżonn issolvi kollezzjoni? Xiex? Int issejjaħ il-funzjoni sort()... Ok, tweġiba tajba... Imma għal database, trid tifhem kif taħdem din il-funzjoni sort().

Hemm diversi algoritmi ta' għażla tajbin, għalhekk ser niffoka fuq l-aktar importanti: jingħaqdu sort. Inti tista 'ma tifhimx għaliex issortjar data hija utli bħalissa, imma għandek wara l-parti ta' ottimizzazzjoni query. Barra minn hekk, il-fehim tal-għaqda sort se jgħinna aktar tard nifhmu l-operazzjoni komuni ta' tingħaqad tad-database imsejħa jingħaqdu jingħaqdu (assoċjazzjoni ta' għaqda).

Għaqda

Bħal ħafna algoritmi utli, merge sort tiddependi fuq trick: li tgħaqqad 2 arrays magħżula ta 'daqs N/2 f'array magħżula N-element jiswa N operazzjonijiet biss. Din l-operazzjoni tissejjaħ għaqda.

Ejja naraw xi jfisser dan b'eżempju sempliċi:

Din il-figura turi li biex tibni l-array finali ta '8 elementi magħżula, għandek bżonn biss li ttenni darba fuq l-arrays ta' 2 4 elementi. Peress li ż-żewġ matriċi ta' 4 elementi huma diġà magħżula:

1) tqabbel iż-żewġ elementi kurrenti f'żewġ matriċi (fil-bidu kurrenti = l-ewwel)
2) imbagħad ħu l-iżgħar waħda biex tpoġġiha f'firxa ta '8 elementi
3) u mxi għall-element li jmiss fil-firxa fejn ħadt l-iżgħar element
u rrepeti 1,2,3 sakemm tilħaq l-aħħar element ta 'waħda mill-arrays.
Imbagħad tieħu l-elementi li jifdal tal-firxa l-oħra biex tpoġġihom f'firxa ta '8 elementi.

Dan jaħdem minħabba li ż-żewġ matriċi ta' 4 elementi huma magħżula u għalhekk m'għandekx għalfejn "tmur lura" f'dawk l-arrays.

Issa li nifhmu l-trick, hawn huwa l-psewdocode tiegħi għall-għaqda:

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 taqsam problema fi problemi iżgħar u mbagħad issib ir-riżultati tal-problemi iżgħar biex tikseb ir-riżultat tal-problema oriġinali (nota: dan it-tip ta 'algoritmu jissejjaħ divide and conquer). Jekk ma tifhimx dan l-algoritmu, tinkwetax; Ma fhimtx l-ewwel darba li rajtha. Jekk tista 'tgħinek, nara dan l-algoritmu bħala algoritmu f'żewġ fażijiet:

Fażi ta 'diviżjoni, fejn il-firxa hija maqsuma f'arrays iżgħar
Il-fażi tal-issortjar hija fejn matriċi żgħar huma kkombinati (bl-użu tal-unjoni) biex jiffurmaw firxa akbar.

Fażi ta' diviżjoni

Fl-istadju tad-diviżjoni, il-firxa hija maqsuma f'arrays unitarji fi 3 passi. In-numru formali ta' passi huwa log(N) (billi N=8, log(N) = 3).

Kif inkun naf dan?

Jien ġenju! F'kelma waħda - il-matematika. L-idea hija li kull pass jaqsam id-daqs tal-firxa oriġinali b'2. In-numru ta 'passi huwa n-numru ta' drabi li tista 'taqsam l-array oriġinali fi tnejn. Din hija d-definizzjoni eżatta ta' logaritmu (bażi 2).

Fażi tal-issortjar

Fil-fażi tal-issortjar, tibda b'arrays unitarji (b'element wieħed). Matul kull pass inti tapplika operazzjonijiet ta' amalgamazzjoni multipli u l-ispiża totali hija N = 8 operazzjonijiet:

Fl-ewwel stadju għandek 4 merges li jiswew 2 operazzjonijiet kull wieħed
Fit-tieni pass għandek 2 merges li jiswew 4 operazzjonijiet kull wieħed
Fit-tielet pass għandek 1 merge li tiswa 8 operazzjonijiet

Peress li hemm passi log(N), spiża totali N * log(N) operazzjonijiet.

Vantaġġi ta 'għaqda sort

Għaliex dan l-algoritmu huwa daqshekk qawwi?

Minħabba li:

Tista' tibdelha biex tnaqqas il-footprint tal-memorja sabiex ma toħloqx arrays ġodda iżda timmodifika direttament l-array input.

Nota: dan it-tip ta 'algoritmu jissejjaħ in-post (issortjar mingħajr memorja addizzjonali).

Tista' tibdelha biex tuża spazju fuq id-diska u ammont żgħir ta' memorja fl-istess ħin mingħajr ma ġġarrab overhead sinifikanti ta' I/O tad-diska. L-idea hija li tgħabbi fil-memorja biss dawk il-partijiet li bħalissa qed jiġu pproċessati. Dan huwa importanti meta jkollok bżonn issolvi tabella b'ħafna gigabyte b'buffer tal-memorja ta' 100 megabyte biss.

Nota: dan it-tip ta 'algoritmu jissejjaħ sort esterna.

Tista' tibdelha biex taħdem fuq proċessi/ħjut/servers multipli.

Pereżempju, it-tip ta' amalgamazzjoni mqassma huwa wieħed mill-komponenti ewlenin Hadoop (li hija struttura fil-big data).

Dan l-algoritmu jista 'jbiddel iċ-ċomb f'deheb (verament!).

Dan l-algoritmu tal-issortjar jintuża fil-biċċa l-kbira tad-databases (jekk mhux kollha), iżda mhuwiex l-uniku wieħed. Jekk trid tkun taf aktar, tista 'taqra dan xogħol ta’ riċerka, li jiddiskuti l-vantaġġi u l-iżvantaġġi ta 'algoritmi komuni ta' għażla ta 'database.

Tabella Array, Siġra u Hash

Issa li nifhmu l-idea tal-kumplessità tal-ħin u l-issortjar, għandi ngħidlek dwar 3 strutturi tad-dejta. Dan huwa importanti għaliex huma huma l-bażi ta' databases moderni. Se nintroduċi wkoll il-kunċett indiċi tad-database.

Array

Array bidimensjonali hija l-aktar struttura tad-dejta sempliċi. Tabella tista' titqies bħala firxa. Pereżempju:

Din il-firxa bi-dimensjonali hija tabella b'ringieli u kolonni:

Kull linja tirrappreżenta entità
Il-kolonni jaħżnu proprjetajiet li jiddeskrivu l-entità.
Kull kolonna taħżen data ta’ tip speċifiku (numru sħiħ, string, data...).

Dan huwa konvenjenti għall-ħażna u l-viżwalizzazzjoni tad-dejta, madankollu, meta jkollok bżonn issib valur speċifiku, dan mhux adattat.

Pereżempju, jekk ridt issib il-ġuvini kollha li jaħdmu fir-Renju Unit, ikollok bżonn tħares lejn kull ringiela biex tiddetermina jekk dik ir-ringiela tappartjenix għar-Renju Unit. Se jiswik N transazzjonijietfejn N - numru ta 'linji, li mhux ħażin, iżda jista' jkun hemm mod aktar mgħaġġel? Issa wasal iż-żmien li nsiru familjari mas-siġar.

Nota: Il-biċċa l-kbira tad-databases moderni jipprovdu arrays estiżi għall-ħażna ta' tabelli b'mod effiċjenti: heap-organizedtables u index-organizedtables. Iżda dan ma jbiddilx il-problema li tinstab malajr kundizzjoni speċifika fi grupp ta 'kolonni.

Siġra tad-database u indiċi

Siġra tat-tfittxija binarja hija siġra binarja bi proprjetà speċjali, iċ-ċavetta f'kull nodu għandha tkun:

akbar miċ-ċwievet kollha maħżuna fis-subtree tax-xellug
inqas minn ċwievet kollha maħżuna fis-subtree dritt

Ejja naraw xi jfisser dan viżwalment

Idea

Din is-siġra għandha N = 15-il element. Ejja ngħidu li qed infittex 208:

Nibda mill-għerq li ċ-ċavetta tagħha hija 136. Peress 136<208, inħares lejn is-subtree tal-lemin tan-node 136.
398>208 għalhekk qed inħares lejn is-subtree tax-xellug tan-node 398
250>208 għalhekk qed inħares lejn is-subtree tax-xellug tan-node 250
200<208, għalhekk qed inħares lejn is-subtree dritt tan-node 200. Imma 200 m'għandu l-ebda subtree dritt, valur ma jeżistix (għax jekk teżisti, tkun fis-subtree tal-lemin 200).

Issa ejja ngħidu li qed infittex 40

Nibda mill-għerq li ċ-ċavetta tagħha hija 136. Peress li 136> 40, inħares lejn is-subtree tax-xellug tan-node 136.
80 > 40, għalhekk qed inħares lejn is-subtree tax-xellug tan-node 80
40= 40, node jeżisti. Nirkupra l-ID tar-ringiela ġewwa n-node (mhux murija fl-istampa) u nfittex fit-tabella għall-ID tar-ringiela mogħtija.
Li tkun taf l-ID tar-ringiela tippermettili nkun naf eżatt fejn tinsab id-dejta fit-tabella, sabiex inkun nista' nirkupraha istantanjament.

Fl-aħħar, iż-żewġ tfittxijiet se jiswieli n-numru ta 'livelli ġewwa s-siġra. Jekk taqra bir-reqqa l-parti dwar l-għaqda sort, għandek tara li hemm livelli log(N). Jirriżulta, reġistru tal-ispiża tat-tfittxija (N), mhux ħażin!

Ejja nerġgħu lura għall-problema tagħna

Iżda dan huwa astratt ħafna, allura ejja nerġgħu lura għall-problema tagħna. Minflok numru sħiħ sempliċi, immaġina string li tirrappreżenta l-pajjiż ta 'xi ħadd fit-tabella ta' qabel. Ejja ngħidu li għandek siġra li fiha l-qasam "pajjiż" (kolonna 3) tat-tabella:

Jekk trid tkun taf min jaħdem fir-Renju Unit
tħares lejn is-siġra biex tikseb in-nodu li jirrappreżenta l-Gran Brittanja
ġewwa "UKnode" issib il-post tar-rekords tal-ħaddiema tar-Renju Unit.

Din it-tfittxija tiswa log(N) operazzjonijiet minflok N operazzjonijiet jekk tuża l-array direttament. Dak li għadek kif ippreżentajt kien indiċi tad-database.

Tista' tibni siġra ta' indiċi għal kwalunkwe grupp ta' oqsma (sekwenza, numru, 2 linji, numru u spag, data...) sakemm ikollok funzjoni li tqabbel ċwievet (jiġifieri gruppi ta' oqsma) sabiex tkun tista' tissettja ordni fost iċ-ċwievet (li huwa l-każ għal kwalunkwe tip bażiku fid-database).

B+TreeIndex

Filwaqt li din is-siġra taħdem tajjeb biex tikseb valur speċifiku, hemm problema KBIRA meta jkollok bżonn tikseb elementi multipli bejn żewġ valuri. Dan se jiswa O(N) għax ikollok tħares lejn kull nodu fis-siġra u tivverifika jekk huwiex bejn dawn iż-żewġ valuri (eż. bi traversal ordnat tas-siġra). Barra minn hekk, din l-operazzjoni mhix faċli għall-I/O tad-disk peress li trid taqra s-siġra kollha. Irridu nsibu mod kif noħorġu b'mod effiċjenti talba tal-firxa. Biex issolvi din il-problema, databases moderni jużaw verżjoni modifikata tas-siġra preċedenti msejħa B+Tree. Fi siġra B+Tree:

in-nodi l-aktar baxxi biss (weraq) taħżen l-informazzjoni (post tar-ringieli fit-tabella relatata)
il-bqija tan-nodi huma hawn għar-rotot għan-nodu korrett waqt it-tfittxija.

Kif tistgħu taraw, hawn aktar nodi (darbtejn). Tabilħaqq, għandek nodi addizzjonali, "nodi ta 'deċiżjoni", li jgħinuk issib in-nodu korrett (li jaħżen il-post tar-ringieli fit-tabella assoċjata). Iżda l-kumplessità tat-tfittxija għadha O(log(N)) (hemm biss livell wieħed aktar). Id-differenza kbira hija dik nodi fil-livell aktar baxx huma konnessi mas-suċċessuri tagħhom.

B'din is-Siġra B+, jekk qed tfittex valuri bejn 40 u 100:

Għandek bżonn biss li tfittex 40 (jew l-eqreb valur wara 40 jekk 40 ma teżistix) bħalma għamilt mas-siġra ta 'qabel.
Imbagħad iġbor 40 eredi billi tuża links diretti tal-eredi sakemm tilħaq 100.

Ejja ngħidu li ssib M suċċessuri u s-siġra għandha N nodi. Is-sejba ta 'node speċifiku jiswa log(N) bħas-siġra ta' qabel. Imma ladarba tikseb dan in-nodu, ikollok suċċessuri M f'operazzjonijiet M b'referenzi għas-suċċessuri tagħhom. Din it-tfittxija tiswa biss M+log(N) operazzjonijiet meta mqabbla ma 'N operazzjonijiet fuq is-siġra ta' qabel. Barra minn hekk, m'għandekx għalfejn taqra s-siġra sħiħa (nodes M+log(N) biss), li jfisser inqas użu tad-disk. Jekk M huwa żgħir (eż. 200 ringiela) u N huwa kbir (1 ringiela), ikun hemm differenza KBIRA.

Iżda hawn problemi ġodda (għal darb'oħra!). Jekk iżżid jew tħassar ringiela fid-database (u għalhekk fl-indiċi B+Tree assoċjat):

trid iżżomm l-ordni bejn in-nodi ġewwa B + Tree, inkella ma tkunx tista 'ssib in-nodi ġewwa siġra mhux magħżula.
trid iżżomm in-numru minimu possibbli ta 'livelli f'B + Tree, inkella l-kumplessità tal-ħin O (log (N)) issir O (N).

Fi kliem ieħor, B + Tree għandu jkun awto-ordni u bilanċjat. Fortunatament, dan huwa possibbli b'operazzjonijiet intelliġenti ta 'tħassir u daħħal. Iżda dan jiġi bi spiża: inserzjonijiet u tħassir f'siġra B+ jiswew O(log(N)). Huwa għalhekk li xi wħud minnkom smajtu hekk li tuża wisq indiċi mhix idea tajba. Tassew, qed jonqos malajr daħħal/aġġornament/tħassir ta 'ringiela f'tabellaminħabba li d-database jeħtieġ li taġġorna l-indiċi tat-tabella billi tuża operazzjoni O(log(N)) għalja għal kull indiċi. Barra minn hekk, iż-żieda ta 'indiċi tfisser aktar xogħol għal maniġer tat-tranżazzjonijiet (se jiġi deskritt fl-aħħar tal-artiklu).

Għal aktar dettalji, tista’ tara l-artiklu tal-Wikipedija fuq B+siġra. Jekk trid eżempju ta 'implimentazzjoni ta' B+Tree f'database, agħti ħarsa dan l-artikolu и dan l-artikolu minn żviluppatur ewlieni tal-MySQL. It-tnejn jiffokaw fuq kif InnoDB (il-magna MySQL) timmaniġġja l-indiċi.

Nota: Qarrej qalli li, minħabba ottimizzazzjonijiet ta 'livell baxx, is-siġra B + għandha tkun kompletament ibbilanċjata.

Hashtable

L-aħħar struttura tad-dejta importanti tagħna hija t-tabella tal-hash. Dan huwa utli ħafna meta trid tfittex malajr il-valuri. Barra minn hekk, il-fehim ta 'tabella hash se jgħinna aktar tard nifhmu operazzjoni komuni ta' rabta ta' database msejħa hash join ( hash join). Din l-istruttura tad-dejta tintuża wkoll mid-database biex taħżen xi affarijiet interni (eż. lock tabella jew buffer pool, naraw dawn iż-żewġ kunċetti aktar tard).

Tabella hash hija struttura tad-dejta li malajr issib element permezz taċ-ċavetta tagħha. Biex tibni tabella hash trid tiddefinixxi:

clue għall-elementi tiegħek
funzjoni hash għaċ-ċwievet. Il-hashes taċ-ċavetta kkalkulati jagħtu l-post tal-elementi (imsejħa segmenti ).
funzjoni għat-tqabbil taċ-ċwievet. Ladarba tkun sibt is-segment korrett, trid issib l-element li qed tfittex fi ħdan is-segment billi tuża dan il-paragun.

Eżempju sempliċi

Ejja nieħdu eżempju ċar:

Din it-tabella tal-hash għandha 10 segmenti. Minħabba li jien għażżien, jiena stampajt 5 segmenti biss, imma naf li int intelliġenti, allura nħallik stampa l-5 l-oħra waħdek. Jien użajt funzjoni hash modulo 10 taċ-ċavetta. Fi kliem ieħor, naħżen biss l-aħħar ċifra taċ-ċavetta tal-element biex insib is-segment tiegħu:

jekk l-aħħar ċifra hija 0, l-element jaqa' fis-segment 0,
jekk l-aħħar ċifra hija 1, l-element jaqa' fis-segment 1,
jekk l-aħħar ċifra hija 2, l-element jaqa' fiż-żona 2,
...

Il-funzjoni ta' paragun li użajt hija sempliċement ugwaljanza bejn żewġ numri interi.

Ejja ngħidu li trid tikseb l-element 78:

It-tabella tal-hash tikkalkula l-kodiċi tal-hash għal 78, li huwa 8.
It-tabella tal-hash tħares lejn is-segment 8, u l-ewwel element li ssib huwa 78.
Hija tirritorna l-oġġett 78 lilek
It-tfittxija tiswa biss 2 operazzjonijiet (wieħed biex jikkalkula l-valur tal-hash u l-ieħor biex ifittex l-element fi ħdan is-segment).

Issa ejja ngħidu li trid tikseb l-element 59:

It-tabella tal-hash tikkalkula l-kodiċi tal-hash għal 59, li huwa 9.
It-tfittxijiet tat-tabella tal-hash fis-segment 9, l-ewwel element misjub huwa 99. Peress li 99!=59, l-element 99 mhuwiex element validu.
Bl-użu tal-istess loġika, it-tieni element (9), it-tielet (79), ..., l-aħħar (29) jittieħdu.
Element mhux misjub.
It-tfittxija swiet 7 operazzjonijiet.

Funzjoni hash tajba

Kif tistgħu taraw, skont il-valur li tkun qed tfittex, l-ispiża mhix l-istess!

Jekk issa nibdel il-funzjoni hash modulo 1 taċ-ċavetta (jiġifieri, tieħu l-aħħar 000 ċifri), it-tieni tfittxija tiswa biss operazzjoni 000 peress li m'hemm l-ebda elementi fis-segment 6. L-isfida reali hija li ssib funzjoni hash tajba li toħloq bramel li jkun fihom numru żgħir ħafna ta 'elementi.

Fl-eżempju tiegħi, issib funzjoni ta 'hash tajba hija faċli. Iżda dan huwa eżempju sempliċi, li ssib funzjoni hash tajba hija aktar diffiċli meta ċ-ċavetta hija:

string (per eżempju - kunjom)
2 linji (per eżempju - kunjom u isem)
2 linji u data (per eżempju - kunjom, isem u data tat-twelid)
...

B'funzjoni tal-hash tajba, il-lokki tat-tabella tal-hash jiswew O(1).

Array vs tabella hash

Għaliex ma tużax firxa?

Hmm, mistoqsija tajba.

It-tabella tal-hash tista 'tkun parzjalment mgħobbija fil-memorja, u s-segmenti li jifdal jistgħu jibqgħu fuq id-diska.
B'firxa trid tuża spazju kontigwu fil-memorja. Jekk qed tagħbija mejda kbira huwa diffiċli ħafna li ssib biżżejjed spazju kontinwu.
Għal tabella hash, tista 'tagħżel iċ-ċavetta li trid (per eżempju, l-isem tal-pajjiż u l-kunjom tal-persuna).

Għal aktar informazzjoni, tista 'taqra l-artiklu dwar JavaHashMap, li hija implimentazzjoni effiċjenti ta 'tabella hash; m'għandekx bżonn tifhem Java biex tifhem il-kunċetti koperti f'dan l-artikolu.

Sors: www.habr.com

Kif Jaħdmu Databases Relazzjonali (Parti 1)