ProHoster > Si sihetë funksionojnë bazat e të dhënave relacionale (Pjesa 1)

Si sihetë funksionojnë bazat e të dhënave relacionale (Pjesa 1)

Përshëndetje, Habr! Po ju prezantoj një përkthim të artikullit
"Si funksionon një bazë e dhënash relacionale".

Kur vjen puna te bazat e të dhënave relacionale, nuk mund të mos mendoj se diçka mungon. Ato përdoren kudo. Ekzistojnë shumë lloje të ndryshme të bazave të dhënash: nga SQLite e vogël dhe e dobishme deri te Teradata e fuqishme. Por ka vetëm disa artikuj që shpjegojnë se si funksionon një bazë e dhënash. Mund të kërkoni vetë me kërkesën "howdoesarelationaldatabasework" ("si funksionojnë bazat e të dhënave relacionale") për të parë se sa pak rezultate ka. Më tepër, këta artikuj janë të shkurtër. Nëse kërkoni teknologjitë e fundit moderne (BigData, NoSQL ose JavaScript), do të gjeni më shumë artikuj të thelluar që shpjegojnë se si funksionojnë ato.

A janë bazat e të dhënave relacionale shumë të vjetra dhe shumë të mërzitshme për t'i shpjeguar jashtë kurseve universitare, punimeve hulumtuese dhe librave?

Si sihetë funksionojnë bazat e të dhënave relacionale (Pjesa 1)

Si zhvillues, unë e urrej të përdor atë që nuk e kuptoj. Dhe nëse bazat e të dhënave janë përdorur për më shumë se 40 vjet, duhet të ketë një arsye. Gjatë këtyre viteve, kam shpenzuar qindra orë për të kuptuar vërtet këto kutitë e zeza të çuditshme që përdor çdo ditë. Bazat e të dhënave relacionale janë shumë interesante, sepse ato janë të bazuara në koncepte të dobishme dhe të përdorura më shumë se një herë. Nëse jeni të interesuar për të kuptuar një bazë të dhënash, por keni pasur ndonjëherë kohë ose dëshirë për të studiuar këtë temë të gjerë, këtë artikull duhet ta pëlqeni.

Megjithëse titulli i këtij artikulli është e qartë, qëllimi i këtij artikulli nuk është të kuptohet se si përdoret një bazë e dhënash.Prandaj, ju tashmë duhet të dini si të shkruani një pyetje të thjeshtë lidhje dhe pyetjet themelore CRUD; ndryshe mund të mos e kuptoni këtë artikull. Kjo është e vetmja gjë që duhet të dini, do ta shpjegoj gjithçka tjetër.

Do të filloj me disa bazë të shkencave kompjuterike, siç është kompleksiteti temporal i algoritmeve (BigO). E di që disa prej jush e urrejnë këtë koncept, por pa të nuk do të mund të kuptoni nuancat brenda një baze të dhënash. Duke qënë se kjo është një temë e madhe, unë do të përqendrohem në atë që e konsideroj të rëndësishme: si një bazë e dhënash përpunon SQL kërkesën. Do të prezantoj vetëm konceptet themelore të bazës së të dhënave, në mënyrë që në fund të artikullit të keni një ide se çfarë ndodh nën kapak.

Duke qenë se ky është një artikull i gjatë dhe teknik, që përfshin shumë algoritmo dhe struktura të dhënash, mos u nxehni për ta lexuar atë. Disa koncepte mund të jenë të vështira për t'u kuptuar; ju mund të kaloni përmbajtjen dhe përsëri të merrni një ide të përgjithshme.

Për ata që janë më të informuar, ky artikull është i ndarë në 3 pjesë:

  • PĂ«rmbledhje e komponentĂ«ve tĂ« bazĂ«s sĂ« tĂ« dhĂ«nave me nivel tĂ« ulĂ«t dhe tĂ« lartĂ«
  • PĂ«rmbledhje e procesit tĂ« optimizimit tĂ« pyetjeve
  • PĂ«rmbledhje e menaxhimit tĂ« transaksioneve dhe rezervuarĂ«ve

Kthehemi te baza

Shumë vite më parë (në një galaksi të largët
), zhvilluesit duheshin të dinin saktësisht numrin e operacioneve që po kodonin. Ata e dinin përmendësh algoritmin dhe strukturat e të dhënave të tyre, sepse nuk mund të lejonin veten që të shpenzonin CPU dhe memorie të kompjuterëve të tyre të ngadaltë.

Në këtë pjesë, do t'ju rikujtoj disa nga këto koncepte, pasi ato janë të nevojshme për të kuptuar bazën e të dhënave. Gjithashtu do të prezantoj konceptin e indeksit të bazës së të dhënave.

O(1) vs O(n2)

Aktualisht shumë zhvillues nuk shqetësohen për kompleksitetin kohor të algoritmo... dhe ata kanë të drejtë!

