Hej Habr! Predstavljam Vašoj pažnji prevod članka
"Kako radi relaciona baza podataka".

Kada su u pitanju relacijske baze podataka, ne mogu a da ne mislim da nešto nedostaje. Koriste se svuda. Dostupne su mnoge različite baze podataka, od malog i korisnog SQLite-a do moćnog Teradata. Ali postoji samo nekoliko članaka koji objašnjavaju kako baza podataka radi. Možete sami tražiti koristeći "howdoesarelationaldatabasework" da vidite koliko je malo rezultata. Štaviše, ovi članci su kratki. Ako tražite najnovije tehnologije (BigData, NoSQL ili JavaScript), naći ćete detaljnije članke koji objašnjavaju kako one rade.

Jesu li relacijske baze podataka prestare i previše dosadne da bi se objašnjavale izvan univerzitetskih kurseva, istraživačkih radova i knjiga?

Kao programer, mrzim da koristim nešto što ne razumijem. A ako se baze podataka koriste više od 40 godina, mora postojati razlog. Tokom godina, proveo sam stotine sati da zaista razumem ove čudne crne kutije koje koristim svaki dan. Relacijske baze podataka veoma interesantno jer oni zasnovano na korisnim konceptima koji se mogu ponovo koristiti. Ako ste zainteresirani za razumijevanje baze podataka, ali nikada niste imali vremena ili sklonosti da se udubite u ovu široku temu, trebali biste uživati ​​u ovom članku.

Iako je naslov ovog članka eksplicitan, Svrha ovog članka nije razumjeti kako koristiti bazu podataka... Dakle, već biste trebali znati kako napisati jednostavan zahtjev za povezivanje i osnovne upite RAW; inače možda nećete razumjeti ovaj članak. To je jedino što trebate znati, ostalo ću vam objasniti.

Počeću sa nekim osnovama računarske nauke, kao što je vremenska složenost algoritama (BigO). Znam da neki od vas mrze ovaj koncept, ali bez njega nećete moći razumjeti zamršenosti unutar baze podataka. Pošto je ovo ogromna tema, Fokusiraću se na šta ja mislim da je važno: kako baza podataka obrađuje SQL upit. Samo ću se predstaviti osnovni koncepti baze podatakatako da na kraju članka imate ideju o tome šta se dešava ispod haube.

Budući da je ovo dugačak i tehnički članak koji uključuje mnogo algoritama i struktura podataka, uzmite si vremena da ga pročitate. Neki koncepti mogu biti teški za razumevanje; možete ih preskočiti i ipak dobiti opću ideju.

Za bolje upućene među vama, ovaj članak je podijeljen u 3 dijela:

• Pregled komponenti baze podataka niskog i visokog nivoa
• Pregled procesa optimizacije upita
• Pregled upravljanja transakcijama i baferima

Nazad na osnove

Prije mnogo godina (u dalekoj, dalekoj galaksiji...), programeri su morali tačno znati broj operacija koje su kodirali. Znali su svoje algoritme i strukture podataka napamet jer nisu mogli priuštiti da troše CPU i memoriju svojih sporih računara.

U ovom dijelu ću vas podsjetiti na neke od ovih koncepata jer su oni bitni za razumijevanje baze podataka. Također ću predstaviti koncept indeks baze podataka.

O(1) vs O(n2)

Danas mnogi programeri ne mare za vremensku složenost algoritama... i u pravu su!

Ali kada imate posla sa puno podataka (ne govorim o hiljadama) ili ako se mučite sa milisekundama, postaje ključno razumjeti ovaj koncept. I kao što možete zamisliti, baze podataka se moraju nositi s obje situacije! Neću te tjerati da trošiš više vremena nego što je potrebno da dočaraš poentu. Ovo će nam pomoći da kasnije shvatimo koncept optimizacije zasnovane na troškovima (trošak zasnovan optimizacija).

Koncept

Vremenska složenost algoritma koristi se da vidi koliko dugo će algoritmu trebati da završi za datu količinu podataka. Da bismo opisali ovu složenost, koristimo matematičku notaciju velikog O. Ova notacija se koristi sa funkcijom koja opisuje koliko je operacija potrebno algoritmu za dati broj ulaza.

