Përshëndetje, Habr! Unë paraqes në vëmendjen tuaj një përkthim të artikullit
"Si funksionon një bazë të dhënash relacionale".

Kur bëhet fjalë për bazat e të dhënave relacionale, nuk mund të mos mendoj se diçka mungon. Ato përdoren kudo. Ka shumë baza të të dhënave të ndryshme në dispozicion, nga SQLite i vogël dhe i dobishëm deri te Teradata i fuqishëm. Por ka vetëm disa artikuj që shpjegojnë se si funksionon baza e të dhënave. Ju mund të kërkoni për veten tuaj duke përdorur "howdoesarelationaldatabasework" për të parë sa pak rezultate ka. Për më tepër, këta artikuj janë të shkurtër. Nëse jeni duke kërkuar për teknologjitë më të fundit të zhurmës (BigData, NoSQL ose JavaScript), do të gjeni artikuj më 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'u shpjeguar jashtë kurseve universitare, punimeve kërkimore dhe librave?

Si zhvillues, e urrej përdorimin e diçkaje 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ë viteve, kam shpenzuar qindra orë për të kuptuar me të vërtetë këto kuti të zeza të çuditshme që përdor çdo ditë. Bazat e të dhënave relacionale shumë interesante sepse ata bazuar në koncepte të dobishme dhe të ripërdorshme. Nëse jeni të interesuar të kuptoni një bazë të dhënash, por nuk keni pasur kurrë kohë ose prirje për të gërmuar në këtë temë të gjerë, duhet ta shijoni këtë artikull.

Edhe pse titulli i këtij artikulli është i qartë, Qëllimi i këtij artikulli nuk është të kuptojmë se si të përdorim bazën e të dhënave. Rrjedhimisht, tashmë duhet të dini se si të shkruani një kërkesë të thjeshtë lidhjeje dhe pyetje themelore I MADH; përndryshe mund të mos e kuptoni këtë artikull. Kjo është e vetmja gjë që duhet të dini, unë do të shpjegoj pjesën tjetër.

Do të filloj me disa baza të shkencës kompjuterike, siç është kompleksiteti kohor i algoritmeve (BigO). E di që disa prej jush e urrejnë këtë koncept, por pa të nuk do të jeni në gjendje të kuptoni ndërlikimet brenda bazës së të dhënave. Meqenëse kjo është një temë e madhe, Unë do të fokusohem në ajo që unë mendoj se është e rëndësishme: si përpunohet baza e të dhënave SQL kërkesë. Unë thjesht do të prezantoj konceptet bazë të bazës së të dhënavenë mënyrë që në fund të artikullit të keni një ide se çfarë po ndodh nën kapuç.

Meqenëse ky është një artikull i gjatë dhe teknik që përfshin shumë algoritme dhe struktura të dhënash, merrni kohën tuaj për ta lexuar. Disa koncepte mund të jenë të vështira për t'u kuptuar; ju mund t'i kaloni ato dhe të merrni ende idenë e përgjithshme.

Për më të diturit nga ju, ky artikull është i ndarë në 3 pjesë:

Pasqyrë e komponentëve të bazës së të dhënave të nivelit të ulët dhe të nivelit të lartë
Pasqyrë e procesit të optimizimit të pyetjeve
Pasqyrë e Transaksioneve dhe Menaxhimit të Pool Buffer

Kthehu te bazat

Vite më parë (në një galaktikë larg, shumë larg...), zhvilluesit duhej të dinin saktësisht numrin e operacioneve që po kodonin. Ata i dinin përmendsh algoritmet dhe strukturat e tyre të të dhënave, sepse nuk mund të përballonin shpenzimin e kot CPU-së dhe kujtesës së kompjuterëve të tyre të ngadaltë.

Në këtë pjesë, unë do t'ju kujtoj disa nga këto koncepte pasi ato janë thelbësore për të kuptuar bazën e të dhënave. Unë gjithashtu do të prezantoj konceptin indeksi i bazës së të dhënave.

O(1) vs O(n2)

Në ditët e sotme, shumë zhvilluesve nuk i intereson kompleksiteti kohor i algoritmeve... dhe kanë të drejtë!

Por kur keni të bëni me shumë të dhëna (nuk po flas për mijëra) ose nëse jeni duke luftuar në milisekonda, bëhet kritike për të kuptuar këtë koncept. Dhe siç mund ta imagjinoni, bazat e të dhënave duhet të merren me të dyja situatat! Unë nuk do t'ju bëj të shpenzoni më shumë kohë sesa duhet për të kuptuar çështjen. Kjo do të na ndihmojë të kuptojmë konceptin e optimizimit të bazuar në kosto më vonë (kosto i bazuar optimization).