Por kur keni të bëni me një sasi të madhe të dhënash (nuk po flas për mijëra) ose nëse po luftoni për milisekonda, bëhet thelbësore të kuptoni këtë koncept. Dhe siç e kuptoni, bazat e të dhënave duhet të përballen me të dyja situatat! Nuk do t'ju bëj të kaloni më shumë kohë se sa duhet për të kapur thelbin. Kjo do na ndihmojë më vonë të kuptojmë konceptin e optimizimit të bazuar në kosto (cost based optimization).

Koncepci

Kompleksiteti kohor i algoritmo përdoret për të parë sa kohë do të marrë ekzekutimi i algoritmit për një sasi të caktuar të dhënash. Për të përshkruar këtë kompleksitet, përdoren nota matematikore të mëdha O. Kjo notacion përdoret me funksionin që përshkruan sa shumë operacione iu duhen algoritmit për një sasi të caktuar të dhënash hyrëse.

Për shembull, kur them "ky algoritëm ka kompleksitet O (some_function() )", kjo do të thotë se për të përpunuar një sasi të caktuar të dhënash, algoritmi i kërkon some_function(a_certain_amount_of_data) operacione.

Dhe është e rëndësishme jo sasia e të dhënave**, por ajo, ** si rritet numri i operacioneve kur rritet sasia e të dhënave. Kompleksiteti kohor nuk jep një numër të saktë operacionesh, por është një mënyrë e mirë për të vlerësuar kohën e ekzekutimit.

Si sihetë funksionojnë bazat e të dhënave relacionale (Pjesa 1)

Në këtë grafik mund të shihni varësinë e numrit të operacioneve nga volumi i të dhënave të hyrjes për lloje të ndryshme të kompleksiteteve të algoritmeve. Kam përdorur një shkallë logarithmike për ta paraqitur atë. Në fjalë të tjera, sasia e të dhënave rritet shpejt nga 1 në 1 miliard. Mund të shohim se:

  • O(1) ose kompleksiteti konstant mbetet i pandryshuar (pĂ«rndryshe nuk do tĂ« quhej kompleksitet konstant).
  • O(log(n)) mbetet i ulĂ«t edhe me miliarda tĂ« dhĂ«na.
  • Kompleksiteti mĂ« i keq Ă«shtë— O(n2), ku numri i operacioneve rritet shpejt.
  • Dy kompleksitete tĂ« tjera gjithashtu rriten me shpejtĂ«si tĂ« madhe.

Shembuj

Me një numër të vogël të dhënash, diferenca midis O(1) dhe O(n2) është e papërfillshme. Për shembull, le ta supozojmë se keni një algoritëm që duhet të procesojë 2000 elemente.

  • Algoritmi O(1) do t'ju kushtojĂ« 1 operacion
  • Algoritmi O(log(n)) do t'ju kushtojĂ« 7 operacione
  • Algoritmi O(n) do t'ju kushtojĂ« 2 000 operacione
  • Algoritmi O(n * log(n)) do t'ju kushtojĂ« 14 000 operacione
  • Algoritmi O(n2) do t'ju kushtojĂ« 4 000 000 operacione

Diferenca midis O(1) dhe O(n2) duket e madhe (4 milion operacione) por do të humbni maksimum 2 ms, sa një kohë për të mbyllur sytë. Në të vërtetë, procesorët modern mund të përpunojnë qindra miliona operacione në sekondë. Kjo është arsyeja pse performanca dhe optimizimi nuk janë probleme në shumë projekte IT.

Siç e thashë, është ende e rëndësishme të kuptohet kjo koncept kur punoni me një sasi të madhe të dhënash. Nëse këtë herë algoritmi duhet të procesojë 1 000 000 elemente (ndonjëherë kjo nuk është shumë për një bazë të dhënash):

  • Algoritmi O(1) do t'ju kushtojĂ« 1 operacion
  • Algoritmi O(log(n)) do t'ju kushtojĂ« 14 operacione
  • Algoritmi O(n) do t'ju kushtojĂ« 1 000 000 operacione
  • Algoritmi O(n * log(n)) do t'ju kushtojĂ« 14 000 000 operacione
  • Algoritmi O(n2) do t'ju kushtojĂ« 1 000 000 000 000 operacione

Nuk kam bërë llogaritjet, por do të thoja se me algoritmin O(n2) keni kohë për të pirë një kafe (madje dy!). Nëse shtoni edhe 0 në sasinë e të dhënave, do të keni kohë për të bësh një gjumë të vogël.

Le të shkojmë më thellë

