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

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

Përshëndetje, Habr! Ju prezantoj përkthimin e artikullit
"Si e punon një bazë të dhënash relacional".

Kur bëhet fjalë për bazat e të dhënave relacionale, nuk mund të mos mendoj që diçka mungon. Ato përdoren në çdo vend. Ekzistojnë shumë lloje të ndryshme bazash të dhënash: nga SQLite më e vogël dhe më e dobishme deri te e fuqishmja Teradata. Por ka vetëm disa artikuj që shpjegojnë se si funksionon një bazë të dhënash. Ju mund të kërkoni vetë me kërkimin "howdoesarelationaldatabasework" («si funksionojnë bazat e të dhënave relacionale») për të parë sa pak rezultate kanë. Për më tepër, këta artikuj janë të shkurtër. Nëse jeni në kërkim të teknologjive më moderne (BigData, NoSQL ose JavaScript), do të gjeni shumë artikuj më të thelluar që shpjegojnë se si ata funksionojnë.

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

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

Si një 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 kaluar qindra orë për të kuptuar vërtet këto kuti të çuditshme të zezë që përdor çdo ditë. Baza të dhënash relacionale shumë interesante, sepse ato bazohet në koncepte të dobishme dhe të përdorura shpesh. Nëse jeni të interesuar për të kuptuar një bazë të dhënash, por keni pasur kurrë kohë ose dëshirë për të hyrë në këtë temë të gjerë, kjo artikull duhet t'ju pëlqejë.

Megjithëse titulli i kësaj artikulli është i qartë, qëllimi i kësaj arti kuti nuk është të kuptoni se si të përdorni një bazë të dhënash. Ndaj, ju duhet të dini tashmë si të shkruani një kërkesë të thjeshtë bashkimi dhe kërkesat themelore CRUD; ndryshe mund të mos e kuptoni këtë artikull. Kjo është e vetmja gjë që duhet të dini, unë do t'ju shpjegoj gjithçka tjetër.

Do të filloj me disa baza të shkencave kompjuterike, si kompleksiteti temporal i algoritmeve (BigO). E di që disa nga ju e urrejnë këtë koncept, por pa të nuk do të jeni në gjendje të kuptoni nuancat brenda një baze të dhënash. Duke qenë se kjo është një temë e madhe, do të përqendrohem në ato që mendoj se janë të rëndësishme: se si një bazë të dhënash përpunon SQL një kërkesë. Unë do të paraqes vetëm konceptet themelore të bazës së të dhënave, në mënyrë që në fund të artikullit të keni një pasqyrë të asaj që ndodh nën kapak.

Pasi se kjo është një artikull i gjatë dhe teknik që përfshin shumë algoritme dhe struktura të dhënash, mos u nxito ta lexosh. Disa koncepte mund të jenë të komplikuara për t'u kuptuar; mund t'i injorosh ato dhe prapë të kesh një ide të përgjithshme.

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

  • PĂ«rmbledhja e komponenteve tĂ« bazĂ«s sĂ« tĂ« dhĂ«nave tĂ« nivelit tĂ« ulĂ«t dhe tĂ« lartĂ«
  • PĂ«rmbledhja e procesit tĂ« optimizimit tĂ« kĂ«rkesave
  • PĂ«rmbledhja e menaxhimit tĂ« transaksioneve dhe rezervuarit tĂ« kujtesĂ«s

Rikthimi në baza

Shumë vite më parë (në një galaksi të largët, të largët
), zhvilluesit duhej të dinin saktësisht numrin e operacioneve që po kodonin. Ata i dinin përmendësh algoritmet dhe strukturat e dhënash, sepse nuk mund të lejonin që CPU dhe memorja e kompjuterëve të tyre të ngadaltë të konsumoheshin kot.

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. Po ashtu, do të prezantoj konceptin e indeksit të bazës së të dhënave.

O(1) vs O(n2)

