Kaip veikia reliacinė duomenų bazė

Kalbant apie reliacines duomenų bazes, negaliu nepagalvoti, kad kažko trūksta. Jie naudojami visur. Yra daugybė skirtingų duomenų bazių: nuo mažos ir naudingos SQLite iki galingos „Teradata“. Tačiau yra tik keli straipsniai, paaiškinantys, kaip veikia duomenų bazė. Galite patys google ieškoti „kaip veikia reliacinė duomenų bazė“, kad pamatytumėte, kiek rezultatų yra. Be to, tie straipsniai yra trumpi. Dabar, jei ieškosite paskutinių madingų technologijų („Big Data“, „NoSQL“ ar „JavaScript“), rasite daugiau išsamių straipsnių, paaiškinančių jų veikimą.

Ar reliacinės duomenų bazės yra per senos ir per nuobodžios, kad jas būtų galima paaiškinti ne universiteto kursuose, mokslo darbuose ir knygose?

Aš, kaip kūrėjas, KENKUosi to, ko nesuprantu. Ir jei duomenų bazės buvo naudojamos 40 metų, turi būti priežastis. Per tuos metus praleidau šimtus valandų, kad iš tikrųjų suprasčiau šias keistas juodas dėžutes, kurias kasdien naudoju. Reliacinės duomenų bazės yra labai įdomu, nes jie pagrįstas naudingomis ir daugkartinio naudojimo koncepcijomis. Jei duomenų bazės supratimas jus domina, bet niekada neturėjote laiko ar valios įsigilinti į šią plačią temą, šis straipsnis jums turėtų patikti.

Nors šio straipsnio pavadinimas yra aiškus, šio straipsnio tikslas NE suprasti, kaip naudotis duomenų baze. Todėl, jau turėtumėte žinoti, kaip parašyti paprastą prisijungimo užklausą ir pagrindines CRUD užklausas; kitaip gali nesuprasti šio straipsnio. Tai yra vienintelis dalykas, kurį reikia žinoti, aš paaiškinsiu visa kita.

Pradėsiu nuo kelių informatikos dalykų, tokių kaip laiko sudėtingumas. Žinau, kad kai kurie iš jūsų nekenčia šios koncepcijos, tačiau be jos negalite suprasti, koks sumanumas yra duomenų bazėje. Kadangi tai didžiulė tema, Aš sutelksiu dėmesį kas, mano manymu, yra būtina: kaip duomenų bazė tvarko SQL užklausą. Aš tik pristatysiu pagrindines duomenų bazės sąvokas kad straipsnio pabaigoje jūs gerai suprastumėte, kas vyksta po gaubtu.

Kadangi tai ilgas ir techninis straipsnis, apimantis daug algoritmų ir duomenų struktūrų, neskubėkite jį perskaityti. Kai kurias sąvokas sunkiau suprasti; galite jų praleisti ir vis tiek gauti bendrą idėją.

Labiau žinantiems iš jūsų šis straipsnis yra daugiau ar mažiau suskirstytas į 3 dalis:

• Žemo ir aukšto lygio duomenų bazių komponentų apžvalga
• Užklausos optimizavimo proceso apžvalga
• Sandorių ir buferio telkinių valdymo apžvalga

Labai seniai (toli toli esančioje galaktikoje …) kūrėjai turėjo tiksliai žinoti koduojamų operacijų skaičių. Jie mintinai žinojo savo algoritmus ir duomenų struktūras, nes negalėjo sau leisti švaistyti savo lėtų kompiuterių procesoriaus ir atminties.

Šioje dalyje jums priminsiu kai kurias iš šių sąvokų, nes jos yra būtinos norint suprasti duomenų bazę. Aš taip pat pristatysiu sąvoką duomenų bazės rodyklė.

O (1) vs O (n²)

Šiais laikais daugeliui kūrėjų nerūpi laiko sudėtingumas … ir jie teisūs!