PĂ«r reference:

  • KĂ«rkimi nĂ« njĂ« tabelĂ« tĂ« mirĂ« tĂ« heshĂ«ve gjen elementin nĂ« O(1).
  • KĂ«rkimi nĂ« njĂ« pemĂ« tĂ« mirĂ« tĂ« balancuar jep rezultatin nĂ« O(log(n)).
  • KĂ«rkimi nĂ« njĂ« varg jep rezultatin nĂ« O(n).
  • Algoritmet mĂ« tĂ« mira tĂ« renditjes kanĂ« kompleksitet O(n * log(n)).
  • NjĂ« algoritĂ«m i keq i renditjes ka kompleksitet O(n2).

Shënim: në pjesët në vazhdim do të shohim këto algoritme dhe struktura të dhënash.

Ka janë disa lloje të kompleksitetit temporal të algoritmit:

  • skenari i rastit mesatar
  • mĂ«nyra mĂ« e mirĂ« e zhvillimit
  • dhe skenari mĂ« i keq

Kompleksiteti temporal zakonisht është skenari më i keq.

Kam folur vetëm për kompleksitetin temporal të algoritmit, por kompleksiteti gjithashtu aplikohet për:

  • konsumimin e memories nga algoritmi
  • konsumimin e input/output nĂ« disk nga algoritmi

Sigurisht, ka komplekse më të këqija se n2, për shembull:

  • n4: kjo Ă«shtĂ« e tmerrshme! Disa nga algoritmet e pĂ«rmendura kanĂ« njĂ« kompleksitet tĂ« tillĂ«.
  • 3n: kjo Ă«shtĂ« akoma mĂ« e keqe! NjĂ« nga algoritmet qĂ« do tĂ« shohim nĂ« mes tĂ« kĂ«tij artikulli ka kĂ«tĂ« kompleksitet (dhe nĂ« tĂ« vĂ«rtetĂ« pĂ«rdoret nĂ« shumĂ« baza tĂ« tĂ« dhĂ«nash).
  • faktorial n: nuk do tĂ« merrni kurrĂ« rezultatet tuaja edhe me njĂ« sasi tĂ« vogĂ«l tĂ« dhĂ«nash.
  • nn: nĂ«se pĂ«rballeni me kĂ«tĂ« kompleksitet, duhet tĂ« pyesni veten, a Ă«shtĂ« vĂ«rtet kjo fusha juaj 


Shënim: ju kam dhënë një ide, jo një definicion të vërtetë të shenjës "O e madhe". Mund të lexoni këtë artikull në Wikipedia për një definicion të vërtetë (asimptotik).

MergeSort (Sortimi me bashkim)

ÇfarĂ« bĂ«ni kur ju nevojitet tĂ« renditni njĂ« koleksion? ÇfarĂ«? ThĂ«rrisni funksionin sort()
 Ok, pĂ«rgjigje e mirë  Por pĂ«r njĂ« bazĂ« tĂ« dhĂ«nash, duhet ta kuptoni se si funksionon ky funksion sort().

Ekzistojnë disa algoritme të mira për renditjen, prandaj unë do të ndalem te më i rëndësishmi: renditja me bashkim. Ndoshta tani nuk po e kuptoni pse renditja e të dhënave është e dobishme, por do të duhet të kuptoni pas pjesës që i dedikohet optimizimit të pyetjeve. Më shumë, kuptimi i renditjes me bashkim do të na ndihmojë më vonë të kuptojmë operacionin e përgjithshëm të bashkimit të bazave të të dhënave, të quajtur merge bashkohu (bashkimi me bashkim).

Bashko (bashkimi)

Si shumë algoritme të dobishme, renditja me bashkim bazohet në një hile: bashkimi i dy masivave të renditur të madhësisë N/2 në një masiv të renditur me N elemente kërkon vetëm N operacione. Ky operacion quhet bashkim.

Le të shohim se çfarë do të thotë kjo në një shembull të thjeshtë:

Si sihetë funksionojnë bazat e të dhënave relacionale (Pjesa 1)

Në këtë skicë, është e qartë se për të ndërtuar masivin përfundimtar të renditur nga 8 elemente duhet të bëni vetëm një iterim për dy masiva të renditur me 4 elemente. Duke qenë se të dy masivat me 4 elemente janë të renditur tashmë:

  • 1) ju krahasoni tĂ« dy elementĂ«t aktualĂ« nĂ« dy masivat (nĂ« fillim aktuali = i pari)
  • 2) pastaj merrni mĂ« tĂ« voglin pĂ«r ta vendosur atĂ« nĂ« njĂ« array me 8 elemente
  • 3) dhe kaloni nĂ« elementin tjetĂ«r nĂ« array, ku morĂ«t elementin mĂ« tĂ« vogĂ«l
  • dhe pĂ«rsĂ«ritni 1, 2, 3 derisa tĂ« arrini te elementi i fundit tĂ« njĂ«rit nga array-t.
  • Pastaj merrni elementĂ«t e tjerĂ« tĂ« array-t tjetĂ«r pĂ«r t'i vendosur nĂ« array me 8 elemente.