Aktualisht, shumë zhvillues nuk interesohen për kompleksitetin e kohës së algoritmeve
 dhe ata kanë të drejtë!

Por kur ke të bësh me një sasi të madhe të dhënash (nuk po flas për mijëra) ose nëse je duke luftuar për milisekonda, bëhet kritikisht e rëndësishme të kuptosh këtë koncept. Dhe siç e kupton, bazat e të dhënave duhet të përballen me të dyja situatat! Nuk do t'ju ndaj më shumë kohë se sa është e nevojshme për të kuptuar thelbin. Kjo do të na ndihmojë më vonë në kuptimin e konceptit të optimizimit të bazuar në kosto (kostot për bazë optimizimi).

Koncepsi

Kompleksiteti i kohës së algoritmit përdoret për të parë se sa kohë do të duhej për të kryer algoritmin për një sasi të caktuar të dhënash. Për të përshkruar këtë kompleksitet, përdoren përfaqësime matematikore të mëdha O. Kjo notacion përdoret me një funksion që përshkruan se sa operacione i nevojiten 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 ka nevojë për some_function(a_certain_amount_of_data) operacione.

Dhe kështu është e rëndësishme jo sasia e dhënave**, por se si ** rritet numri i operacioneve me rritjen e sasisë së dhënave. Kompleksiteti i kohës 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 funksionojnë bazat e të dhënave relacione (Pjesa 1)