Na primjer, kada kažem "ovaj algoritam ima složenost O(some_function())", to znači da algoritam zahtijeva neke_function(a_certain_amount_of_data) operacije za obradu određene količine podataka.

tako Nije bitna količina podataka**, inače ** kako se broj operacija povećava sa povećanjem količine podataka. Vremenska složenost ne daje tačan broj operacija, ali je dobar način za procjenu vremena izvršenja.

Na ovom grafikonu možete vidjeti broj operacija u odnosu na količinu ulaznih podataka za različite tipove vremenske složenosti algoritama. Koristio sam logaritamsku skalu da ih prikažem. Drugim riječima, količina podataka se brzo povećava sa 1 na 1 milijardu. Vidimo da:

• O(1) ili konstantna složenost ostaje konstantna (inače se ne bi zvala konstantna složenost).
• O(log(n)) ostaje nizak čak i sa milijardama podataka.
• Najgora poteškoća - O(n2), gdje broj operacija brzo raste.
• Druge dvije komplikacije rastu jednako brzo.

primjeri

Uz malu količinu podataka, razlika između O(1) i O(n2) je zanemarljiva. Na primjer, recimo da imate algoritam koji treba obraditi 2000 elemenata.

• O(1) algoritam će vas koštati 1 operaciju
• O(log(n)) algoritam će vas koštati 7 operacija
• O(n) algoritam će vas koštati 2 operacija
• O(n*log(n)) algoritam će vas koštati 14 operacija
• O(n2) algoritam će vas koštati 4 operacija

Čini se da je razlika između O(1) i O(n2) velika (4 miliona operacija), ali ćete izgubiti maksimalno 2 ms, samo vrijeme da trepnete očima. Zaista, savremeni procesori mogu da obrađuju stotine miliona operacija u sekundi. Zbog toga performanse i optimizacija nisu problem u mnogim IT projektima.

Kao što sam rekao, i dalje je važno poznavati ovaj koncept kada radite sa ogromnim količinama podataka. Ako ovaj put algoritam mora obraditi 1 elemenata (što nije toliko za bazu podataka):

• O(1) algoritam će vas koštati 1 operaciju
• O(log(n)) algoritam će vas koštati 14 operacija
• O(n) algoritam će vas koštati 1 operacija
• O(n*log(n)) algoritam će vas koštati 14 operacija
• O(n2) algoritam će vas koštati 1 operacija

Nisam računao, ali rekao bih da sa O(n2) algoritmom imate vremena da popijete kafu (čak i dvije!). Ako dodate još 0 volumenu podataka, imat ćete vremena da odrijemate.

Hajdemo dublje

Za referencu:

• Dobro traženje hash tablice pronalazi element u O(1).
• Pretraživanje dobro izbalansiranog stabla daje rezultate u O(log(n)).
• Pretraživanje niza daje rezultate u O(n).
• Najbolji algoritmi za sortiranje imaju složenost O(n*log(n)).
• Loš algoritam za sortiranje ima složenost O(n2).

Napomena: U sljedećim dijelovima ćemo vidjeti ove algoritme i strukture podataka.

Postoji nekoliko tipova vremenske složenosti algoritama:

• prosečan scenario slučaja
• najboljem scenariju
• i najgorem scenariju

Vremenska složenost je često najgori scenario.

Govorio sam samo o vremenskoj složenosti algoritma, ali složenost se odnosi i na:

• potrošnja memorije algoritma
• algoritam potrošnje I/O diska

Naravno, postoje komplikacije gore od n2, na primjer:

• n4: ovo je strašno! Neki od navedenih algoritama imaju ovu složenost.
• 3n: ovo je još gore! Jedan od algoritama koje ćemo vidjeti u sredini ovog članka ima ovu složenost (i zapravo se koristi u mnogim bazama podataka).
• faktorijel n: nikada nećete dobiti svoje rezultate čak ni sa malom količinom podataka.
• nn: Ako naiđete na ovu složenost, zapitajte se da li je to zaista vaše polje djelovanja...

Napomena: Nisam vam dao stvarnu definiciju oznake velikog O, samo ideju. Ovaj članak možete pročitati na Wikipedia za realnu (asimptotičku) definiciju.