Kjo funksionon, sepse të dy array-t me 4 elemente janë të renditura, dhe për këtë arsye nuk keni nevojë të "ktheheni" në këto array.

Tani që e kuptuam këtë mashtrim, ja pseudokodi im për bashkimin:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //kthimet rekurzive
   [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);

   //bashkimi i 2 array-ve të vogla të renditura në një të madhe
   array result := merge(new_left_array,new_right_array);
   return result;

Sorting me bashkim e ndan detyrën në detyra më të vogla dhe pastaj gjen rezultatet e detyrave më të vogla për të marrë rezultatin e detyrës origjinale (shënim: ky lloj algoritmi quhet ndaje dhe sundo). Nëse nuk e kuptoni këtë algoritem, mos u shqetësoni; unë nuk e kuptova këtë herën e parë që e pashë. Nëse kjo mund t'ju ndihmojë, unë e shoh këtë algoritëm si një algoritëm me dy faza:

  • Faza e ndarjes, ku array-i ndahet nĂ« array tĂ« vogla
  • Faza e renditjes, ku array tĂ« vogla bashkohen (duke pĂ«rdorur bashkimin) pĂ«r tĂ« krijuar njĂ« array mĂ« tĂ« madh.

Faza e ndarjes

Si sihetë funksionojnë bazat e të dhënave relacionale (Pjesa 1)

Në fazën e ndarjes, array ndahen në array të njësi përmes 3 hapash. Numri formal i hapave është log(N) (për shkak se N=8, log(N) = 3).

Si e di unë këtë?

UnĂ« jam njĂ« gjenial! NĂ« njĂ« fjalĂ« — matematika. Ideja Ă«shtĂ« se çdo hap nda madhĂ«sinĂ« e array-original nĂ« 2. Numri i hapave Ă«shtĂ« numri i herĂ«ve qĂ« mund t'i ndani array-n origjinal nĂ« dy. Kjo Ă«shtĂ« pĂ«rkufizimi i saktĂ« i logaritmit (me bazĂ« 2).

Faza e renditjes

Si sihetë funksionojnë bazat e të dhënave relacionale (Pjesa 1)

Në fazën e renditjes, filloni me array të njësi (me një element). Në secilën fazë, aplikoni disa operacione bashkimi, dhe kostoja totale është N = 8 operacione:

  • NĂ« hapin e parĂ«, keni 4 bashkime, tĂ« cilat kushtojnĂ« 2 operacione secila
  • NĂ« hapin e dytĂ«, keni 2 bashkime, qĂ« kushtojnĂ« 4 operacione secila
  • NĂ« hapin e tretĂ«, keni 1 bashkim, qĂ« kushton 8 operacione

PĂ«r shkak se ka log(N) hapa, kostoja totale N * log(N) operacione.

Avantazhet e renditjes me bashkim

Pse është ky algoritëm kaq i fuqishëm?

Sepse:

  • Mund ta ndryshoni atĂ« pĂ«r tĂ« reduktuar sasinĂ« e memories, nĂ« mĂ«nyrĂ« qĂ« tĂ« mos krijoni masa tĂ« reja, por tĂ« ndryshoni direkt masĂ«n hyrĂ«se.

ShĂ«nim: ky lloj algoritmesh quhet in—vend (renditje pa kujtesĂ« shtesĂ«).

  • Mund ta ndryshoni atĂ« pĂ«r tĂ« pĂ«rdorur hapĂ«sirĂ«n ndihmĂ«se dhe njĂ« sasi tĂ« vogĂ«l memorjeje pa kosto tĂ« konsiderueshme nĂ« hyrje/ dalje nga disku. Ideja Ă«shtĂ« qĂ« tĂ« ngarkohet nĂ« memorje vetĂ«m ato pjesĂ« qĂ« janĂ« duke u trajtuar aktualisht. Kjo Ă«shtĂ« e rĂ«ndĂ«sishme kur ju nevojitet tĂ« renditni njĂ« tabelĂ« me disa gigabajtĂ« me njĂ« tampon memorjeje prej 100 megabajtĂ«sh.

Shënim: ky lloj algoritmesh quhet renditje e jashtme.

  • Mund ta ndryshoni atĂ« pĂ«r tĂ« funksionuar nĂ« disa procese/rrjedha/servertime.

Për shembull, renditja e shpërndarë me bashkim është një nga komponentët kyç Hadoop (i cili është një strukturë në të dhënat e mëdha).

  • Ky algoritĂ«m mund tĂ« kthejĂ« plumbin nĂ« ar (e vĂ«rtetĂ«!).

Ky algoritëm renditjeje përdoret në shumicën (nëse jo në të gjitha) bazat e të dhënave, por nuk është i vetmi. Nëse dëshironi të dini më shumë, mund të lexoni këtë punim kërkimor, i cili diskuton avantazhet dhe disavantazhet e algoritmeve të zakonshme të renditjes në bazat e të dhënave.