Në këtë grafik mund të shihni varësinë midis numrit të operacioneve dhe vëllimit të të dhënave hyrëse për lloje të ndryshme të kompleksiteteve kohore të algoritmeve. Kam përdorur një shkallë logarifmike për t'i paraqitur ato. Në fjalë të tjera, numri i të dhënave rritet shpejt nga 1 në 1 miliard. Mund të shohim se:

  • O(1) ose kompleksiteti konstant mbetet i pandryshuar (ndryshe 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 shpejt.

Shembuj

Me një numër të vogël të dhënash, diferenca midis O(1) dhe O(n2) është e vogël. Për shembull, supozoni që keni një algoritëm që duhet të përpunojë 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 maksimumi 2 ms, aq sa zgjat koha për të mbyllur sytë. Në të vërtetë, procesorët modernë mund të përpunojnë qindra miliona operacione në sekondë. Ky është arsyeja pse performanca dhe optimizimi nuk janë një problem në shumë projekte IT.

Siç thashë më parë, është akoma e rëndësishme të njihni këtë koncept kur punoni me një sasi të madhe të dhënash. Nëse këtë herë algoritmi duhet të përpunojë 1,000,000 elemente (çfarë 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ë llogaritje, por do të thosha se me algoritmin O(n2) keni kohë të pini një kafe (madje dy!). Nëse shtoni edhe 0 në vëllimin e të dhënave, do të keni kohë për të fjetur.

Të shkojmë më thellë

Për referencë:

  • KĂ«rkimi nĂ« njĂ« tabelĂ« tĂ« mirĂ« hesh Ă«shtĂ« i mundĂ«sishĂ«m pĂ«r O(1).
  • KĂ«rkimi nĂ« njĂ« pemĂ« tĂ« mirĂ« tĂ« balancuar jep rezultat pĂ«r O(log(n)).
  • KĂ«rkimi nĂ« njĂ« varg jep rezultat pĂ«r O(n).
  • Algoritmet mĂ« tĂ« mira tĂ« renditjes kanĂ« kompleksitet O(n * log(n)).
  • NjĂ« algoritĂ«m i dobĂ«t i renditjes ka kompleksitet O(n2).

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

Ekzistojnë disa lloje të kompleksitetit temporal të algoritmit:

  • scenar i rastit mesatar
  • nĂ« variantin mĂ« tĂ« mirĂ« tĂ« mundshĂ«m
  • dhe skenari mĂ« i keq

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

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

  • pĂ«rdorimin e memories nga algoritmi
  • pĂ«rdorimin e hyrjes / daljes nĂ« disk nga algoritmi

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

  • n4: kjo Ă«shtĂ« tmerrĂ«sisht! Disa nga algoritmet e pĂ«rmendura kanĂ« njĂ« kompleksitet tĂ« tillĂ«.
  • 3n: kjo Ă«shtĂ« akoma mĂ« keq! NjĂ« nga algoritmet qĂ« do tĂ« shohim nĂ« mes tĂ« kĂ«tij artikulli ka kĂ«tĂ« kompleksitet (dhe pĂ«rdoret vĂ«rtet nĂ« shumĂ« baza tĂ« dhĂ«nash).
  • faktorial n: nuk do tĂ« merrni asnjĂ«herĂ« 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 e punĂ«s...

Shënim: ju kam dhënë një përkufizim jo të vërtetë të shenjes për "O të madhe", por thjesht një ide. Ju mund të lexoni këtë artikull në Wikipedia për një definim të vërtetë (asimptotik).

MergeSort (Sizimi me bashkim)

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

Ka disa algorithma të mirë sqarimi, prandaj do të ndalem te më i rëndësishmi: sizi me bashkim. Ndoshta tani nuk e kuptoni pse renditja e të dhënave është e dobishme, por duhet ta kuptoni pas pjesës që i dedikohet optimizimit të pyetjeve. Për më tepër, kuptimi i sizit me bashkim do të na ndihmojë më vonë të kuptojmë operacionin e përgjithshëm të bashkimit të bordit të të dhënave, quajtur bashkë join (bashkimi me bashkim).

Bashkimi

Si shumë algorithma të dobishëm, sizimi me bashkim bazohet në një strategji: bashkimi i 2 masivave të renditur me madhësi N/2 në një masiv të renditur me N elemente kushton vetëm N operacione. Ky operacion quhet bashkimi.

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

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

Në këtë vizatim, bëhet e qartë se për të ndërtuar masivin e renditur përfundimtar nga 8 elementë ju nevojitet të bëni vetëm një iterim në 2 masa 4-elementëshe. Duke qenë se të dy masat 4-elementëshe tashmë janë të renditura:

  • 1) ju krahasoni tĂ« dy elementet aktuale nĂ« dy masat (nĂ« fillim tĂ« aktualit = tĂ« parit)
  • 2) pastaj merrni mĂ« tĂ« voglin, pĂ«r ta vendosur atĂ« nĂ« njĂ« masiv prej 8 elementesh
  • 3) dhe kaloni tek elementi i ardhshĂ«m nĂ« masiv, ku e keni marrĂ« elementin mĂ« tĂ« vogĂ«l
  • dhe pĂ«rsĂ«ritni 1, 2, 3, derisa tĂ« arrini tek elementi i fundit tĂ« njĂ«rit nga masivat.
  • Pastaj merrni elementĂ«t e tjerĂ« nga masivi tjetĂ«r, pĂ«r t'i vendosur nĂ« masivin prej 8 elementesh.