koncept

Kompleksiteti kohor i algoritmit përdoret për të parë se sa kohë do të duhet për të ekzekutuar një algoritëm për një sasi të caktuar të dhënash. Për të përshkruar këtë kompleksitet, ne përdorim shënimin matematikor të madh O. Ky shënim përdoret me një funksion që përshkruan sa operacione i nevojiten një algoritmi për një numër të caktuar hyrjesh.

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

Në këtë rast, Nuk është sasia e të dhënave që ka rëndësi **, ndryshe ** si rritet numri i operacioneve me rritjen e vëllimit të të dhënave. Kompleksiteti kohor nuk siguron një numër të saktë të operacioneve, por është një mënyrë e mirë për të vlerësuar kohën e ekzekutimit.

Në këtë grafik mund të shihni numrin e operacioneve kundrejt sasisë së të dhënave hyrëse për lloje të ndryshme të kompleksiteteve kohore të algoritmit. Kam përdorur një shkallë logaritmike për t'i shfaqur ato. Me 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 konstant (përndryshe nuk do të quhej kompleksitet konstant).
O(hyni(n)) mbetet i ulët edhe me miliarda të dhëna.
Vështirësia më e madhe - O(n2), ku numri i operacioneve rritet me shpejtësi.
Dy ndërlikimet e tjera rriten po aq shpejt.

shembuj

Me një sasi të vogël të dhënash, ndryshimi midis O(1) dhe O(n2) është i papërfillshëm. Për shembull, le të themi se keni një algoritëm që duhet të përpunojë 2000 elementë.

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 operacione
Algoritmi O(n*log(n)) do t'ju kushtojë 14 operacione
Algoritmi O(n2) do t'ju kushtojë 4 operacione

Dallimi midis O(1) dhe O(n2) duket i madh (4 milionë operacione), por ju do të humbni një maksimum prej 2 ms, vetëm koha 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ë një problem në shumë projekte IT.

Siç thashë, është ende e rëndësishme të njohësh këtë koncept kur punohet me sasi të mëdha të dhënash. Nëse këtë herë algoritmi duhet të përpunojë 1 elementë (që nuk është aq 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 operacione
Algoritmi O(n*log(n)) do t'ju kushtojë 14 operacione
Algoritmi O(n2) do t'ju kushtojë 1 operacione

Nuk e kam bërë matematikën, por do të thoja që me algoritmin O(n2) keni kohë për të pirë një kafe (madje edhe dy!). Nëse shtoni një 0 tjetër në vëllimin e të dhënave, do të keni kohë të bëni një sy gjumë.

Le të shkojmë më thellë

Për informacionin tuaj:

Një kërkim i mirë i tabelës hash gjen një element në O(1).
Kërkimi i një peme të balancuar mirë prodhon rezultate në O(log(n)).
Kërkimi i një grupi prodhon rezultate në O(n).
Algoritmet më të mira të renditjes kanë kompleksitet O(n*log(n)).
Një algoritëm i keq klasifikimi ka kompleksitet O(n2).

Shënim: Në pjesët e mëposhtme do të shohim këto algoritme dhe struktura të dhënash.

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

skenari mesatar i rastit
skenari më i mirë
dhe skenari më i keq

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

Unë po flisja vetëm për kompleksitetin kohor të algoritmit, por kompleksiteti vlen edhe për:

konsumi i memories së algoritmit
Algoritmi i konsumit të I/O të diskut

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

n4: kjo është e tmerrshme! Disa nga algoritmet e përmendur e kanë këtë kompleksitet.
3n: kjo është edhe më keq! Një nga algoritmet që do të shohim në mes të këtij artikulli ka këtë kompleksitet (dhe në fakt përdoret në shumë baza të dhënash).
faktorial n: nuk do t'i merrni kurrë rezultatet tuaja edhe me një sasi të vogël të dhënash.
nn: Nëse hasni këtë kompleksitet, duhet të pyesni veten nëse kjo është me të vërtetë fusha juaj e aktivitetit...

Shënim: Nuk ju dhashë përkufizimin aktual të përcaktimit të madh O, vetëm një ide. Ju mund ta lexoni këtë artikull në Wikipedia për përkufizimin real (asimptotik).

MergeSort

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

Ka disa algoritme të mira të renditjes, kështu që unë do të përqendrohem në më të rëndësishmit: bashkoj renditje. Ju mund të mos e kuptoni pse renditja e të dhënave është e dobishme tani, por duhet ta kuptoni pas pjesës së optimizimit të pyetjeve. Për më tepër, kuptimi i renditjes së bashkimit do të na ndihmojë të kuptojmë më vonë operacionin e përbashkët të bashkimit të bazës së të dhënave të quajtur shkrihet të bashkohen (shoqata e bashkimit).

Shkrihet

Ashtu si shumë algoritme të dobishme, renditja e bashkimit mbështetet në një truk: kombinimi i 2 vargjeve të renditura me madhësi N/2 në një grup të renditur me elemente N kushton vetëm N operacione. Ky operacion quhet bashkim.

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

Kjo figurë tregon se për të ndërtuar grupin përfundimtar të renditur me 8 elementë, ju duhet vetëm të përsërisni një herë mbi 2 vargjet me 4 elementë. Meqenëse të dy grupet me 4 elementë janë të renditur tashmë:

1) ju krahasoni të dy elementët aktualë në dy grupe (në fillim rryma = së pari)
2) pastaj merrni më të voglin për ta vendosur në një grup me 8 elementë
3) dhe kaloni te elementi tjetër në grup ku morët elementin më të vogël
dhe përsëritni 1,2,3 derisa të arrini elementin e fundit të njërës prej vargjeve.
Pastaj ju merrni elementët e mbetur të grupit tjetër për t'i vendosur ato në një grup me 8 elementë.