Masa, Pema dhe Tabela e Hashit

Tani që e kuptojmë idenë e kompleksitetit temporal dhe renditjes, duhet t'ju flas për 3 strukturat e dhënave. Kjo është e rëndësishme sepse ato janë baza e bazave të të dhënave moderne. Do të prezantoj gjithashtu konceptin indeksit të bazës së të dhënave.

Array

Masa dy dimensionale është struktura më e thjeshtë e dhënave. Tabela mund të mendohet si një masë. Për shembull:

Si sihetë funksionojnë bazat e të dhënave relacionale (Pjesa 1)

Ky masë 2-dimensionale përfaqëson një tabelë me rreshta dhe kolona:

  • Çdo rresht pĂ«rfaqĂ«son njĂ« entitet
  • Kolonat ruajnĂ« pronat qĂ« pĂ«rshkruajnĂ« entitetin.
  • Çdo kolonĂ« ruan tĂ« dhĂ«na tĂ« njĂ« lloji tĂ« caktuar (integer, string, date 
).

ËshtĂ« kaq e pĂ«rshtatshme pĂ«r tĂ« ruajtur dhe vizualizuar tĂ« dhĂ«na, megjithatĂ«, kur ju nevojitet tĂ« gjeni njĂ« vlerĂ« tĂ« caktuar, kjo nuk funksionon.

PĂ«r shembull, nĂ«se dĂ«shironi tĂ« gjeni tĂ« gjithĂ« djemtĂ« qĂ« punojnĂ« nĂ« MbretĂ«rinĂ« e Bashkuar, do t'ju duhet tĂ« shqyrtoni çdo rresht pĂ«r tĂ« pĂ«determuar nĂ«se ky rresht i pĂ«rket MbretĂ«risĂ« sĂ« Bashkuar. Kjo do t'ju kushtojĂ« N operacioneindex N — numri i rreshtave, qĂ« nuk Ă«shtĂ« keq, por a ka njĂ« mĂ«nyrĂ« mĂ« tĂ« shpejtĂ«? Tani Ă«shtĂ« koha tĂ« njihemi me pemĂ«t.

Shënim: shumica e bazave të të dhënave moderne ofrojnë grupe të zgjeruara për ruajtjen efikase të tabelave: heap-organized tables dhe index-organized tables. Por kjo nuk ndryshon problemin e kërkimit të shpejtë për një kusht të caktuar në një grup kolonash.

Pema dhe indeksi i bazës së të dhënave

Pema binare e kërkimit është një pemë binare me një pronë të veçantë, çelësi në çdo nyje duhet të jetë:

  • mĂ« i madh se tĂ« gjithĂ« çelĂ«sat qĂ« janĂ« ruajtur nĂ« nĂ«npemĂ«n e majtĂ«
  • mĂ« i vogĂ«l se tĂ« gjithĂ« çelĂ«sat qĂ« janĂ« ruajtur nĂ« nĂ«npemĂ«n e djathtĂ«

Le ta shohim se çfarë do të thotë kjo vizualisht

Ideja

Si sihetë funksionojnë bazat e të dhënave relacionale (Pjesa 1)

Kjo pemë ka N = 15 elemente. Le të themi se po kërkoj 208:

  • Filloj nga rrĂ«nja, çelĂ«si i sĂ« cilĂ«s Ă«shtĂ« 136. Pasi 136<208, shoh nĂ« nĂ«npemĂ«n e djathtĂ« tĂ« nyjes 136.
  • 398>208, prandaj, shoh nĂ« nĂ«npemĂ«n e majtĂ« tĂ« nyjes 398
  • 250>208, prandaj, shoh nĂ« nĂ«npemĂ«n e majtĂ« tĂ« nyjes 250
  • 200<208, prandaj, shoh nĂ« nĂ«npemĂ«n e djathtĂ« tĂ« nyjes 200. Por 200 nuk ka nĂ«npemĂ« tĂ« djathtĂ«, vlera nuk ekziston (sepse, nĂ«se do tĂ« ekzistonte, do tĂ« ishte nĂ« nĂ«npemĂ«n e djathtĂ« tĂ« 200).

Tani, le të themi se po kërkoj 40

  • Fillo nga rrĂ«nja, çelĂ«si i sĂ« cilĂ«s Ă«shtĂ« 136. Pasi 136 > 40, shoh nĂ« nĂ«npemĂ«n e majtĂ« tĂ« nyjes 136.
  • 80 > 40, prandaj, shoh nĂ« nĂ«npemĂ«n e majtĂ« tĂ« nyjes 80
  • 40= 40, nyja ekziston. Nxjerr identifikuesin e rreshtit brenda nyjĂ«s (kjo nuk Ă«shtĂ« nĂ« ilustrim) dhe shoh nĂ« tabelĂ« pĂ«r identifikuesin e dhĂ«nĂ« tĂ« rreshtit.
  • Dija pĂ«r identifikuesin e rreshtit, mĂ« lejon tĂ« di saktĂ«sisht ku ndodhen tĂ« dhĂ«nat nĂ« tabelĂ«, dhe pĂ«r kĂ«tĂ« arsye mund t'i marr ato menjĂ«herĂ«.