MergeSort

Šta radite kada trebate sortirati kolekciju? Šta? Pozivate funkciju sort()... Ok, dobar odgovor... Ali za bazu podataka, morate razumjeti kako ova funkcija sort() funkcionira.

Postoji nekoliko dobrih algoritama za sortiranje, pa ću se fokusirati na najvažnije: sortiranje spajanjem. Možda ne razumijete zašto je sortiranje podataka korisno upravo sada, ali trebali biste nakon dijela za optimizaciju upita. Štaviše, razumevanje sortiranja spajanjem će nam pomoći da kasnije razumemo uobičajenu operaciju spajanja baze podataka koja se zove spojiti Pridruži se (udruženje spajanja).

Spoji

Kao i mnogi korisni algoritmi, sortiranje spajanjem se oslanja na trik: kombinovanje 2 sortirana niza veličine N/2 u sortirani niz sa N elementima košta samo N operacija. Ova operacija se zove spajanje.

Pogledajmo šta to znači na jednostavnom primjeru:

Ova slika pokazuje da za izgradnju konačnog sortiranog niza od 8 elemenata trebate samo jednom ponoviti 2 niza od 4 elementa. Pošto su oba niza od 4 elementa već sortirana:

• 1) poredite oba trenutna elementa u dva niza (na početku struja = prva)
• 2) zatim uzmite najmanji i stavite ga u niz od 8 elemenata
• 3) i prijeđite na sljedeći element u nizu gdje ste uzeli najmanji element
• i ponavljajte 1,2,3 dok ne dođete do posljednjeg elementa jednog od nizova.
• Zatim uzimate preostale elemente drugog niza da ih stavite u niz od 8 elemenata.

Ovo funkcionira jer su oba niza od 4 elementa sortirana i tako da se ne morate "vratiti" u te nizove.

Sada kada smo razumjeli trik, evo mog pseudokoda za spajanje:

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;

Sortiranje spajanjem razbija problem na manje probleme, a zatim pronalazi rezultate manjih problema kako bi se dobio rezultat originalnog problema (napomena: ovaj tip algoritma se zove podijeli pa vladaj). Ako ne razumijete ovaj algoritam, ne brinite; Nisam razumeo kada sam to prvi put video. Ako vam može pomoći, ovaj algoritam vidim kao dvofazni algoritam:

• Faza podjele, gdje se niz dijeli na manje nizove
• Faza sortiranja je u kojoj se mali nizovi kombinuju (koristeći uniju) kako bi se formirao veći niz.

Faza podjele

U fazi podjele, niz se dijeli na unitarne nizove u 3 koraka. Formalni broj koraka je log(N) (pošto je N=8, log(N) = 3).

Kako ja to znam?

Ja sam genije! Jednom rečju - matematika. Ideja je da svaki korak dijeli veličinu originalnog niza sa 2. Broj koraka je koliko puta možete podijeliti originalni niz na dva. Ovo je tačna definicija logaritma (baza 2).

Faza sortiranja

U fazi sortiranja, počinjete s unitarnim (jednostrukim) nizovima. Tokom svakog koraka primjenjujete više operacija spajanja i ukupni trošak je N = 8 operacija:

• U prvoj fazi imate 4 spajanja koja koštaju po 2 operacije
• U drugom koraku imate 2 spajanja koja koštaju po 4 operacije
• U trećem koraku imate 1 stapanje koje košta 8 operacija

Pošto postoji log(N) koraka, ukupni trošak N * log(N) operacije.

Prednosti sortiranja spajanjem

Zašto je ovaj algoritam tako moćan?

Jer:

• Možete ga promijeniti da smanjite memorijski otisak tako da ne kreirate nove nizove već direktno modificirate ulazni niz.

Napomena: ovaj tip algoritma se zove in-mjesto (sortiranje bez dodatne memorije).

• Možete ga promijeniti tako da istovremeno koristi prostor na disku i malu količinu memorije, a da pritom ne stvarate značajne troškove I/O diska. Ideja je da se u memoriju učitaju samo oni dijelovi koji se trenutno obrađuju. Ovo je važno kada trebate sortirati višegigabajtnu tabelu sa samo 100-megabajtnim memorijskim baferom.