Bet kai susiduriate su dideliu duomenų kiekiu (aš nekalbu apie tūkstančius) arba jei kovojate dėl milisekundžių, suprasti šią sąvoką tampa labai svarbu. Ir spėk ką, duomenų bazės turi spręsti abi situacijas! Aš jums ilgai nenuobodžiausiu, tik laikas sugalvoti idėją. Tai padės mums vėliau suprasti sąvoką sąnaudomis pagrįstas optimizavimas.

Sąvoka

The laiko sudėtingumas naudojamas norint pamatyti, kiek laiko užtruks algoritmas tam tikram duomenų kiekiui. Norėdami apibūdinti šį sudėtingumą, informatikai naudoja matematinį didįjį O žymėjimą. Šis žymėjimas naudojamas kartu su funkcija, apibūdinančia, kiek operacijų algoritmui reikia tam tikram įvesties duomenų kiekiui.

Pvz., Kai sakau „šis algoritmas yra O (kai kurios_funkcijos ())“, tai reiškia, kad tam tikram duomenų kiekiui algoritmui reikia atlikti tam tikras_funkcijos (a_kenkamas_duomenų_duomenų) operacijas, kad galėtų atlikti savo darbą.

Kas yra svarbu ne duomenų kiekį, o tai, kaip operacijų skaičius didėja, kai duomenų kiekis didėja. Laiko sudėtingumas nenurodo tikslaus operacijų skaičiaus, bet yra gera idėja.

Šiame paveikslėlyje galite pamatyti skirtingų tipų sudėtingumo raidą. Jai nubrėžti panaudojau logaritminę skalę. Kitaip tariant, duomenų skaičius greitai didėja nuo 1 iki 1 milijardo. Mes galime pamatyti, kad:

• The O (1) arba pastovus sudėtingumas išlieka pastovus (kitaip jis nebūtų vadinamas nuolatiniu kompleksiškumu).
• The O (žurnalas (n)) lieka mažai net ir turint milijardus duomenų.
• Blogiausias sudėtingumas yra O (n²) kur operacijų skaičius greitai sprogsta.
• Du othkartumplexitigreitai didėja.

Pavyzdžiai

Esant mažai duomenų, skirtumas tarp O (1) ir O (n²) yra nereikšmingas. Pavyzdžiui, tarkime, kad turite algoritmą, kuris turi apdoroti 2000 elementų.

• O (1) algoritmas jums kainuos 1 operaciją
• O (log (n)) algoritmas jums kainuos 7 operacijas
• O (n) algoritmas jums kainuos 2 000 operacijų
• O (n * log (n)) algoritmas jums kainuos 14 000 operacijų
• An O (n²) algoritmas jums kainuos 4 000 000 operacijų

Skirtumas tarp O (1) ir O (n²) atrodo daug (4 milijonai), bet prarasite ne daugiau kaip 2 ms, tik laikas mirksėti. Iš tiesų, dabartiniai procesoriai gali atlikti šimtus milijonų operacijų per sekundę. Štai kodėl našumas ir optimizavimas nėra daugelio IT projektų problema.

Kaip sakiau, vis tiek svarbu žinoti šią sąvoką, kai susiduriama su didžiuliu duomenų kiekiu. Jei šį kartą algoritmas turi apdoroti 1 000 000 elementų (duomenų bazei jis nėra toks didelis):

• O (1) algoritmas jums kainuos 1 operaciją
• O (log (n)) algoritmas jums kainuos 14 operacijų
• O (n) algoritmas jums kainuos 1 000 000 operacijų
• O (n * log (n)) algoritmas jums kainuos 14 000 000 operacijų
• An O (n²) algoritmas jums kainuos 1 000 000 000 000 operacijų

Aš nesu matematikos, bet sakyčiau su O (n²) algoritmą turite laiko išgerti kavos (net ir antrą!). Jei duomenų kiekiui pridėsite dar 0, turėsite laiko ilgai nusnausti.

Giliau

Norėdami suteikti jums idėją:

• Ieškant geroje maišos lentelėje pateikiamas elementas iš O (1)
• Ieškant gerai subalansuotame medyje gaunamas rezultatas O (log (n))
• Paieškos masyve rezultatas yra O (n)
• Geriausi rūšiavimo algoritmai turi O (n * log (n)) sudėtingumą.
• Netinkamas rūšiavimo algoritmas turi O (n²) sudėtingumas