Në fund, të dy kërkime do të më kushtojnë numrin e niveleve brenda pemës. Nëse lexoni me kujdes pjesën mbi renditjen e bashkimit, duhet të shihni se këtu ka log(N) nivele. Pra, kostoja e kërkimit është log(N), nuk është keq!

Kthehemi në problemin tonë

Por kjo është shumë abstrakte, prandaj le të kthehemi në problemin tonë. Në vend të një integeri të thjeshtë, imagjinoni një varg që përfaqëson vendin e dikujt në tabelën e mëparshme. Supozoni se keni një pemë që përmban fushën "country" (kolona 3) të tabelës:

  • NĂ«se dĂ«shironi tĂ« dini, kush punon nĂ« MbretĂ«rinĂ« e Bashkuar
  • shihni pemĂ«n pĂ«r tĂ« marrĂ« nyjĂ«n qĂ« pĂ«rfaqĂ«son MbretĂ«rinĂ« e Bashkuar
  • brenda "UKnode" do tĂ« gjeni lokacionin e regjistrimeve tĂ« punĂ«torĂ«ve nĂ« MbretĂ«rinĂ« e Bashkuar.

Kërkimi i kësaj do t'i kushtojë log(N) operacione në vend të N operacioneve nëse e përdorni drejtpërdrejt matricën. Ajo që sapo paraqitët është indeksi i bazës së të dhënave.

Mund tĂ« ndĂ«rtoni njĂ« pemĂ« indeksi pĂ«r çdo grup fushash (string, numĂ«r, 2 strings, numĂ«r dhe string, datë ) sa kohĂ« qĂ« keni njĂ« funksion pĂ«r tĂ« krahasuar çelĂ«sat (dmth. grupet e fushave) nĂ« mĂ«nyrĂ« qĂ« tĂ« mund tĂ« vendosni renditjen mes çelĂ«save (çka ndodh pĂ«r çdo tip tĂ« thjeshtĂ« nĂ« bazĂ«n e tĂ« dhĂ«nave).

B+TreeIndex

MegjithĂ«se kjo pemĂ« funksionon mirĂ« pĂ«r tĂ« marrĂ« njĂ« vlerĂ« tĂ« caktuar, ekziston njĂ« PROBLEM TË MADH kur ju nevojitet tĂ« merrni disa elemente midis dy vlerave. Kjo do t'i kushtojĂ« O(N) sepse do t'ju duhet tĂ« shihni çdo nyje nĂ« pemĂ« dhe tĂ« kontrolloni nĂ«se ndodhet midis kĂ«tyre dy vlerave (pĂ«r shembull, me njĂ« kalim tĂ« renditur tĂ« pemĂ«s). PĂ«r mĂ« tepĂ«r, kjo operacion nuk Ă«shtĂ« e pĂ«rshtatshme pĂ«r hyrjen dhe daljen nĂ« disk, pasi do t'ju duhet tĂ« lexoni tĂ« gjithĂ« pemĂ«n. Na nevojitet njĂ« mĂ«nyrĂ« pĂ«r tĂ« kryer kĂ«rkesĂ«n e intervalit. PĂ«r tĂ« zgjidhur kĂ«tĂ« problem, bazat e tĂ« dhĂ«nave moderne pĂ«rdorin njĂ« version tĂ« modifikuar tĂ« pemĂ«s sĂ« mĂ«parshme tĂ« quajtur B+Tree. NĂ« pemĂ«n B+Tree:

  • vetĂ«m nyjet mĂ« tĂ« ulĂ«ta (gjethet) ruajnĂ« informacionin (lokacionin e rreshtave nĂ« tabelĂ«n e lidhur)
  • nyjet e tjera janĂ« kĂ«tu pĂ«r t'u drejtuar nĂ« nyjen e duhur gjatĂ« kĂ«rkimit.

Si sihetë funksionojnë bazat e të dhënave relacionale (Pjesa 1)

Siç mund ta shihni, këtu ka më shumë nyje (dyfish). Në të vërtetë, keni nyje shtesë, "nyje vendimmarrëse", që do t'ju ndihmojnë të gjeni nyjen e duhur (e cila ruan lokacionin e rreshtave në tabelën e lidhur). Por kompleksiteti i kërkimit mbetet përsëri O(log(N)) (ka vetëm një nivel tjetër). Diferenca e madhe është se nyjet në nivelin më të ulët janë të lidhura me pasardhësit e tyre.