Napomena: ovaj tip algoritma se zove eksterno sortiranje.

• Možete ga promijeniti da radi na više procesa/nitova/servera.

Na primjer, distribuirano sortiranje spajanjem je jedna od ključnih komponenti Hadoop (što je struktura u velikim podacima).

• Ovaj algoritam može pretvoriti olovo u zlato (zaista!).

Ovaj algoritam za sortiranje se koristi u većini (ako ne i u svim) bazama podataka, ali nije jedini. Ako želite da saznate više, možete pročitati ovo istraživački rad, koji raspravlja o prednostima i nedostacima uobičajenih algoritama za sortiranje baza podataka.

Niz, stablo i hash tabela

Sada kada smo razumjeli ideju vremenske složenosti i sortiranja, trebao bih vam reći o 3 strukture podataka. Ovo je važno jer oni su osnova modernih baza podataka. Također ću predstaviti koncept indeks baze podataka.

Massiv

Dvodimenzionalni niz je najjednostavnija struktura podataka. Tabela se može posmatrati kao niz. Na primjer:

Ovaj dvodimenzionalni niz je tabela sa redovima i kolonama:

• Svaka linija predstavlja entitet
• Kolone pohranjuju svojstva koja opisuju entitet.
• Svaka kolona pohranjuje podatke određenog tipa (cijeli broj, niz, datum...).

Ovo je zgodno za pohranjivanje i vizualizaciju podataka, međutim, kada trebate pronaći određenu vrijednost, to nije prikladno.

Na primjer, ako želite pronaći sve momke koji rade u UK, trebali biste pogledati svaki red da biste utvrdili pripada li taj red UK. To će vas koštati N transakcijagde N - broj linija, što nije loše, ali može li postojati brži način? Sada je vrijeme da se upoznamo sa drvećem.

Napomena: Većina modernih baza podataka pruža proširene nizove za efikasno skladištenje tabela: tabele organizovane u hrpi i tabele organizovane u indeksu. Ali to ne mijenja problem brzog pronalaženja određenog stanja u grupi kolona.

Stablo baze podataka i indeks

Binarno stablo pretraživanja je binarno stablo sa posebnim svojstvom, ključ na svakom čvoru mora biti:

• veći od svih ključeva pohranjenih u lijevom podstablu
• manje od svih ključeva pohranjenih u desnom podstablu

Hajde da vidimo šta ovo znači vizuelno

Ideja

Ovo stablo ima N = 15 elemenata. Recimo da tražim 208:

• Počinjem od korijena čiji je ključ 136. Od 136<208, gledam desno podstablo čvora 136.
• 398>208 stoga gledam lijevo podstablo čvora 398
• 250>208 stoga gledam lijevo podstablo čvora 250
• 200<208, stoga gledam desno podstablo čvora 200. Ali 200 nema desno podstablo, vrijednost ne postoji (jer ako postoji, biće u desnom podstablu 200).

Sada recimo da tražim 40

• Počinjem od korijena čiji je ključ 136. Pošto je 136 > 40, gledam lijevo podstablo čvora 136.
• 80 > 40, stoga gledam lijevo podstablo čvora 80
• 40= 40, čvor postoji. Uzimam ID reda unutar čvora (nije prikazan na slici) i tražim u tabeli dati ID reda.
• Poznavanje ID-a reda mi omogućava da znam tačno gdje se podaci nalaze u tabeli, tako da mogu odmah da ih preuzmem.

Na kraju, oba pretraživanja će me koštati broj nivoa unutar stabla. Ako pažljivo pročitate dio o sortiranju spajanjem, trebali biste vidjeti da postoje nivoi dnevnika (N). ispada, dnevnik troškova pretraživanja (N), nije loše!

Vratimo se našem problemu

Ali ovo je vrlo apstraktno, pa da se vratimo na naš problem. Umjesto jednostavnog cijelog broja, zamislite niz koji predstavlja nečiju državu u prethodnoj tabeli. Recimo da imate stablo koje sadrži polje "država" (kolona 3) tabele:

• Ako želite znati ko radi u UK
• pogledate u drvo da dobijete čvor koji predstavlja Veliku Britaniju
• unutar "UKnode" naći ćete lokaciju evidencije radnika u UK.

Ova pretraga će koštati log(N) operacija umjesto N operacija ako direktno koristite niz. Ono što ste upravo predstavili je bilo indeks baze podataka.

Možete napraviti stablo indeksa za bilo koju grupu polja (niz, broj, 2 reda, broj i niz, datum...) sve dok imate funkciju za poređenje ključeva (tj. grupa polja) tako da možete postaviti red među ključevima (što je slučaj za sve osnovne tipove u bazi podataka).

B+TreeIndex

Iako ovo stablo dobro funkcionira za dobivanje određene vrijednosti, postoji VELIKI problem kada vam zatreba dobiti više elemenata između dvije vrijednosti. Ovo će koštati O(N) jer ćete morati pogledati svaki čvor u stablu i provjeriti da li se nalazi između ove dvije vrijednosti (npr. s uređenim obilaskom stabla). Štaviše, ova operacija nije prilagođena za disk I/O jer morate pročitati cijelo stablo. Moramo pronaći način za efikasno izvršenje zahtjev za rasponom. Da bi riješili ovaj problem, moderne baze podataka koriste modificiranu verziju prethodnog stabla pod nazivom B+Tree. U stablu B+drvo:

• samo najniži čvorovi (listovi) pohraniti informacije (lokacija redova u povezanoj tabeli)
• ostali čvorovi su ovdje za rutiranje do ispravnog čvora tokom pretrage.

Kao što vidite, ovdje ima više čvorova (dva puta). Zaista, imate dodatne čvorove, "čvorove odluke", koji će vam pomoći da pronađete ispravan čvor (koji pohranjuje lokaciju redova u pridruženoj tablici). Ali složenost pretraživanja je i dalje O(log(N)) (postoji samo još jedan nivo). Velika razlika je u tome čvorovi na nižem nivou su povezani sa svojim nasljednicima.

Sa ovim B+Stablom, ako tražite vrijednosti između 40 i 100:

• Samo trebate potražiti 40 (ili najbližu vrijednost nakon 40 ako 40 ne postoji) kao što ste radili s prethodnim stablom.
• Zatim prikupite 40 nasljednika koristeći direktne veze za nasljednike dok ne dođete do 100.

Recimo da ste pronašli M nasljednika, a stablo ima N čvorova. Pronalaženje određenog čvora košta log(N) kao prethodno stablo. Ali kada dobijete ovaj čvor, dobićete M nasljednika u M operacijama s referencama na njihove nasljednike. Ova pretraga košta samo M+log(N) operacije u poređenju sa N operacijama na prethodnom stablu. Štaviše, ne morate čitati cijelo stablo (samo M+log(N) čvorova), što znači manje korištenje diska. Ako je M malo (npr. 200 redova), a N veliko (1 redova), bit će VELIKA razlika.

Ali tu su (opet!) novi problemi. Ako dodate ili izbrišete red u bazi podataka (i stoga u povezanom indeksu B+Tree):

• morate održavati red između čvorova unutar B+Stabla, inače nećete moći pronaći čvorove unutar nesortiranog stabla.
• morate zadržati minimalni mogući broj nivoa u B+Tree, inače vremenska složenost O(log(N)) postaje O(N).

Drugim riječima, B+Tree mora biti samouređen i uravnotežen. Srećom, to je moguće pomoću pametnih operacija brisanja i umetanja. Ali ovo dolazi po cijeni: umetanja i brisanja u B+ stablu koštaju O(log(N)). Zato su neki od vas to čuli korištenje previše indeksa nije dobra ideja. stvarno, usporavate brzo umetanje/ažuriranje/brisanje reda u tabelijer baza podataka treba da ažurira indekse tabele koristeći skupu operaciju O(log(N)) za svaki indeks. Štaviše, dodavanje indeksa znači veće opterećenje za menadžer transakcija (biće opisano na kraju članka).

Za više detalja, možete pogledati članak na Wikipediji B+drvo. Ako želite primjer implementacije B+Tree u bazu podataka, pogledajte ovaj članak и ovaj članak od vodećeg MySQL programera. Oboje se fokusiraju na to kako InnoDB (MySQL motor) rukuje indeksima.

