Äau Habr! PiedÄvÄju jÅ«su uzmanÄ«bai raksta tulkojumu
.
RunÄjot par relÄciju datu bÄzÄm, es nevaru palÄ«dzÄt, bet domÄju, ka kaut kÄ trÅ«kst. Tos izmanto visur. Ir pieejamas daudzas dažÄdas datu bÄzes, sÄkot no mazÄs un noderÄ«gÄs SQLite lÄ«dz jaudÄ«gajai Teradata. Bet ir tikai daži raksti, kas izskaidro, kÄ darbojas datubÄze. Varat meklÄt sevi, izmantojot āhowdoesarelationaldatabaseworkā, lai redzÄtu, cik maz ir rezultÄtu. TurklÄt Å”ie raksti ir Ä«si. Ja meklÄjat jaunÄkÄs dinamiskÄs tehnoloÄ£ijas (BigData, NoSQL vai JavaScript), jÅ«s atradÄ«sit padziļinÄtus rakstus, kuros izskaidrots, kÄ tÄs darbojas.
Vai relÄciju datu bÄzes ir pÄrÄk vecas un pÄrÄk garlaicÄ«gas, lai tÄs izskaidrotu Ärpus universitÄtes kursiem, pÄtniecÄ«bas darbiem un grÄmatÄm?
KÄ izstrÄdÄtÄjam man nepatÄ«k izmantot kaut ko, ko nesaprotu. Un, ja datu bÄzes ir izmantotas vairÄk nekÄ 40 gadus, tam ir jÄbÅ«t iemeslam. Gadu gaitÄ esmu pavadÄ«jis simtiem stundu, lai patiesi izprastu Ŕīs dÄ«vainÄs melnÄs kastes, kuras lietoju katru dienu. RelÄciju datu bÄzes ļoti interesanti, jo viÅi pamatojoties uz noderÄ«gÄm un atkÄrtoti lietojamÄm koncepcijÄm. Ja vÄlaties izprast datubÄzi, taÄu jums nekad nav bijis laika vai vÄlmes iedziļinÄties Å”ajÄ plaÅ”ajÄ tÄmÄ, jums vajadzÄtu izbaudÄ«t Å”o rakstu.
Lai gan Ŕī raksta nosaukums ir skaidrs, Ŕī raksta mÄrÄ·is nav saprast, kÄ izmantot datubÄzi. TÄpÄc jums jau vajadzÄtu zinÄt, kÄ uzrakstÄ«t vienkÄrÅ”u savienojuma pieprasÄ«jumu un pamata vaicÄjumus NeapstrÄdÄts; pretÄjÄ gadÄ«jumÄ jÅ«s varat nesaprast Å”o rakstu. Tas ir vienÄ«gais, kas jums jÄzina, pÄrÄjo es paskaidroÅ”u.
SÄkÅ”u ar dažiem datorzinÄtÅu pamatiem, piemÄram, algoritmu laika sarežģītÄ«bu (BigO). Es zinu, ka daži no jums ienÄ«st Å”o jÄdzienu, taÄu bez tÄ jÅ«s nevarÄsit saprast datubÄzes sarežģījumus. TÄ kÄ Å”Ä« ir milzÄ«ga tÄma, Es koncentrÄÅ”os uz kas, manuprÄt, ir svarÄ«gi: kÄ datu bÄze apstrÄdÄ SQL uzziÅu. Es tikai iepazÄ«stinÄÅ”u datu bÄzes pamatjÄdzienilai raksta beigÄs jums bÅ«tu priekÅ”stats par to, kas notiek zem pÄrsega.
TÄ kÄ Å”is ir garÅ” un tehnisks raksts, kas ietver daudz algoritmu un datu struktÅ«ru, veltiet laiku, lai to izlasÄ«tu. Dažus jÄdzienus var bÅ«t grÅ«ti saprast; varat tos izlaist un joprojÄm gÅ«t vispÄrÄ«gu priekÅ”statu.
ZinoÅ”Äkiem jÅ«su vidÅ« Å”is raksts ir sadalÄ«ts 3 daļÄs:
- PÄrskats par zema un augsta lÄ«meÅa datu bÄzes komponentiem
- PÄrskats par vaicÄjumu optimizÄcijas procesu
- PÄrskats par darÄ«jumu un bufera pÅ«la pÄrvaldÄ«bu
Atgriezties uz pamatiem
Pirms gadiem (tÄlÄ, tÄlÄ galaktikÄ...) izstrÄdÄtÄjiem bija precÄ«zi jÄzina operÄciju skaits, ko viÅi kodÄja. ViÅi zinÄja savus algoritmus un datu struktÅ«ras no galvas, jo nevarÄja atļauties tÄrÄt savu lÄno datoru CPU un atmiÅu.
Å ajÄ daÄ¼Ä es jums atgÄdinÄÅ”u dažus no Å”iem jÄdzieniem, jo āātie ir bÅ«tiski datu bÄzes izpratnei. Es arÄ« iepazÄ«stinÄÅ”u ar koncepciju datu bÄzes indekss.
O(1) pret O(n2)
MÅ«sdienÄs daudziem izstrÄdÄtÄjiem nerÅ«p algoritmu laika sarežģītÄ«ba... un viÅiem ir taisnÄ«ba!
Bet, ja jums ir darÄ«Å”ana ar daudz datu (es nerunÄju par tÅ«kstoÅ”iem) vai ja jums ir grÅ«tÄ«bas milisekundÄs, ir ļoti svarÄ«gi saprast Å”o jÄdzienu. Un, kÄ jÅ«s varat iedomÄties, datu bÄzÄm ir jÄrisina abas situÄcijas! Es nelikÅ”u jums tÄrÄt vairÄk laika, nekÄ nepiecieÅ”ams, lai saprastu bÅ«tÄ«bu. Tas mums palÄ«dzÄs izprast uz izmaksÄm balstÄ«tas optimizÄcijas jÄdzienu vÄlÄk (izmaksÄt pamatojoties optimizÄcija).
JÄdziens
Algoritma laika sarežģītÄ«ba izmanto, lai redzÄtu, cik ilgs laiks prasÄ«s algoritma pabeigÅ”anai noteiktam datu apjomam. Lai aprakstÄ«tu Å”o sarežģītÄ«bu, mÄs izmantojam lielo O matemÄtisko apzÄ«mÄjumu. Å o apzÄ«mÄjumu izmanto kopÄ ar funkciju, kas apraksta, cik operÄciju algoritmam nepiecieÅ”ams noteiktam ievades datu skaitam.
PiemÄram, kad es saku "Å”im algoritmam ir sarežģītÄ«ba O(some_function())", tas nozÄ«mÄ, ka algoritmam ir nepiecieÅ”amas dažas_funkcijas(a_noteikts_datu_apjoms) darbÄ«bas, lai apstrÄdÄtu noteiktu datu apjomu.
Å ajÄ gadÄ«jumÄ, SvarÄ«gs nav datu apjoms**, citÄdi ** kÄ palielinÄs operÄciju skaits, palielinoties datu apjomam. Laika sarežģītÄ«ba nenodroÅ”ina precÄ«zu darbÄ«bu skaitu, bet ir labs veids, kÄ novÄrtÄt izpildes laiku.
Å ajÄ grafikÄ var redzÄt operÄciju skaitu pret ievades datu apjomu dažÄda veida algoritmu laika sarežģītÄ«bÄm. Es izmantoju logaritmisko skalu, lai tos parÄdÄ«tu. Citiem vÄrdiem sakot, datu apjoms strauji palielinÄs no 1 lÄ«dz 1 miljardam. MÄs redzam, ka:
- O(1) jeb konstanta sarežģītÄ«ba paliek nemainÄ«ga (citÄdi to nesauktu par konstantu sarežģītÄ«bu).
- O(log(n)) joprojÄm ir zems pat ar miljardiem datu.
- SliktÄkÄs grÅ«tÄ«bas - O(n2), kur operÄciju skaits strauji pieaug.
- PÄrÄjÄs divas komplikÄcijas palielinÄs tikpat Ätri.
piemÄri
Ar nelielu datu apjomu atŔķirÄ«ba starp O(1) un O(n2) ir niecÄ«ga. PiemÄram, pieÅemsim, ka jums ir algoritms, kuram jÄapstrÄdÄ 2000 elementi.
- O(1) algoritms jums izmaksÄs 1 operÄciju
- O(log(n)) algoritms jums izmaksÄs 7 operÄcijas
- O(n) algoritms jums izmaksÄs 2 operÄciju
- Algoritms O(n*log(n)) tev izmaksÄs 14 000 operÄciju
- O(n2) algoritms jums izmaksÄs 4 000 000 operÄciju
Å Ä·iet, ka atŔķirÄ«ba starp O(1) un O(n2) ir liela (4 miljoni darbÄ«bu), taÄu jÅ«s zaudÄsiet ne vairÄk kÄ 2 ms, tikai laiks pamirkŔķinÄt acis. PatieÅ”Äm, mÅ«sdienu procesori var apstrÄdÄt . TÄpÄc daudzos IT projektos veiktspÄja un optimizÄcija nav problÄma.
KÄ jau teicu, joprojÄm ir svarÄ«gi zinÄt Å”o jÄdzienu, strÄdÄjot ar milzÄ«gu datu apjomu. Ja Å”oreiz algoritmam ir jÄapstrÄdÄ 1 000 000 elementu (kas datu bÄzei nav tik daudz):
- O(1) algoritms jums izmaksÄs 1 operÄciju
- O(log(n)) algoritms jums izmaksÄs 14 operÄcijas
- O(n) algoritms jums izmaksÄs 1 000 000 operÄciju
- O(n*log(n)) algoritms jums izmaksÄs 14 000 000 operÄciju
- O(n2) algoritms jums izmaksÄs 1 000 000 000 000 operÄciju
Es neesmu izdarÄ«jis matemÄtiku, bet es teiktu, ka ar O(n2) algoritmu jums ir laiks izdzert kafiju (pat divas!). Ja datu apjomam pievienosiet vÄl 0, jums bÅ«s laiks pasnaust.
Iesim dziļÄk
Par savu informÄciju:
- Laba hash tabulas uzmeklÄÅ”ana atrod elementu O(1).
- MeklÄjot labi lÄ«dzsvarotu koku, tiek iegÅ«ti rezultÄti O(log(n)).
- MeklÄjot masÄ«vÄ, rezultÄti tiek iegÅ«ti O(n).
- LabÄkajiem ŔķiroÅ”anas algoritmiem ir sarežģītÄ«ba O(n*log(n)).
- Sliktam kÄrtoÅ”anas algoritmam ir sarežģītÄ«ba O(n2).
PiezÄ«me. TurpmÄkajÄs daļÄs mÄs redzÄsim Å”os algoritmus un datu struktÅ«ras.
Ir vairÄki algoritmu laika sarežģītÄ«bas veidi:
- vidÄjais gadÄ«juma scenÄrijs
- labÄkais scenÄrijs
- un sliktÄkajÄ gadÄ«jumÄ
Laika sarežģītÄ«ba bieži vien ir sliktÄkais scenÄrijs.
Es runÄju tikai par algoritma laika sarežģītÄ«bu, bet sarežģītÄ«ba attiecas arÄ« uz:
- algoritma atmiÅas patÄriÅÅ”
- diska I/O patÄriÅa algoritms
Protams, ir komplikÄcijas, kas ir sliktÄkas par n2, piemÄram:
- n4: tas ir briesmÄ«gi! Dažiem no minÄtajiem algoritmiem ir Å”Äda sarežģītÄ«ba.
- 3n: tas ir vÄl sliktÄk! Vienam no algoritmiem, ko redzÄsim Ŕī raksta vidÅ«, ir Å”Äda sarežģītÄ«ba (un to faktiski izmanto daudzÄs datu bÄzÄs).
- faktoriÄls n: jÅ«s nekad nesaÅemsit rezultÄtus pat ar nelielu datu apjomu.
- nn: Ja jÅ«s saskaraties ar Å”o sarežģītÄ«bu, jums vajadzÄtu pajautÄt sev, vai tas tieÅ”Äm ir jÅ«su darbÄ«bas lauks...
PiezÄ«me: es jums nesniedzu lielÄ O apzÄ«mÄjuma faktisko definÄ«ciju, tikai ideju. Å o rakstu varat izlasÄ«t vietnÄ reÄlajai (asimptotiskajai) definÄ«cijai.
MergeSort
Ko jÅ«s darÄt, ja jums ir jÄkÄrto kolekcija? Kas? JÅ«s izsaucat funkciju sort()... Labi, laba atbilde... Bet datu bÄzei ir jÄsaprot, kÄ Å”Ä« sort() funkcija darbojas.
Ir vairÄki labi ŔķiroÅ”anas algoritmi, tÄpÄc es koncentrÄÅ”os uz vissvarÄ«gÄko: sapludinÄt kÄrtot. JÅ«s, iespÄjams, nesaprotat, kÄpÄc datu kÄrtoÅ”ana Å”obrÄ«d ir noderÄ«ga, bet pÄc vaicÄjuma optimizÄcijas daļas tas ir jÄdara. TurklÄt sapludinÄÅ”anas kÄrtoÅ”anas izpratne palÄ«dzÄs mums vÄlÄk izprast kopÄ«go datubÄzes pievienoÅ”anÄs darbÄ«bu apvienot pievienoties (apvienoÅ”anÄs asociÄcija).
Apvienot
TÄpat kÄ daudzi noderÄ«gi algoritmi, sapludinÄÅ”anas kÄrtoÅ”ana balstÄs uz triku: 2 sakÄrtotu N/2 lieluma masÄ«vu apvienoÅ”ana N elementu sakÄrtotÄ masÄ«vÄ maksÄ tikai N operÄcijas. Å o darbÄ«bu sauc par apvienoÅ”anu.
ApskatÄ«sim, ko tas nozÄ«mÄ, izmantojot vienkÄrÅ”u piemÄru:
Å is attÄls parÄda, ka, lai izveidotu galÄ«go sakÄrtoto 8 elementu masÄ«vu, jums tikai vienu reizi ir jÄatkÄrto 2 4 elementu masÄ«vi. TÄ kÄ abi 4 elementu masÄ«vi jau ir sakÄrtoti:
- 1) jÅ«s salÄ«dzinÄt abus paÅ”reizÄjos elementus divos masÄ«vos (sÄkumÄ strÄva = pirmais)
- 2) pÄc tam paÅemiet mazÄko, lai ievietotu to 8 elementu masÄ«vÄ
- 3) un pÄrejiet uz nÄkamo elementu masÄ«vÄ, kurÄ paÅÄmÄt mazÄko elementu
- un atkÄrtojiet 1,2,3, lÄ«dz sasniedzat viena masÄ«va pÄdÄjo elementu.
- PÄc tam Åemat pÄrÄjos cita masÄ«va elementus, lai ievietotu tos 8 elementu masÄ«vÄ.
Tas darbojas, jo abi 4 elementu masÄ«vi ir sakÄrtoti un tÄpÄc jums nav "jÄatgriežas" Å”ajos masÄ«vos.
Tagad, kad mÄs saprotam triku, Å”eit ir mans sapludinÄÅ”anas pseidokods:
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;SapludinÄÅ”anas kÄrtoÅ”ana sadala problÄmu mazÄkÄs problÄmÄs un pÄc tam atrod mazÄko problÄmu rezultÄtus, lai iegÅ«tu sÄkotnÄjÄs problÄmas rezultÄtu (piezÄ«me: Å”Äda veida algoritmu sauc par sadali un iekaro). Ja jÅ«s nesaprotat Å”o algoritmu, neuztraucieties; Es to nesapratu, kad pirmo reizi to redzÄju. Ja tas var jums palÄ«dzÄt, es redzu Å”o algoritmu kÄ divfÄžu algoritmu:
- SadalÄ«Å”anas fÄze, kur masÄ«vs tiek sadalÄ«ts mazÄkos masÄ«vos
- Å Ä·iroÅ”anas fÄzÄ mazie masÄ«vi tiek apvienoti (izmantojot savienÄ«bu), lai izveidotu lielÄku masÄ«vu.
SadalÄ«Å”anas fÄze
SadalÄ«Å”anas stadijÄ masÄ«vs tiek sadalÄ«ts vienotos masÄ«vos 3 soļos. FormÄlais soļu skaits ir log(N) (jo N=8, log(N) = 3).
KÄ es to varu zinÄt?
Es esmu Ä£Änijs! VÄrdu sakot - matemÄtika. Ideja ir tÄda, ka katrs solis dala sÄkotnÄjÄ masÄ«va lielumu ar 2. Soļu skaits ir skaits, cik reižu varat sadalÄ«t sÄkotnÄjo masÄ«vu divÄs daļÄs. Å Ä« ir precÄ«za logaritma definÄ«cija (2. bÄze).
Å Ä·iroÅ”anas fÄze
Å Ä·iroÅ”anas fÄzÄ jÅ«s sÄkat ar vienotiem (viena elementa) masÄ«viem. KatrÄ darbÄ«bÄ tiek lietotas vairÄkas sapludinÄÅ”anas darbÄ«bas, un kopÄjÄs izmaksas ir N = 8 darbÄ«bas:
- PirmajÄ posmÄ jums ir 4 sapludinÄÅ”anas, kas katra maksÄ 2 darbÄ«bas
- OtrajÄ darbÄ«bÄ jums ir 2 sapludinÄÅ”anas, kas katra maksÄ 4 darbÄ«bas
- TreÅ”ajÄ darbÄ«bÄ jums ir 1 sapludinÄÅ”ana, kas maksÄ 8 darbÄ«bas
TÄ kÄ ir log(N) soļi, kopÄjÄs izmaksas N * log(N) operÄcijas.
ApvienoÅ”anas kÄrtoÅ”anas priekÅ”rocÄ«bas
KÄpÄc Å”is algoritms ir tik spÄcÄ«gs?
Jo:
- Varat to mainÄ«t, lai samazinÄtu atmiÅas apjomu, lai jÅ«s neizveidotu jaunus masÄ«vus, bet gan tieÅ”i pÄrveidotu ievades masÄ«vu.
PiezÄ«me: Å”Äda veida algoritmu sauc (ŔķiroÅ”ana bez papildu atmiÅas).
- Varat to mainÄ«t, lai vienlaikus izmantotu diska vietu un nelielu daudzumu atmiÅas, neradot ievÄrojamas diska ievades/izvades izmaksas. Ideja ir ielÄdÄt atmiÅÄ tikai tÄs daļas, kuras paÅ”laik tiek apstrÄdÄtas. Tas ir svarÄ«gi, ja nepiecieÅ”ams kÄrtot vairÄku gigabaitu tabulu tikai ar 100 megabaitu atmiÅas buferi.
PiezÄ«me: Å”Äda veida algoritmu sauc .
- Varat to mainÄ«t, lai tas darbotos vairÄkos procesos/pavedienos/serveros.
PiemÄram, izplatÄ«tÄ sapludinÄÅ”anas kÄrtoÅ”ana ir viena no galvenajÄm sastÄvdaļÄm (kas ir lielo datu struktÅ«ra).
- Å is algoritms var pÄrvÄrst svinu zeltÄ (tieÅ”Äm!).
Å is ŔķiroÅ”anas algoritms tiek izmantots lielÄkajÄ daÄ¼Ä (ja ne visÄs) datu bÄzÄs, taÄu tas nav vienÄ«gais. Ja vÄlaties uzzinÄt vairÄk, varat izlasÄ«t Å”o , kurÄ aplÅ«koti izplatÄ«to datu bÄzu ŔķiroÅ”anas algoritmu plusi un mÄ«nusi.
Masīvu, koku un hash tabula
Tagad, kad mÄs saprotam laika sarežģītÄ«bas un ŔķiroÅ”anas ideju, man vajadzÄtu pastÄstÄ«t par 3 datu struktÅ«rÄm. Tas ir svarÄ«gi, jo viÅi ir mÅ«sdienu datu bÄzu pamatÄ. Es arÄ« iepazÄ«stinÄÅ”u ar koncepciju datu bÄzes indekss.
Masīvs
Divdimensiju masÄ«vs ir vienkÄrÅ”ÄkÄ datu struktÅ«ra. Tabulu var uzskatÄ«t par masÄ«vu. PiemÄram:
Å is 2 dimensiju masÄ«vs ir tabula ar rindÄm un kolonnÄm:
- Katra rinda apzÄ«mÄ entÄ«tiju
- SlejÄs tiek saglabÄti rekvizÄ«ti, kas apraksta entÄ«tiju.
- KatrÄ kolonnÄ tiek glabÄti noteikta veida dati (vesels skaitlis, virkne, datums...).
Tas ir Ärti datu glabÄÅ”anai un vizualizÄÅ”anai, taÄu, ja nepiecieÅ”ams atrast konkrÄtu vÄrtÄ«bu, tas nav piemÄrots.
PiemÄram, ja vÄlaties atrast visus vÄ«rieÅ”us, kuri strÄdÄ ApvienotajÄ KaralistÄ, jums ir jÄaplÅ«ko katra rinda, lai noteiktu, vai Ŕī rinda pieder Apvienotajai Karalistei. Tas jums izmaksÄs N darÄ«jumusKur N - rindu skaits, kas nav slikti, bet vai var bÅ«t ÄtrÄks veids? Tagad mums ir pienÄcis laiks iepazÄ«ties ar kokiem.
PiezÄ«me. LielÄkÄ daļa mÅ«sdienu datu bÄzu nodroÅ”ina paplaÅ”inÄtus masÄ«vus tabulu efektÄ«vai glabÄÅ”anai: kaudzes sakÄrtotas tabulas un indeksu sakÄrtotas tabulas. Bet tas nemaina problÄmu Ätri atrast konkrÄtu nosacÄ«jumu kolonnu grupÄ.
Datu bÄzes koks un indekss
BinÄrais meklÄÅ”anas koks ir binÄrs koks ar Ä«paÅ”u Ä«paŔību, atslÄgai katrÄ mezglÄ jÄbÅ«t:
- lielÄks nekÄ visas atslÄgas, kas saglabÄtas kreisajÄ apakÅ”kokÄ
- mazÄk nekÄ visas atslÄgas, kas saglabÄtas labajÄ apakÅ”kokÄ
ApskatÄ«sim, ko tas nozÄ«mÄ vizuÄli
Ideja
Å im kokam ir N = 15 elementi. PieÅemsim, ka es meklÄju 208:
- Es sÄku no saknes, kuras atslÄga ir 136. TÄ kÄ 136<208, es skatos uz 136. mezgla labo apakÅ”koku.
- 398>208 tÄpÄc es skatos uz 398. mezgla kreiso apakÅ”koku
- 250>208 tÄpÄc es skatos uz 250. mezgla kreiso apakÅ”koku
- 200<208, tÄpÄc es skatos uz mezgla 200 labo apakÅ”koku. Bet 200 nav labÄ apakÅ”koka, vÄrtÄ«ba neeksistÄ (jo, ja tas pastÄv, tas bÅ«s labajÄ apakÅ”kokÄ 200).
Tagad pieÅemsim, ka es meklÄju 40
- Es sÄku no saknes, kuras atslÄga ir 136. TÄ kÄ 136 > 40, es skatos uz 136. mezgla kreiso apakÅ”koku.
- 80 > 40, tÄpÄc es skatos uz 80. mezgla kreiso apakÅ”koku
- 40 = 40, mezgls pastÄv. Node iekÅ”pusÄ izgÅ«stu rindas ID (nav redzams attÄlÄ) un tabulÄ meklÄju doto rindas ID.
- Zinot rindas ID, es varu precÄ«zi zinÄt, kur tabulÄ atrodas dati, lai es varÄtu tos izgÅ«t uzreiz.
Galu galÄ abi meklÄjumi man izmaksÄs koka iekÅ”ienÄ esoÅ”o lÄ«meÅu skaitu. Ja uzmanÄ«gi izlasiet sadaļu par sapludinÄÅ”anas kÄrtoÅ”anu, jums vajadzÄtu redzÄt, ka ir žurnÄla (N) lÄ«meÅi. IzrÄdÄs, meklÄÅ”anas izmaksu žurnÄls (N), nav slikti!
AtgriezÄ«simies pie mÅ«su problÄmas
Bet tas ir ļoti abstrakti, tÄpÄc atgriezÄ«simies pie mÅ«su problÄmas. VienkÄrÅ”a vesela skaitļa vietÄ iedomÄjieties virkni, kas attÄlo kÄda cilvÄka valsti iepriekÅ”ÄjÄ tabulÄ. PieÅemsim, ka jums ir koks, kurÄ ir tabulas lauks āvalstsā (3. sleja):
- Ja vÄlaties uzzinÄt, kas strÄdÄ ApvienotajÄ KaralistÄ
- paskatÄs uz koku, lai iegÅ«tu mezglu, kas apzÄ«mÄ LielbritÄniju
- "UKnode" iekÅ”pusÄ jÅ«s atradÄ«siet ApvienotÄs Karalistes darbinieku ierakstu atraÅ”anÄs vietu.
Å Ä« meklÄÅ”ana maksÄs log(N) operÄcijas, nevis N operÄcijas, ja izmantosit masÄ«vu tieÅ”i. Tas, ko jÅ«s tikko prezentÄjÄt, bija datu bÄzes indekss.
Varat izveidot indeksa koku jebkurai lauku grupai (virkne, numurs, 2 rindiÅas, numurs un virkne, datums...), ja vien jums ir funkcija, lai salÄ«dzinÄtu atslÄgas (ti, lauku grupas), lai jÅ«s varÄtu iestatÄ«t secÄ«ba starp atslÄgÄm (kas attiecas uz visiem pamata tipiem datubÄzÄ).
B+TreeIndex
Lai gan Å”is koks darbojas labi, lai iegÅ«tu noteiktu vÄrtÄ«bu, nepiecieÅ”amÄ«bas gadÄ«jumÄ pastÄv LIELA problÄma iegÅ«t vairÄkus elementus starp divÄm vÄrtÄ«bÄm. Tas maksÄs O(N), jo jums bÅ«s jÄaplÅ«ko katrs koka mezgls un jÄpÄrbauda, āāvai tas atrodas starp Ŕīm divÄm vÄrtÄ«bÄm (piemÄram, ar sakÄrtotu koka ŔķÄrsoÅ”anu). TurklÄt Ŕī darbÄ«ba nav draudzÄ«ga diskam I/O, jo jums ir jÄlasa viss koks. Mums ir jÄatrod veids, kÄ efektÄ«vi izpildÄ«t diapazona pieprasÄ«jums. Lai atrisinÄtu Å”o problÄmu, mÅ«sdienu datubÄzÄs tiek izmantota iepriekÅ”ÄjÄ koka modificÄta versija ar nosaukumu B+Tree. B+koka kokÄ:
- tikai zemÄkie mezgli (lapas) uzglabÄt informÄciju (rindu atraÅ”anÄs vieta saistÄ«tajÄ tabulÄ)
- pÄrÄjie mezgli ir Å”eit marÅ”rutÄÅ”anai uz pareizo mezglu meklÄÅ”anas laikÄ.
KÄ redzat, Å”eit ir vairÄk mezglu (divas reizes). PatieÅ”Äm, jums ir papildu mezgli, "lÄmuma mezgli", kas palÄ«dzÄs atrast pareizo mezglu (kas saglabÄ saistÄ«tÄs tabulas rindu atraÅ”anÄs vietu). Bet meklÄÅ”anas sarežģītÄ«ba joprojÄm ir O(log(N)) (ir tikai vÄl viens lÄ«menis). LielÄ atŔķirÄ«ba ir tÄ mezgli zemÄkajÄ lÄ«menÄ« ir saistÄ«ti ar to pÄcteÄiem.
Izmantojot Å”o B+Tree, ja meklÄjat vÄrtÄ«bas no 40 lÄ«dz 100:
- Jums vienkÄrÅ”i jÄmeklÄ 40 (vai tuvÄkÄ vÄrtÄ«ba pÄc 40, ja 40 neeksistÄ), kÄ to darÄ«jÄt ar iepriekÅ”Äjo koku.
- PÄc tam savÄc 40 mantiniekus, izmantojot tieÅ”Äs mantinieku saites, lÄ«dz sasniegsiet 100.
PieÅemsim, ka atrodat M pÄcteÄus un kokam ir N mezgli. KonkrÄta mezgla atraÅ”ana maksÄ Å¾urnÄlu(N), tÄpat kÄ iepriekÅ”Äjais koks. Bet, tiklÄ«dz jÅ«s iegÅ«sit Å”o mezglu, jÅ«s iegÅ«sit M operÄciju pÄcteci ar atsaucÄm uz viÅu pÄcteÄiem. Å Ä« meklÄÅ”ana maksÄ tikai M+log(N) operÄcijas, salÄ«dzinot ar N operÄcijÄm iepriekÅ”ÄjÄ kokÄ. TurklÄt jums nav jÄlasa viss koks (tikai M+log(N) mezgli), kas nozÄ«mÄ mazÄku diska lietojumu. Ja M ir mazs (piem., 200 rindas) un N ir liels (1 000 000 rindu), bÅ«s LIELA atŔķirÄ«ba.
Bet Å”eit ir jaunas problÄmas (atkal!). Ja pievienojat vai dzÄÅ”at rindu datu bÄzÄ (un lÄ«dz ar to saistÄ«tajÄ B+Tree indeksÄ):
- jums ir jÄuztur kÄrtÄ«ba starp mezgliem B+Tree iekÅ”pusÄ, pretÄjÄ gadÄ«jumÄ jÅ«s nevarÄsit atrast mezglus neŔķirota koka iekÅ”pusÄ.
- jums ir jÄsaglabÄ minimÄlais iespÄjamais lÄ«meÅu skaits B+Tree, pretÄjÄ gadÄ«jumÄ O(log(N)) laika sarežģītÄ«ba kļūst par O(N).
Citiem vÄrdiem sakot, B+Tree ir jÄbÅ«t paÅ”sakÄrtotam un lÄ«dzsvarotam. Par laimi, tas ir iespÄjams, izmantojot viedÄs dzÄÅ”anas un ievietoÅ”anas darbÄ«bas. Bet par to ir jÄmaksÄ: ievietoÅ”ana un dzÄÅ”ana B+ kokÄ maksÄ O(log(N)). TÄpÄc daži no jums to ir dzirdÄjuÅ”i PÄrÄk daudzu indeksu izmantoÅ”ana nav laba ideja. TieÅ”Äm, jÅ«s palÄninÄt Ätru rindas ievietoÅ”anu/atjauninÄÅ”anu/dzÄÅ”anu tabulÄjo datu bÄzei ir jÄatjaunina tabulas indeksi, izmantojot dÄrgu O(log(N)) operÄciju katram indeksam. TurklÄt indeksu pievienoÅ”ana nozÄ«mÄ lielÄku darba slodzi darÄ«jumu vadÄ«tÄjs (tiks aprakstÄ«ts raksta beigÄs).
Lai iegÅ«tu sÄ«kÄku informÄciju, varat skatÄ«t Wikipedia rakstu par . Ja vÄlaties piemÄru B+Tree ievieÅ”anai datu bÄzÄ, ieskatieties Šø no vadoÅ”Ä MySQL izstrÄdÄtÄja. ViÅi abi koncentrÄjas uz to, kÄ InnoDB (MySQL dzinÄjs) apstrÄdÄ indeksus.
PiezÄ«me. KÄds lasÄ«tÄjs man teica, ka zema lÄ«meÅa optimizÄcijas dÄļ kokam B+ jÄbÅ«t pilnÄ«bÄ lÄ«dzsvarotam.
Hashtable
MÅ«su pÄdÄjÄ svarÄ«gÄ datu struktÅ«ra ir hash tabula. Tas ir ļoti noderÄ«gi, ja vÄlaties Ätri meklÄt vÄrtÄ«bas. TurklÄt, izprotot jaukÅ”anas tabulu, mÄs vÄlÄk varÄsim izprast parasto datu bÄzes pievienoÅ”anas darbÄ«bu, ko sauc par jaukÅ”anas pievienoÅ”anu ( hash pievienoties). Å o datu struktÅ«ru datu bÄze izmanto arÄ« dažu iekÅ”Äjo lietu glabÄÅ”anai (piem. slÄdzams galds vai bufera baseins, mÄs abus Å”os jÄdzienus redzÄsim vÄlÄk).
Hash tabula ir datu struktÅ«ra, kas Ätri atrod elementu pÄc atslÄgas. Lai izveidotu hash tabulu, jums jÄdefinÄ:
- pavediens jūsu elementiem
- jaucÄjfunkcija par atslÄgÄm. AprÄÄ·inÄtÄs atslÄgas jaucÄjzÄ«mes norÄda elementu atraÅ”anÄs vietu (ko sauc segmentiem ).
- funkciju taustiÅu salÄ«dzinÄÅ”anai. Kad esat atradis pareizo segmentu, jums ir jÄatrod elements, kuru meklÄjat segmentÄ, izmantojot Å”o salÄ«dzinÄjumu.
VienkÄrÅ”s piemÄrs
Å emsim skaidru piemÄru:
Å ajÄ hash tabulÄ ir 10 segmenti. TÄ kÄ es esmu slinks, es nobildÄju tikai 5 segmentus, bet es zinu, ka tu esi gudrs, tÄpÄc ļauÅ”u tev paÅ”am iztÄloties pÄrÄjos 5. Es izmantoju atslÄgas jaucÄjfunkciju modulo 10. Citiem vÄrdiem sakot, es saglabÄju tikai elementa atslÄgas pÄdÄjo ciparu, lai atrastu tÄ segmentu:
- ja pÄdÄjais cipars ir 0, elements ietilpst segmentÄ 0,
- ja pÄdÄjais cipars ir 1, elements ietilpst segmentÄ 1,
- ja pÄdÄjais cipars ir 2, elements ietilpst apgabalÄ 2,
- ...
SalÄ«dzinÄÅ”anas funkcija, ko izmantoju, ir vienkÄrÅ”i vienÄdÄ«ba starp diviem veseliem skaitļiem.
PieÅemsim, ka vÄlaties iegÅ«t 78. elementu:
- Hash tabula aprÄÄ·ina jaucÄjkodu 78, kas ir 8.
- Jauktabula aplūko 8. segmentu, un pirmais atrastais elements ir 78.
- ViÅa atdod jums 78. preci
- MeklÄÅ”ana maksÄ tikai 2 operÄcijas (viens, lai aprÄÄ·inÄtu jaucÄjvÄrtÄ«bu, un otrs, lai meklÄtu elementu segmentÄ).
Tagad pieÅemsim, ka vÄlaties iegÅ«t 59. elementu:
- Hash tabula aprÄÄ·ina jaucÄjkodu 59, kas ir 9.
- Hash tabula meklÄ segmentÄ 9, pirmais atrastais elements ir 99. TÄ kÄ 99!=59, elements 99 nav derÄ«gs elements.
- Izmantojot to paÅ”u loÄ£iku, tiek Åemts otrais elements (9), treÅ”ais (79), ..., pÄdÄjais (29).
- Elements nav atrasts.
- MeklÄÅ”ana izmaksÄja 7 operÄcijas.
Laba hash funkcija
KÄ redzat, atkarÄ«bÄ no meklÄtÄs vÄrtÄ«bas izmaksas nav vienÄdas!
Ja tagad mainÄ«Å”u atslÄgas jaucÄjfunkciju modulo 1 000 000 (tas ir, Åemot pÄdÄjos 6 ciparus), otrÄ uzmeklÄÅ”ana maksÄ tikai 1 operÄciju, jo segmentÄ 000059 nav elementu. Patiesais izaicinÄjums ir atrast labu jaucÄjfunkciju, kas izveidos kausus, kas satur ļoti mazu elementu skaitu.
ManÄ piemÄrÄ ir viegli atrast labu jaucÄjfunkciju. Bet Å”is ir vienkÄrÅ”s piemÄrs, labu jaucÄjfunkciju atrast ir grÅ«tÄk, ja atslÄga ir:
- virkne (piemÄram, uzvÄrds)
- 2 rindas (piemÄram, uzvÄrds un vÄrds)
- 2 rindas un datums (piemÄram, uzvÄrds, vÄrds un dzimÅ”anas datums)
- ...
Izmantojot labu jaucÄjfunkciju, jaucÄj tabulas meklÄÅ”ana maksÄ O (1).
Tabula Masīvs vs hash
KÄpÄc neizmantot masÄ«vu?
Hmm, labs jautÄjums.
- Hash tabula var bÅ«t daļÄji ielÄdÄts atmiÅÄ, un atlikuÅ”ie segmenti var palikt diskÄ.
- Izmantojot masÄ«vu, atmiÅÄ ir jÄizmanto blakus esoÅ”Ä vieta. Ja ielÄdÄjat lielu galdu ir ļoti grÅ«ti atrast pietiekami daudz nepÄrtrauktas vietas.
- JaukÅ”anas tabulai varat atlasÄ«t vajadzÄ«go atslÄgu (piemÄram, valsti un personas uzvÄrdu).
Lai iegÅ«tu papildinformÄciju, varat izlasÄ«t rakstu par , kas ir efektÄ«va hash tabulas ievieÅ”ana; jums nav jÄsaprot Java, lai saprastu Å”ajÄ rakstÄ aplÅ«kotos jÄdzienus.
Avots: www.habr.com