Me këtë B+Tree, nëse kërkoni vlerat nga 40 në 100:

  • Thjesht duhet tĂ« kĂ«rkoni 40 (ose vlerĂ«n mĂ« tĂ« afĂ«rt pas 40, nĂ«se 40 nuk ekziston), ashtu siç bĂ«tĂ« me pemĂ«n e mĂ«parshme.
  • Pastaj mbledhni pasardhĂ«sit e 40, duke pĂ«rdorur lidhje direkte me pasardhĂ«sit, derisa tĂ« arrini 100.

Të supozoni se keni gjetur M pasardhës, dhe pemë ka N nyje. Kërkimi në një nyje të caktuar kushton log(N) si me pemën e mëparshme. Por, duke marrë këtë nyje, do të merrni M pasardhës në M operacione me lidhjet ndaj pasardhësve të tyre. Ky kërkim kushton vetëm M+log(N) në krahasim me N operacione të pemës së mëparshme. Më shumë, nuk ju nevojitet të lexoni të gjithë pemën (vetëm M + log (N) nodules), që do të thotë përdorim më të ulët të ndarjes. Nëse M është e vogël (p.sh. 200 rreshta) dhe N është e madhe (1 000 000 rreshta), kjo do të jetë një DALLIM I MADH.

Por këtu ka probleme të reja (prapë!). Nëse shtoni ose hiqni një rresht në bazën e të dhënave (dhe, për rrjedhojë, në indekset e lidhura B+Tree):

  • duhet tĂ« mbani rendin midis nodulave brenda pemĂ«s B+Tree, pĂ«rndryshe nuk do tĂ« jeni nĂ« gjendje tĂ« gjeni nodet brenda pemĂ«s sĂ« pa renditur.
  • duhet tĂ« ruani numrin minimal tĂ« niveleve nĂ« B+Tree, pĂ«rndryshe kompleksiteti temporal nĂ« O (log (N)) do tĂ« bĂ«het O (N).

Me fjalë të tjera, B+Tree duhet të jetë vetë-renditur dhe i balancuar. Fatmirësisht, kjo është e mundur me operacione të mençura të fshirjes dhe shtimit. Por kjo do të kushtojë shtrenjtë: shtimi dhe fshirja në pemën B+ kushtojnë O (log (N)). Kjo është arsyeja pse disa prej jush kanë dëgjuar se përdorimi i shumë indekseve nuk është një ide e mirë. Në të vërtetë, ju ngadalësoni shtimin e shpejtë / përditësimin / fshirjen e një rreshti në tabelë, pasi baza e të dhënave duhet të përditësojë indiket e tabelës me një operacion të kushtueshëm O (log (N)) për çdo indeks. Më shumë, shtimi i indekseve do të thotë një ngarkesë më të madhe për menaxherin e transaksioneve (do të përshkruhet në fund të artikullit).

Për më shumë informacion, mund të shihni artikullin në Wikipedia rreth B+Pemës. Nëse dëshironi një shembuj implementimi të B+Tree në bazën e të dhënave, shihni ky artikull dhe ky artikull nga zhvilluesi kryesor i MySQL. Të dy përqendrohen në mënyrën se si InnoDB (motor MySQL) trajton indiket.

Shënim: lexuesi më tha se, për shkak të optimizimeve të nivelit të ulët, pema B+ duhet të jetë plotësisht e balancuar.

Hashtable (Tabela e Heshit)