Kjo funksionon sepse të dy grupet me 4 elementë janë të renditur dhe kështu nuk keni nevojë të "ktheheni prapa" në ato vargje.

Tani që e kuptojmë mashtrimin, këtu është pseudokodi im për bashkim:

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;

Renditja e bashkimit ndan një problem në probleme më të vogla dhe më pas gjen rezultatet e problemeve më të vogla për të marrë rezultatin e problemit origjinal (shënim: ky lloj algoritmi quhet përça dhe sundo). Nëse nuk e kuptoni këtë algoritëm, mos u shqetësoni; Nuk e kuptova herën e parë që e pashë. Nëse mund t'ju ndihmojë, unë e shoh këtë algoritëm si një algoritëm dyfazor:

Faza e ndarjes, ku grupi ndahet në vargje më të vogla
Faza e renditjes është ajo ku grupet e vogla kombinohen (duke përdorur bashkimin) për të formuar një grup më të madh.

Faza e ndarjes

Në fazën e ndarjes, grupi ndahet në vargje unitare në 3 hapa. Numri formal i hapave është log(N) (pasi N=8, log(N) = 3).

Si e di këtë?

Unë jam gjeni! Me një fjalë - matematikë. Ideja është që çdo hap të ndajë madhësinë e grupit origjinal me 2. Numri i hapave është numri i herëve që mund ta ndani grupin origjinal në dy. Ky është përkufizimi i saktë i një logaritmi (baza 2).

Faza e renditjes

Në fazën e renditjes, filloni me vargje unitare (me një element). Gjatë çdo hapi ju aplikoni operacione të shumta bashkimi dhe kostoja totale është N = 8 operacione:

Në fazën e parë keni 4 bashkime që 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

Meqenëse ka hapa log(N), kostoja totale N * operacionet log(N)..

Avantazhet e llojit të bashkimit

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

Sepse:

Mund ta ndryshoni për të reduktuar gjurmën e kujtesës në mënyrë që të mos krijoni vargje të reja, por të modifikoni drejtpërdrejt grupin e hyrjes.

Shënim: ky lloj algoritmi quhet in-vend (rendisim pa memorie shtesë).

Ju mund ta ndryshoni atë për të përdorur hapësirën në disk dhe një sasi të vogël memorie në të njëjtën kohë pa shkaktuar shpenzime të mëdha të hyrjes/daljes së diskut. Ideja është që të ngarkohen në memorie vetëm ato pjesë që aktualisht janë duke u përpunuar. Kjo është e rëndësishme kur ju duhet të renditni një tabelë me shumë gigabajt me vetëm një tampon memorie prej 100 megabajt.

Shënim: ky lloj algoritmi quhet lloj i jashtëm.

Mund ta ndryshoni për të ekzekutuar në procese/thread/server të shumtë.

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

Ky algoritëm mund ta kthejë plumbin në ar (me të vërtetë!).