Kjo funksionon, sepse të dy masivët me 4 elementë janë të rregulluar, dhe prandaj nuk keni nevojë të "ktheheni" në këta masiva.

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

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

   // thirrjet rekursive
   [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 masivëve të vogla të renditur në një më të madh
   array result := merge(new_left_array,new_right_array);
   return result;

Sortimi 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 fillestare (shënim: ky lloj algoritmi quhet ndaj dhe sundo). Nëse nuk e kuptoni këtë algoritëm, mos u shqetësoni; unë nuk e kuptova këtë herën e parë që e pashë. Nëse mund t'ju ndihmojë, e shikoj këtë algoritëm si një algoritëm me dy faza:

  • Faza e ndarjes, ku masivi ndahet nĂ« masive mĂ« tĂ« vogla
  • Faza e renditjes, ku masivĂ«t e vegjĂ«l bashkohen (duke pĂ«rdorur bashkimin), pĂ«r tĂ« formuar njĂ« masiv mĂ« tĂ« madh.

Faza e ndarjes

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

Në fazën e ndarjes, masivi ndahet në masive uniat që realizohen në 3 hapa. Numri formal i hapave është log(N) (pasi N=8, log(N) = 3).

Si e di këtë?

UnĂ« jam gjenial! NĂ« njĂ« fjali – matematikĂ«. Ideja Ă«shtĂ« qĂ« çdo hap ndahet madhĂ«sinĂ« e masivit fillestar nĂ« 2. Numri i hapave Ă«shtĂ« sa herĂ« mund tĂ« ndahen masivi fillestar nĂ« dy. Kjo Ă«shtĂ« pĂ«rkufizimi i saktĂ« i logaritmit (me bazĂ« 2).

Faza e renditjes

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

Në fazën e renditjes filloni me masivë uniat (me një element). Gjatë çdo etape, ju aplikoni disa operacione bashkimi, dhe kosto totale është N = 8 operacione:

  • NĂ« etapĂ«n e parĂ« keni 4 bashkime, qĂ« kushtojnĂ« 2 operacione çdo njĂ«si
  • NĂ« hapin e dytĂ«, keni 2 bashkime, qĂ« kushtojnĂ« 4 operacione çdo njĂ«si
  • NĂ« hapin e tretĂ«, keni 1 bashkim, qĂ« kushton 8 operacione

Duke pasur log(N) hapa, kosto totale N * log(N) operacione.

Avantazhet e renditjes me bashkim

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

Sepse:

  • Ju mund ta modifikoni atĂ« pĂ«r tĂ« reduktuar hapĂ«sirĂ«n e memories, nĂ« kĂ«tĂ« mĂ«nyrĂ« qĂ« tĂ« mos krijoni masive tĂ« reja, por tĂ« ndryshoni direkt masivin hyrĂ«s.

ShĂ«nim: ky lloj algoritmi quhet në—vend (renditje pa hapĂ«sirĂ« shtesĂ«).

  • Ju mund ta modifikoni atĂ« pĂ«r tĂ« pĂ«rdorur si hapĂ«sirĂ«n e diskut ashtu edhe njĂ« sasi tĂ« vogĂ«l tĂ« memories pa kosto tĂ« larta pĂ«r hyrje/dalje disk.

Shënim: ky lloj algoritmi quhet renditja jashtme.

  • Ju mund ta modifikoni atĂ« pĂ«r tĂ« funksionuar nĂ« disa procese / kanale / serverĂ«.

Për shembull, renditja e bashkimit të shpërndarë është një nga komponentët kyç Hadoop (që është një strukturë në të dhëna të mëdha).

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

Ky algoritëm i renditjes përdoret në shumicën (nëse jo në të gjitha) bazat e të dhënave, por nuk është i vetmi. Nëse dëshiron të dish më shumë, mund të lexosh këtë punim hulumtimi, që diskuton përfitimet dhe disavantazhet e algoritmeve të zakonshme të renditjes në bazat e të dhënave.

Masivi, Pema dhe Harta e Thesareve

Tani që e kuptojmë idenë e kompleksitetit të kohës dhe renditjes, duhet t'ju tregoj për 3 struktura të dhënave. Këto janë themeli i bazave të të dhënave moderne.. Do të prezantoj gjithashtu konceptin indeksit të bazës së të dhënave.

Matiç

Masivi dy-dimensional është struktura më e thjeshtë e të dhënave. Një tabelë mund të konsiderohet si një masiv. Për shembull:

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

Ky masiv 2-dimensional përfaqëson një tabelë me rreshta dhe kolona:

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

Kështu është e lehtë të ruash dhe të vizualizosh të dhëna, por, kur nevojitet të gjejmë një vlerë të caktuar, kjo nuk funksionon.

PĂ«r shembull, po tĂ« duash tĂ« gjesh tĂ« gjithĂ« djemtĂ« qĂ« punojnĂ« nĂ« MbretĂ«rinĂ« e Bashkuar, do tĂ« duhet tĂ« shikosh çdo rresht pĂ«r tĂ« parĂ« nĂ«se ai rresht i pĂ«rket MbretĂ«risĂ« sĂ« Bashkuar. Kjo do t'ju kushtojĂ« N operacione, ku N — numri i rreshtave, qĂ« nuk Ă«shtĂ« keq, por a mund tĂ« jetĂ« njĂ« rrugĂ« mĂ« e shpejtĂ«? Tani ka ardhur koha tĂ« njihemi me pemĂ«t.

Shënim: shumica e bazave të të dhënave moderne ofrojnë struktura të zgjeruara për ruajtjen efikase të tabelave: heap-organizedtables dhe index-organizedtables. Por kjo nuk zgjidh problemin e kërkimit të shpejtë të një kushti të caktuar në një grup kolonash.

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

Një pemë binare kërkimi ë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Ă« ruhen nĂ« nĂ«npemĂ«n e majtĂ«
  • mĂ« i vogĂ«l se tĂ« gjithĂ« çelĂ«sat qĂ« ruhen nĂ« nĂ«npemĂ«n e djathtĂ«

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

Ideja

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

Kjo pemë ka N = 15 elemente. Supozoni se po kërkoj 208:

  • Filloj me rrĂ«njĂ«n, çelĂ«si i sĂ« cilĂ«s Ă«shtĂ« 136. Duke qenĂ« se 136<208, shikoj nĂ« nĂ«npemĂ«n e djathtĂ« tĂ« nyjĂ«s 136.
  • 398>208, prandaj shikoj nĂ« nĂ«npemĂ«n e majtĂ« tĂ« nyjĂ«s 398
  • 250>208, prandaj shikoj nĂ« nĂ«npemĂ«n e majtĂ« tĂ« nyjĂ«s 250
  • 200<208, prandaj shikoj nĂ« nĂ«npemĂ«n e djathtĂ« tĂ« nyjĂ«s 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, të themi, po kërkoj 40

  • Filloj me rrĂ«njĂ«n, çelĂ«si i sĂ« cilĂ«s Ă«shtĂ« 136. Duke qenĂ« se 136 > 40, shikoj nĂ« nĂ«npemĂ«n e majtĂ« tĂ« nyjĂ«s 136.
  • 80 > 40, prandaj shikoj nĂ« nĂ«npemĂ«n e majtĂ« tĂ« nyjĂ«s 80
  • 40= 40, nyja ekziston. Nxjerr identifikuesin e rreshtit brenda nyjĂ«s (kjo nuk Ă«shtĂ« e pranishme nĂ« figurĂ«) dhe shikoj nĂ« tabelĂ« pĂ«r identifikuesin e dhĂ«nĂ« tĂ« rreshtit.
  • Dije identifikuesin e rreshtit, mĂ« lejon tĂ« di se ku ndodhen tĂ« dhĂ«nat nĂ« tabelĂ«, dhe prandaj mund t'i marr ato menjĂ«herĂ«.

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

Të kthehemi te problemi ynë

Por kjo është shumë abstrakte, prandaj le të kthehemi te problemi ynë. 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 doni tĂ« dini kush punon nĂ« MbretĂ«rinĂ« e Bashkuar
  • shikoni pemĂ«n pĂ«r tĂ« marrĂ« nyjĂ«n qĂ« pĂ«rfaqĂ«son MbretĂ«rinĂ« e Bashkuar
  • nĂ« brendĂ«si tĂ« "UKnode" do tĂ« gjeni vendndodhjen e regjistrimeve tĂ« punonjĂ«sve nĂ« MbretĂ«rinĂ« e Bashkuar.

Kërkimi i këtij do të kërkojë log(N) operacione në vend të N operacioneve nëse e përdorni drejtpërdrejt atë si një array. Ajo që sapo paraqitet ishte indeksi i bazës së të dhënave.

Ju mund të ndërtoni një pemë indeksi për çdo grup fushash (string, numër, 2 strings, numër dhe string, datë...) për sa kohë që keni një funksion për krahasimin e çelësave (dmth. grupet e fushave) në mënyrë që të mund të vendosni renditjen mes çelësave (gjë që ndodh për çdo lloj bazë të dhënash të tipeve themelore).

B+TreeIndex

Megjithëse kjo pemë funksionon mirë për marrjen e një vlere të caktuar, ekziston një PROBLEM I MADH kur ju nevojitet të merrni disa elemente midis dy vlerave. Kjo do të kushtojë O(N) sepse do t'ju duhet të shikoni çdo nyje në pemë dhe të kontrolloni nëse është 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 hyrje-dalje në disk, pasi do t'ju duhet të lexoni tërë pemën. Na nevojitet një mënyrë për të kryer në mënyrë efikase kërkesën për intervalin. 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 (vendndodhja e rreshtave nĂ« tabelĂ«n e lidhur)
  • nyjet e tjera janĂ« kĂ«tu pĂ«r tĂ« drejtuar nĂ« nyjen e duhur gjashtĂ« gjatĂ« kĂ«rkimit.

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

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

Me këtë B+Tree, nëse po kërkoni vlera nga 40 deri në 100:

  • Ju 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 mblidhni pasardhĂ«sit e 40, duke pĂ«rdorur lidhje tĂ« drejtpĂ«rdrejta me pasardhĂ«sit, derisa tĂ« arrini nĂ« 100.

Supozoni se keni gjetur M pasardhĂ«s, dhe pemĂ«s ka N nyje. KĂ«rkimi i njĂ« nyje tĂ« caktuar kushton log(N) si nĂ« pemĂ«n e mĂ«parshme. Por, pasi tĂ« merrni kĂ«tĂ« nyje, do tĂ« merrni M pasardhĂ«s nĂ« M operacione me lidhje me pasardhĂ«sit e tyre. Ky kĂ«rkim kushton vetĂ«m M+log(N) operacioneve krahasuar me N operacionet e pemĂ«s sĂ« mĂ«parshme. MĂ« shumĂ« se kaq, nuk keni nevojĂ« tĂ« lexoni gjithĂ« pemĂ«n (vetĂ«m M + log (N) nod), qĂ« do tĂ« thotĂ« pĂ«rdorim mĂ« i vogĂ«l i diskut. NĂ«se M Ă«shtĂ« e vogĂ«l (p.sh. 200 rreshta) dhe N Ă«shtĂ« i madh (1 000 000 rreshta), kjo do tĂ« jetĂ« NËN DIFFERECË TË MADHE.

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

  • duhet tĂ« mbani rendin midis nodĂ«ve brenda pemĂ«s B+Tree, nd otherwise, nuk do tĂ« jeni nĂ« gjendje tĂ« gjeni nodĂ«t brenda pemĂ«s qĂ« nuk Ă«shtĂ« e renditur.
  • duhet tĂ« ruani numrin minimal tĂ« niveleve nĂ« B+Tree, nd otherwise, kompleksiteti temporal nĂ« O (log (N)) do tĂ« bĂ«het O (N).

Me fjalë të tjera, B+Tree duhet të jetë e organizuar vetë dhe e balancuar. Për fat të mirë, kjo është e mundur me operacione të mençura të fshirjes dhe vendosjes. Por kjo vjen me një kosto të madhe: vendosja dhe fshirja në pemën B+ ndodhin në O (log (N)). Kjo është arsyeja pse disa prej jush kanë dëgjuar se përdorimi i një numri të madh indekseve nuk është një ide shumë e mirë. Vërtetë, ngadalësoni vendosjen / përditësimin / fshirjen e shpejtë të rreshtit në tabelë, pasi që baza e të dhënave duhet të përditësojë indeksat e tabelës me operacione të kushtueshme O (log (N)) për çdo indeks. Më shumë se kaq, shtimi i indekseve do të thotë 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 mbi B+Pemën. Nëse dëshironi një shembull zbatimi të B+Tree në një bazë të dhënash, shihni këtë artikull dhe këtë artikull nga zhvilluesi i njohur të MySQL. Të dy përqendrohen në mënyrën se si InnoDB (motorin MySQL) përpunon indekset.

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

Hashtable (Tabela e Hash)

Struktura jonë e fundit e rëndësishme të dhënash është tabela e hash. Kjo është shumë e dobishme kur dëshironi të kërkoni shpejt vlera. Më shumë se kaq, kuptimi i tabelës së hash 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 i hashit ( bashkimi i hash). Kjo strukturë e të dhënave gjithashtu përdoret nga baza e të dhënave për të ruajtur disa gjëra të brendshme (p.sh., tabela e blokadës ose pooli i tamponëve, ne do t'i shohim 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, ju nevojitet të përcaktoni:

  • çelĂ«si pĂ«r elementet tuaj
  • funksioni hesh pĂ«r çelĂ«sat. Hesh-at e llogaritur tĂ« çelĂ«save japin vendndodhjen e elementeve (tĂ« quajtur segmente ).
  • funksioni 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.

Shembulli i thjeshtë

Le të marrim një shembull ilustrues:

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

Kjo tabelë hesh ka 10 segmente. Pasi unë jam lenë, kam ilustruar vetëm 5 segmente, por e di që jeni të zgjuar, prandaj do t'ju lë të imagjinoni 5 të tjera vetë. Kam përdorur funksionin hesh sipas modulus 10 të çelësit. Në fjalë të tjera, mbaj vetëm_numrin_ e fundit të çelësit të elementit për të gjetur segmentin:

  • 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 barazimi midis dy numrave të plotë.

Supozoni se doni të merrni elementin 78:

  • Tabela e heshit llogarit kodin hesh pĂ«r 78, i cili Ă«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 hesh, dhe tjetra pĂ«r gjetjen e elementit brenda segmentit).

Tani, le të supozojmë se doni të merrni elementin 59:

  • Tabela e heshit llogarit kodin hesh pĂ«r 59, i cili Ă«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 duhur.
  • Duke pĂ«rdorur tĂ« njĂ«jtĂ«n logjikĂ«, merret elementi i dytĂ« (9), i treti (79), 
, i fundit (29).
  • Elementi nuk Ă«shtĂ« gjetur.
  • KĂ«rkimi kushtoi 7 operacione.

Funksioni i mirë hesh

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

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

Në shembulin 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:

  • njĂ« varg (p.sh. - mbiemri)
  • 2 vargje (p.sh. - mbiemri dhe emri)
  • 2 rreshta dhe data (p.sh. - mbiemri, emri dhe data e lindjes)
  • 


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

Array vs tabela hash

Pse të mos përdorim një array?

Hmm, pyetje e mirë.

  • Tabela hash mund tĂ« jetĂ« pjesĂ«risht e ngarkuar nĂ« memorie, ndĂ«rsa segmentet e tjera mund tĂ« mbeten nĂ« disk.
  • Me njĂ« array duhet tĂ« pĂ«rdorni hapĂ«sirĂ« tĂ« vazhdueshme nĂ« memorie. NĂ«se ngarkoni njĂ« tabelĂ« tĂ« madhe Ă«shtĂ« shumĂ« e vĂ«shtirĂ« tĂ« gjeni mjaft hapĂ«sirĂ« tĂ« vazhdueshme.
  • PĂ«r tabelĂ«n hash, mund tĂ« zgjidhni çelĂ«sin e duhur (p.sh. vendin dhe mbiemrin e personit).

Për informacion të mëtejshëm, mund të lexoni artikullin mbi JavaHashMap, i cili është një implementim efektiv i tabelës hash; nuk është e nevojshme të kuptoni Java për të kuptuar konceptet e paraqitura në këtë artikull.

Burimi: habr.com

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