Struktura jonë e fundit e rëndësishme të dhënash është tabela e heshit. Kjo është shumë e dobishme kur dëshironi të kërkoni shpejt vlera. Më shumë, kuptimi i tabelës së heshit do të na ndihmojë më vonë të kuptojmë operacionin e përgjithshëm të bashkimit me bazën e të dhënave, të quajtur bashkimi hesh ( bashkim hesh). Kjo strukturë të dhënash përdoret gjithashtu nga baza e të dhënave për ruajtjen e disa gjërave të brendshme (p.sh., tabela e bllokimit ose pula e memorjes, do t'i shohim të dy këto koncepte më vonë).

Tabela e heshit është një strukturë të dhënash që gjen shpejt një element sipas çelësit të tij. Për të ndërtuar një tabelë hesh, duhet të përcaktoni:

  • çelĂ«sin pĂ«r elementet tuaja
  • funksionin e heshit pĂ«r çelĂ«sat. HeshĂ«t e llogaritur tĂ« çelĂ«save japin vendndodhjen e elementeve (tĂ« quajtur segmente ).
  • funksion pĂ«r krahasimin e çelĂ«save. Sapo tĂ« keni gjetur segmentin e duhur, duhet tĂ« gjeni elementin qĂ« kĂ«rkoni brenda segmentit, duke pĂ«rdorur kĂ«tĂ« krahasim.

Një shembull i thjeshtë

Le të marrim një shembull ilustruar:

Si sihetë funksionojnë bazat e të dhënave relacionale (Pjesa 1)

Kjo tabelë hesh ka 10 segmente. Për shkak se jam lenë, kam ilustruar vetëm 5 segmente, por e di që ju jeni të zgjuar, prandaj do t'ju lejoj të imagjinoni 5 të tjerat vetë. Kam përdorur funksionin e heshit mod 10 të çelësit. Në fjalë të tjera, ruaj vetëm numrin e fundit të çelësit të elementit për të gjetur segmentin e tij:

  • nĂ«se numri i fundit Ă«shtĂ« 0, elementi hyn nĂ« segmentin 0,
  • nĂ«se numri i fundit Ă«shtĂ« 1, elementi hyn nĂ« segmentin 1,
  • nĂ«se numri i fundit Ă«shtĂ« 2, elementi hyn nĂ« segmentin 2,
  • 


Funksioni i krahasimit që kam përdorur, është thjesht barazia midis dy numrave të plotë.

Supozoni se dëshironi të merrni elementin 78:

  • Tabela e heshit llogarit kodin hesh pĂ«r 78, qĂ« Ă«shtĂ« 8.
  • Tabela e heshit shikon nĂ« segmentin 8, dhe elementi i parĂ« qĂ« gjen Ă«shtĂ« 78.
  • Ajo ju kthen elementin 78
  • KĂ«rkimi kushton vetĂ«m 2 operacione (njĂ« pĂ«r llogaritjen e vlerĂ«s sĂ« funksionit tĂ« heshit, dhe tjetra pĂ«r gjetjen e elementit brenda segmentit).

Tani, supozoni se dëshironi të merrni elementin 59:

  • Tabela e heshit llogarit kodin hesh pĂ«r 59, qĂ« Ă«shtĂ« 9.
  • Tabela e heshit kĂ«rkon nĂ« segmentin 9, elementi i parĂ« i gjetur Ă«shtĂ« 99. Pasi 99 != 59, elementi 99 nuk Ă«shtĂ« elementi i saktĂ«.
  • Duke pĂ«rdorur logjikĂ«n e njĂ«jtĂ«, merret elementi i dytĂ« (9), i treti (79), 
, i fundit (29).
  • Elementi nuk u gjet.
  • KĂ«rkimi kishte kushtuar 7 operacione.

Një funksion i mirë hesh

Siç shihni, në varësi të vlerës që po kërkoni, kostoja nuk është e njëjtë!

Nëse tani ndryshoj funksionin e heshit në mod 1 000 000 të çelësit (dmth, duke marrë 6 numrat e fundit), kërkimi i dytë do të kushtojë vetëm 1 operacion, sepse në segmentin 000059 nuk ka elemente. Detyra reale është të gjendet një funksion i mirë hesh, i cili do të krijojë segmente që përmbajnë një numër shumë të vogël elementesh..

Në shembullin tim, është e lehtë të gjesh një funksion hash të mirë. Por ky është një shembull i thjeshtë, të gjesh një funksion hash të mirë është më e vështirë kur çelësi:

  • string (p.sh. mbiemri)
  • 2 strings (p.sh. mbiemri dhe emri)
  • 2 strings dhe njĂ« datĂ« (p.sh. mbiemri, emri dhe data e lindjes)
  • 


Me një funksion hash të mirë, kërkimi në tabelën hash bëhet në O(1).

Merrja e array-ve vs tabelës hash

Pse të mos përdorim array?

Hmm, pyetje e mirë.

  • Tabela hash mund tĂ« jetĂ« pjesĂ«risht e ngarkuar nĂ« memorie, ndĂ«rsa segmentet e tjera mund tĂ« qĂ«ndrojnĂ« nĂ« disk.
  • Me array duhet tĂ« pĂ«rdorĂ«sh hapĂ«sirĂ« tĂ« pandĂ«rprerĂ« nĂ« memorie. NĂ«se ngarkon njĂ« tabelĂ« tĂ« madhe shumĂ« e vĂ«shtirĂ« tĂ« gjejĂ« mjaft hapĂ«sirĂ« tĂ« pandĂ«rprerĂ«.
  • PĂ«r tabelĂ«n hash, mund tĂ« zgjidhni çelĂ«sin qĂ« dĂ«shironi (p.sh. vendi dhe mbiemri i personit).

Për informacion të mëtejshëm, mund të lexoni artikullin mbi JavaHashMap, e cila është një realizim efikas i tabelës hash; nuk keni nevojë të kuptoni Java për të kuptuar konceptet e paraqitura në këtë artikull.

Burimi: habr.com

Blini hosting tĂ« besueshĂ«m pĂ«r faqe interneti me mbrojtje nga DDoS, serverĂ« VPS VDS đŸ”„ Blini hosting tĂ« besueshĂ«m pĂ«r faqe interneti me mbrojtje nga DDoS, serverĂ« VPS VDS | ProHoster