Pastaba: kitose dalyse pamatysime šiuos algoritmus ir duomenų struktūras.

Laiko sudėtingumas yra kelių tipų:

• vidutinio atvejo scenarijaus
• geriausiu atveju
• ir blogiausiu atveju

Laiko sudėtingumas dažnai yra blogiausias scenarijus.

Aš kalbėjau tik apie laiko sudėtingumą, tačiau sudėtingumas taip pat tinka:

• algoritmo atminties sunaudojimas
• algoritmo disko įvesties / išvesties sunaudojimas

Žinoma, yra blogesnių kompleksiškumų nei n², Kaip:

• n⁴: kad čiulpia! Kai kurie iš paminėtų algoritmų yra tokie sudėtingi.
• 3ⁿ: kad čiulpia dar daugiau! Vienas iš algoritmų, kurį pamatysime šio straipsnio viduryje, turi tokį sudėtingumą (ir jis tikrai naudojamas daugelyje duomenų bazių).
• faktorius n: niekada negausite rezultatų, net turėdami nedidelį duomenų kiekį.
• nⁿ: jei susiduriate su tokiu sudėtingumu, turėtumėte savęs paklausti, ar IT iš tikrųjų yra jūsų sritis …

Pastaba: Aš jums nepateikiau tikrojo didžiojo O žymėjimo apibrėžimo, bet tik idėją. Šį straipsnį „Wikipedia“ galite perskaityti, kad gautumėte tikrąjį (asimptotinį) apibrėžimą.

Sujungti rūšiuoti

Ką darote, kai reikia rūšiuoti kolekciją? Ką? Jūs iškviečiate rūšiavimo () funkciją … gerai, geras atsakymas … Bet norint sukurti duomenų bazę, turite suprasti, kaip veikia ši rūšiavimo () funkcija.

Yra keli geri rūšiavimo algoritmai, todėl daugiausia dėmesio skirsiu svarbiausiam: sulieti rūšiuoti. Dabar galite nesuprasti, kodėl duomenų rūšiavimas yra naudingas, bet turėtumėte po užklausos optimizavimo dalies. Be to, susivienijimo rūšies supratimas padės mums vėliau suprasti bendrą duomenų bazės sujungimo operaciją, vadinamą sujungti prisijungti.

Sujungti

Kaip ir daugelis naudingų algoritmų, suliejimo rūšiavimas yra pagrįstas gudrybėmis: 2 N / 2 dydžio rūšiuotų masyvų sujungimas į N elementų rūšiuojamą masyvą kainuoja tik N operacijas. Ši operacija vadinama a sujungti.

Pažiūrėkime, ką tai reiškia, pateikdami paprastą pavyzdį:

Šiame paveiksle galite pamatyti, kad norint sukonstruoti galutinį surūšiuotą 8 elementų masyvą, reikia pakartoti tik vieną kartą 2 4 elementų masyvuose. Kadangi abi 4 elementų masyvai jau yra rūšiuojami:

• 1) palyginate abu dabartinius elementus 2 masyvuose (dabartinis = pirmą kartą pirmą kartą)
• 2) tada paimkite mažiausią, kad įdėtumėte jį į 8 elementų masyvą
• 3) ir eikite į kitą masyvo elementą, kurį paėmėte žemiausiu
• ir kartokite 1,2,3, kol pasieksite paskutinį vienos iš masyvų elementą.
• Tada paimkite likusius kito masyvo elementus, kad juos įdėtumėte į 8 elementų masyvą.

Tai veikia, nes abi 4 elementų masyvai yra rūšiuojami, todėl jums nereikia „grįžti“ šiuose masyvuose.

Dabar, kai supratome šį triuką, pateikiamas mano sujungimo rūšies pseudokodas.

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;

Sujungimo rūšis išskaido problemą į mažesnes problemas, tada suranda mažesnių problemų rezultatus, kad gautų pradinės problemos rezultatą (pastaba: tokio tipo algoritmai vadinami dalinkis ir užkariauk). Jei nesuprantate šio algoritmo, nesijaudinkite; Pirmą kartą tai pamačiusi nesupratau. Jei tai gali jums padėti, matau šį algoritmą kaip dviejų fazių algoritmą:

• Dalijimo fazė, kai masyvas yra padalintas į mažesnius masyvus
• Rūšiavimo fazė, kai maži masyvai sujungiami (naudojant sujungimą), kad susidarytų didesnis masyvas.

Dalijimo etapas

Dalijimo fazėje masyvas padalijamas į vienetinius masyvus, naudojant 3 žingsnius. Formalus žingsnių skaičius yra log (N) (nes N = 8, log (N) = 3).

Iš kur aš tai žinau?

Aš esu genijus! Vienu žodžiu: matematika. Idėja yra ta, kad kiekviename žingsnyje pradinio masyvo dydis padalijamas iš 2. Veiksmų skaičius rodo, kiek kartų pradinį masyvą galite padalyti iš dviejų. Tai tikslus logaritmo apibrėžimas (2 bazėje).

Rūšiavimo etapas

Rūšiavimo etape pradedate nuo vienetinių masyvų. Kiekvieno veiksmo metu taikote kelis sujungimus, o bendra operacijų kaina yra N = 8 operacijos:

• Pirmajame etape turite 4 sujungimus, kurie kainuoja po 2 operacijas
• Antrame etape turite 2 sujungimus, kurie kainuoja po 4 operacijas
• Trečiame etape turite 1 sujungimą, kuris kainuoja 8 operacijas

Kadangi yra žurnalo (N) žingsnių, bendros N * log (N) operacijų išlaidos.

Sujungimo galia

Kodėl šis algoritmas yra toks galingas?

Nes:

• Galite jį modifikuoti, kad sumažintumėte atminties pėdsaką, tokiu būdu, kad nesukuriate naujų masyvų, bet tiesiogiai modifikuojate įvesties masyvą.

Pastaba: tokio tipo algoritmai vadinami vietoje.

• Galite jį modifikuoti, kad tuo pačiu metu būtų galima naudoti disko vietą ir nedidelį atminties kiekį be didžiulės disko įvesties / išvesties bausmės. Idėja yra į atmintį įkelti tik tas dalis, kurios šiuo metu yra apdorojamos. Tai svarbu, kai reikia rūšiuoti kelių gigabaitų lentelę, kurioje yra tik 100 megabaitų atminties buferis.

Pastaba: tokio tipo algoritmai vadinami išoriniu rūšiavimu.

• Galite modifikuoti, kad jis veiktų keliuose procesuose / gijose / serveriuose.

Pvz., Paskirstyto sujungimo rūšiavimas yra vienas iš pagrindinių „Hadoop“ komponentų (tai yra „The Framework“ didžiuosiuose duomenyse).

• Šis algoritmas gali paversti šviną auksu (tikras faktas!).

Šis rūšiavimo algoritmas naudojamas daugumoje (jei ne visose) duomenų bazėse, tačiau jis nėra vienintelis. Jei norite sužinoti daugiau, galite perskaityti šį mokslinį darbą, kuriame aptariami duomenų bazėje paplitusių rūšiavimo algoritmų privalumai ir trūkumai.

Masyvo, medžio ir maišos stalas

Dabar, kai suprantame laiko sudėtingumo ir rūšiavimo idėją, turiu jums pasakyti apie 3 duomenų struktūras. Tai svarbu, nes jie šiuolaikinių duomenų bazių pagrindas. Aš taip pat pristatysiu sąvoką duomenų bazės rodyklė.

Masyvas

Dvimatis masyvas yra paprasčiausia duomenų struktūra. Lentelę galima vertinti kaip masyvą. Pavyzdžiui:

Šis dvimatis masyvas yra lentelė su eilutėmis ir stulpeliais:

• Kiekviena eilutė reiškia subjektą
• Stulpeliuose aprašomi objektai.
• Kiekviename stulpelyje saugomi tam tikro tipo duomenys (sveikasis skaičius, eilutė, data …).

Nors puiku laikyti ir vizualizuoti …