Ky algoritëm klasifikimi përdoret në shumicën (nëse jo të gjitha) bazat e të dhënave, por nuk është i vetmi. Nëse dëshironi të dini më shumë, mund ta lexoni këtë punë kërkimore, i cili diskuton të mirat dhe të këqijat e algoritmeve të zakonshme të renditjes së bazës së të dhënave.

Array, Tree dhe Hash Tabela

Tani që e kuptojmë idenë e kompleksitetit kohor dhe renditjes, duhet t'ju tregoj për 3 struktura të dhënash. Kjo është e rëndësishme sepse ata janë baza e bazave moderne të të dhënave. Unë gjithashtu do të prezantoj konceptin indeksi i bazës së të dhënave.

Array

Një grup dydimensional është struktura më e thjeshtë e të dhënave. Një tabelë mund të konsiderohet si një grup. Për shembull:

Ky grup 2-dimensional është një tabelë me rreshta dhe kolona:

Çdo rresht përfaqëson një entitet
Kolonat ruajnë vetitë që përshkruajnë entitetin.
Çdo kolonë ruan të dhëna të një lloji të caktuar (numër i plotë, varg, datë...).

Kjo është e përshtatshme për ruajtjen dhe vizualizimin e të dhënave, megjithatë, kur ju duhet të gjeni një vlerë specifike, kjo nuk është e përshtatshme.

Për shembull, nëse dëshironi të gjeni të gjithë djemtë që punojnë në MB, do t'ju duhet të shikoni çdo rresht për të përcaktuar nëse ai rresht i përket MB. Do t'ju kushtojë N transaksioneKu N - numri i rreshtave, i cili nuk është i keq, por a mund të ketë një mënyrë më të shpejtë? Tani është koha që ne të njihemi me pemët.

Shënim: Shumica e bazave të të dhënave moderne ofrojnë vargje të zgjeruara për ruajtjen e tabelave në mënyrë efikase: tabela të organizuara nga grumbulli dhe tabela të organizuara me indeks. Por kjo nuk e ndryshon problemin e gjetjes së shpejtë të një kushti specifik në një grup kolonash.

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

Një pemë kërkimi binar është një pemë binare me një veti të veçantë, çelësi në secilën nyje duhet të jetë:

më i madh se të gjithë çelësat e ruajtur në nënpemën e majtë
më pak se të gjithë çelësat e ruajtur në nënpemën e duhur

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

Ide

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. Që nga viti 136<208, shikoj nënpemën e djathtë të nyjës 136.
398>208 prandaj po shikoj në nënpemën e majtë të nyjës 398
250>208 prandaj po shikoj në nënpemën e majtë të nyjës 250
200<208, prandaj po shikoj nënpemën e djathtë të nyjës 200. Por 200 nuk ka nënpemë të djathtë, vlera nuk ekziston (sepse nëse ekziston, do të jetë në nënpemën e djathtë 200).

Tani le të themi se po kërkoj 40

Filloj nga rrënja, çelësi i së cilës është 136. Që nga 136 > 40, shikoj nënpemën e majtë të nyjës 136.
80 > 40, prandaj po shikoj në nënpemën e majtë të nyjës 80
40 = 40, nyja ekziston. Unë marr ID-në e rreshtit brenda nyjës (nuk tregohet në foto) dhe shikoj në tabelë ID-në e rreshtit të dhënë.
Njohja e ID-së së rreshtit më lejon të di saktësisht se ku janë të dhënat në tabelë, në mënyrë që t'i marr ato menjëherë.

Në fund, të dy kërkimet do të më kushtojnë numrin e niveleve brenda pemës. Nëse e lexoni me kujdes pjesën për renditjen e bashkimit, duhet të shihni se ka nivele log(N). Doli qe, regjistri i kostos së kërkimit (N), jo keq!

Le të kthehemi te problemi ynë

Por kjo është shumë abstrakte, ndaj le të kthehemi te problemi ynë. Në vend të një numri të plotë të thjeshtë, imagjinoni një varg që përfaqëson vendin e dikujt në tabelën e mëparshme. Le të themi se keni një pemë që përmban fushën "vendi" (kolona 3) e tabelës:

Nëse doni të dini se kush punon në MB
ju shikoni pemën për të marrë nyjen që përfaqëson Britaninë e Madhe
brenda "UKnode" do të gjeni vendndodhjen e të dhënave të punëtorëve në MB.