Napomena: Čitalac mi je rekao da bi, zbog optimizacije niskog nivoa, B+ stablo trebalo biti potpuno izbalansirano.

Hashtable

Naša posljednja važna struktura podataka je hash tablica. Ovo je vrlo korisno kada želite brzo potražiti vrijednosti. Štoviše, razumijevanje hash tablice će nam pomoći da kasnije shvatimo uobičajenu operaciju spajanja baze podataka koja se zove hash join ( hash join). Ovu strukturu podataka baza podataka također koristi za pohranjivanje nekih internih stvari (npr. zaključati sto ili pufer pufera, kasnije ćemo vidjeti oba ova koncepta).

Haš tabela je struktura podataka koja brzo pronalazi element po ključu. Da biste napravili hash tablicu potrebno je definirati:

• trag za vaše elemente
• hash funkcija za ključeve. Izračunati hešovi ključa daju lokaciju elemenata (zv segmentima ).
• funkcija za poređenje ključeva. Nakon što pronađete ispravan segment, morate pronaći element koji tražite unutar segmenta koristeći ovo poređenje.

Jednostavan primjer

Uzmimo jasan primjer:

Ova hash tabela ima 10 segmenata. Zato što sam lijen, slikao sam samo 5 segmenata, ali znam da si pametan, pa ću ti dozvoliti da sam zamisliš ostalih 5. Koristio sam hash funkciju po modulu 10 ključa. Drugim riječima, pohranjujem samo posljednju znamenku ključa elementa da pronađem njegov segment:

• ako je zadnja cifra 0, element pada u segment 0,
• ako je zadnja cifra 1, element pada u segment 1,
• ako je zadnja cifra 2, element pada u područje 2,
• ...

Funkcija poređenja koju sam koristio je jednostavno jednakost između dva cijela broja.

Recimo da želite da dobijete element 78:

• Heš tabela izračunava heš kod za 78, što je 8.
• Heš tabela gleda segment 8, a prvi element koji pronađe je 78.
• Ona vam vraća stavku 78
• Pretraga košta samo 2 operacije (jedan za izračunavanje hash vrijednosti, a drugi za traženje elementa unutar segmenta).

Sada recimo da želite da dobijete element 59:

• Heš tabela izračunava heš kod za 59, što je 9.
• Heš tabela pretražuje segment 9, prvi pronađeni element je 99. Pošto je 99!=59, element 99 nije važeći element.
• Po istoj logici uzimaju se drugi element (9), treći (79), ..., posljednji (29).
• Element nije pronađen.
• Pretraga je koštala 7 operacija.

Dobra hash funkcija

Kao što vidite, u zavisnosti od vrijednosti koju tražite, cijena nije ista!

Ako sada promijenim hash funkciju po modulu 1 ključa (tj. uzimajući zadnjih 000 cifara), drugo traženje košta samo 000 operaciju jer nema elemenata u segmentu 6. Pravi izazov je pronaći dobru hash funkciju koja će kreirati kante koje sadrže vrlo mali broj elemenata.

U mom primjeru, lako je pronaći dobru hash funkciju. Ali ovo je jednostavan primjer, pronalaženje dobre hash funkcije je teže kada je ključ:

• niz (na primjer - prezime)
• 2 reda (na primjer - prezime i ime)
• 2 reda i datum (na primjer - prezime, ime i datum rođenja)
• ...

Uz dobru hash funkciju, traženje hash tablice košta O(1).

Niz vs hash tablica

Zašto ne koristiti niz?

Hmm, dobro pitanje.

• Heš tabela može biti djelomično učitano u memoriju, a preostali segmenti mogu ostati na disku.
• Kod niza morate koristiti neprekidni prostor u memoriji. Ako učitavate veliki sto vrlo je teško naći dovoljno kontinuiranog prostora.
• Za hash tabelu, možete odabrati ključ koji želite (na primjer, zemlju i prezime osobe).

Za više informacija, možete pročitati članak o JavaHashMap, što je efikasna implementacija hash tablice; ne morate razumjeti Javu da biste razumjeli koncepte pokrivene u ovom članku.

izvor: www.habr.com