Ky kërkim do të kushtojë operacione log(N) në vend të operacioneve N nëse përdorni grupin drejtpërdrejt. Ajo që sapo prezantove ishte indeksi i bazës së të dhënave.

Ju mund të ndërtoni një pemë indeksi për çdo grup fushash (varg, numër, 2 rreshta, numër dhe varg, data...) për sa kohë që keni një funksion për të krahasuar çelësat (p.sh. grupet e fushave) në mënyrë që të vendosni rendit midis çelësave (që është rasti për çdo lloj bazë në bazën e të dhënave).

B+TreeIndex

Ndërsa kjo pemë funksionon mirë për marrjen e një vlere specifike, ka një problem të madh kur ju nevojitet merrni shumë elementë 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.sh. me një kalim të porositur të pemës). Për më tepër, ky operacion nuk është i përshtatshëm për hyrje/daljen e diskut pasi duhet të lexoni të gjithë pemën. Ne duhet të gjejmë një mënyrë për të ekzekutuar në mënyrë efikase kërkesë për varg. 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ë një pemë B+Tree:

vetëm nyjet më të ulëta (gjethe) ruaj informacionin (vendndodhja e rreshtave në tabelën përkatëse)
pjesa tjetër e nyjeve janë këtu për rrugëtim në nyjen e duhur gjatë kërkimit.

Siç mund ta shihni, ka më shumë nyje këtu (dy herë). Në të vërtetë, ju keni nyje shtesë, "nyje vendimi", që do t'ju ndihmojnë të gjeni nyjen e saktë (e cila ruan vendndodhjen e rreshtave në tabelën përkatëse). Por kompleksiteti i kërkimit është akoma O(log(N)) (ka vetëm një nivel më shumë). Dallimi i madh është se nyjet në nivelin më të ulët janë të lidhura me pasardhësit e tyre.

Me këtë B+Tree, nëse jeni duke kërkuar për vlerat midis 40 dhe 100:

Thjesht duhet të kërkoni 40 (ose vlerën më të afërt pas 40 nëse 40 nuk ekziston) siç keni bërë me pemën e mëparshme.
Më pas mblidhni 40 trashëgimtarë duke përdorur lidhjet e drejtpërdrejta të trashëgimtarëve derisa të arrini 100.

Le të themi se ju gjeni M pasues dhe pema ka N nyje. Gjetja e një nyje specifike kushton log(N) si pema e mëparshme. Por sapo të merrni këtë nyje, do të merrni M-pasardhësit në operacionet M me referenca për pasardhësit e tyre. Ky kërkim kushton vetëm M+log(N) operacionet në krahasim me operacionet N në pemën e mëparshme. Për më tepër, nuk keni nevojë të lexoni pemën e plotë (vetëm nyjet M+log(N), që do të thotë më pak përdorim të diskut. Nëse M është i vogël (p.sh. 200 rreshta) dhe N është i madh (1 rreshta), do të ketë një ndryshim të madh.

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

ju duhet të ruani rendin midis nyjeve brenda një peme B+, përndryshe nuk do të jeni në gjendje t'i gjeni nyjet brenda një peme të pa sortuar.
ju duhet të mbani numrin minimal të mundshëm të niveleve në B+Tree, përndryshe kompleksiteti kohor O(log(N)) bëhet O(N).

Me fjalë të tjera, B+Tree duhet të jetë vetë-renditëse dhe e ekuilibruar. Për fat të mirë, kjo është e mundur me operacionet inteligjente të fshirjes dhe futjes. Por kjo ka një kosto: futjet dhe fshirjet në një pemë B+ kushtojnë O(log(N)). Kjo është arsyeja pse disa prej jush e kanë dëgjuar këtë përdorimi i shumë indekseve nuk është një ide e mirë. Vërtet, po ngadalësoni futjen/përditësimin/fshirjen e shpejtë të një rreshti në një tabelësepse baza e të dhënave duhet të përditësojë indekset e tabelës duke përdorur një operacion të shtrenjtë O(log(N)) për çdo indeks. Për më tepër, shtimi i indekseve do të thotë më shumë ngarkesë pune për menaxher transaksionesh (do të përshkruhet në fund të artikullit).

Për më shumë detaje, mund të shihni artikullin e Wikipedia-s B+Pemë. Nëse dëshironi një shembull të zbatimit të B+Tree në një bazë të dhënash, hidhini një sy Ky artikull и Ky artikull nga një zhvillues kryesor i MySQL. Ata të dy fokusohen në mënyrën se si InnoDB (motori MySQL) trajton indekset.

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

Hashtable

Struktura jonë e fundit e rëndësishme e të dhënave është tabela hash. Kjo është shumë e dobishme kur dëshironi të kërkoni shpejt vlerat. Për më tepër, të kuptuarit e një tabele hash do të na ndihmojë të kuptojmë më vonë një operacion të përbashkët të bashkimit të bazës së të dhënave të quajtur një bashkim hash ( hash bashkohu). Kjo strukturë e të dhënave përdoret gjithashtu nga baza e të dhënave për të ruajtur disa gjëra të brendshme (p.sh. tavolinë mbyllëse ose pishinë tampon, do t'i shohim të dyja këto koncepte më vonë).

Një tabelë hash është një strukturë e të dhënave që gjen shpejt një element me çelësin e saj. Për të ndërtuar një tabelë hash ju duhet të përcaktoni:

ключ për elementët tuaj
funksion hash për çelësat. Hash-et e llogaritura të çelësave japin vendndodhjen e elementeve (të quajtur segmente ).
funksion për krahasimin e çelësave. Pasi të keni gjetur segmentin e duhur, duhet të gjeni elementin që kërkoni brenda segmentit duke përdorur këtë krahasim.

Shembull i thjeshtë

Le të marrim një shembull të qartë:

Kjo tabelë hash ka 10 segmente. Për shkak se jam dembel, kam fotografuar vetëm 5 segmente, por e di që je i zgjuar, ndaj do të të lë të fotografosh vetë 5 të tjerat. Kam përdorur një modul 10 të funksionit hash të çelësit. Me fjalë të tjera, ruaj vetëm shifrën e fundit të çelësit të elementit për të gjetur segmentin e tij:

nëse shifra e fundit është 0, elementi bie në segmentin 0,
nëse shifra e fundit është 1, elementi bie në segmentin 1,
nëse shifra e fundit është 2, elementi bie në zonën 2,
...

Funksioni i krahasimit që përdora është thjesht barazia midis dy numrave të plotë.

Le të themi se dëshironi të merrni elementin 78:

Tabela hash llogarit kodin hash për 78, që është 8.
Tabela hash shikon segmentin 8 dhe elementi i parë që gjen është 78.
Ajo ju kthen artikullin 78
Kërkimi kushton vetëm 2 operacione (njëra për të llogaritur vlerën hash dhe tjetra për të kërkuar elementin brenda segmentit).

Tani le të themi se dëshironi të merrni elementin 59:

Tabela hash llogarit kodin hash për 59, që është 9.
Tabela hash kërkon në segmentin 9, elementi i parë i gjetur është 99. Meqenëse 99!=59, elementi 99 nuk është një element i vlefshëm.
Duke përdorur të njëjtën logjikë, merret elementi i dytë (9), i treti (79), ..., i fundit (29).
Elementi nuk u gjet.
Kërkimi kushtoi 7 operacione.

Funksion i mirë hash

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

Nëse tani ndryshoj modulin e funksionit hash 1 të çelësit (d.m.th., duke marrë 000 shifrat e fundit), kërkimi i dytë kushton vetëm 000 operacion pasi nuk ka elementë në segmentin 6. Sfida e vërtetë është të gjesh një funksion të mirë hash që do të krijojë kova që përmbajnë një numër shumë të vogël elementësh.

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

varg (për shembull - mbiemri)
2 rreshta (për shembull - mbiemri dhe emri)
2 rreshta dhe data (për shembull - mbiemri, emri dhe data e lindjes)
...

Me një funksion të mirë hash, kërkimet e tabelave hash kushtojnë O(1).

Array vs tabelë hash

Pse të mos përdorni një grup?

Hmm, pyetje e mirë.

Tabela hash mund të jetë pjesërisht i ngarkuar në memorie, dhe segmentet e mbetura mund të mbeten në disk.
Me një grup ju duhet të përdorni hapësirë të vazhdueshme në memorie. Nëse jeni duke ngarkuar një tryezë të madhe është shumë e vështirë të gjesh hapësirë të mjaftueshme të vazhdueshme.
Për një tabelë hash, mund të zgjidhni çelësin që dëshironi (për shembull, vendin dhe mbiemrin e personit).

Për më shumë informacion, mund të lexoni artikullin rreth JavaHashMap, i cili është një zbatim efikas i një tabele hash; ju nuk keni nevojë të kuptoni Java për të kuptuar konceptet e mbuluara në këtë artikull.

Burimi: www.habr.com

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