Hej Habr! Jeg præsenterer for din opmærksomhed oversættelsen af artiklen
"Hvordan fungerer en relationsdatabase".

Når det kommer til relationelle databaser kan jeg ikke lade være med at tænke, at der mangler noget. De bruges overalt. Der findes mange forskellige databaser, lige fra den lille og brugbare SQLite til den kraftfulde Teradata. Men der er kun få artikler, der forklarer, hvordan databasen fungerer. Du kan selv søge ved at bruge "howdoesarelationaldatabasework" for at se, hvor få resultater der er. Desuden er disse artikler korte. Hvis du leder efter de nyeste buzzy-teknologier (BigData, NoSQL eller JavaScript), vil du finde mere dybdegående artikler, der forklarer, hvordan de fungerer.

Er relationsdatabaser for gamle og for kedelige til at blive forklaret uden for universitetskurser, forskningsartikler og bøger?

Som udvikler hader jeg at bruge noget, jeg ikke forstår. Og hvis databaser har været brugt i mere end 40 år, skal der være en grund. Gennem årene har jeg brugt hundredvis af timer på virkelig at forstå disse mærkelige sorte kasser, som jeg bruger hver dag. Relationelle databaser meget interessant, fordi de baseret på brugbare og genanvendelige koncepter. Hvis du er interesseret i at forstå en database, men aldrig har haft tid eller lyst til at dykke ned i dette brede emne, bør du nyde denne artikel.

Selvom titlen på denne artikel er eksplicit, Formålet med denne artikel er ikke at forstå, hvordan man bruger databasen. Derfor, du burde allerede vide, hvordan man skriver en simpel forbindelsesanmodning og grundlæggende forespørgsler URIGT; ellers forstår du måske ikke denne artikel. Det er det eneste du behøver at vide, jeg forklarer resten.

Jeg vil starte med nogle grundlæggende datalogi, såsom tidskompleksitet af algoritmer (BigO). Jeg ved, at nogle af jer hader dette koncept, men uden det vil I ikke være i stand til at forstå forviklingerne i databasen. Da dette er et stort emne, Jeg vil fokusere på hvad jeg synes er vigtigt: hvordan databasen behandler SQL forespørgsel. Jeg vil lige introducere grundlæggende databasekoncepterså du i slutningen af artiklen har en idé om, hvad der foregår under motorhjelmen.

Da dette er en lang og teknisk artikel, der involverer en masse algoritmer og datastrukturer, så tag dig tid til at læse den igennem. Nogle begreber kan være svære at forstå; du kan springe dem over og stadig få den generelle idé.

For de mere vidende blandt jer er denne artikel opdelt i 3 dele:

Oversigt over databasekomponenter på lavt og højt niveau
Oversigt over forespørgselsoptimeringsprocessen
Oversigt over transaktions- og bufferpuljestyring

Tilbage til det basale

For år siden (i en galakse langt, langt væk...) skulle udviklere vide nøjagtigt antallet af operationer, de kodede. De kendte deres algoritmer og datastrukturer udenad, fordi de ikke havde råd til at spilde CPU'en og hukommelsen på deres langsomme computere.

I denne del vil jeg minde dig om nogle af disse begreber, da de er essentielle for at forstå databasen. Jeg vil også introducere konceptet database indeks.

O(1) vs. O(n2)

I dag er mange udviklere ligeglade med tidskompleksiteten af algoritmer... og de har ret!

Men når du har at gøre med en masse data (jeg taler ikke om tusindvis), eller hvis du kæmper på millisekunder, bliver det afgørende at forstå dette koncept. Og som du kan forestille dig, skal databaser håndtere begge situationer! Jeg vil ikke få dig til at bruge mere tid end nødvendigt på at få pointen igennem. Dette vil hjælpe os med at forstå begrebet omkostningsbaseret optimering senere (koste baseret optimering).

koncept

Tidskompleksitet af algoritmen bruges til at se, hvor lang tid en algoritme vil tage at fuldføre for en given mængde data. For at beskrive denne kompleksitet bruger vi matematisk notation med stor O. Denne notation bruges med en funktion, der beskriver hvor mange operationer en algoritme skal bruge for et givet antal input.

For eksempel, når jeg siger "denne algoritme har kompleksitet O(some_function())", betyder det, at algoritmen kræver some_function(a_certain_amount_of_data) operationer for at behandle en vis mængde data.

I dette tilfælde Det er ikke mængden af data, der betyder noget**, Ellers ** hvordan antallet af operationer stiger med stigende datamængde. Tidskompleksitet giver ikke et nøjagtigt antal operationer, men er en god måde at estimere eksekveringstiden på.

I denne graf kan du se antallet af operationer i forhold til mængden af inputdata for forskellige typer af algoritmetidskompleksiteter. Jeg brugte en logaritmisk skala til at vise dem. Med andre ord stiger mængden af data hurtigt fra 1 til 1 mia. Vi kan se, at:

O(1) eller konstant kompleksitet forbliver konstant (ellers ville det ikke blive kaldt konstant kompleksitet).
O(log(n)) forbliver lav selv med milliarder af data.
Værste vanskelighed - O(n2), hvor antallet af operationer vokser hurtigt.
De to andre komplikationer øges lige så hurtigt.

Примеры

Med en lille mængde data er forskellen mellem O(1) og O(n2) ubetydelig. Lad os for eksempel sige, at du har en algoritme, der skal behandle 2000 elementer.

O(1)-algoritmen vil koste dig 1 operation
O(log(n))-algoritmen vil koste dig 7 operationer
O(n)-algoritmen vil koste dig 2 operationer
O(n*log(n))-algoritmen vil koste dig 14 operationer
O(n2)-algoritmen vil koste dig 4 operationer

Forskellen mellem O(1) og O(n2) virker stor (4 millioner operationer), men du vil maksimalt miste 2 ms, bare tid til at blinke med øjnene. Faktisk kan moderne processorer behandle hundreder af millioner af operationer i sekundet. Derfor er ydeevne og optimering ikke et problem i mange it-projekter.

Som sagt er det stadig vigtigt at kende til dette koncept, når man arbejder med enorme mængder data. Hvis algoritmen denne gang skal behandle 1 elementer (hvilket ikke er så meget for en database):

O(1)-algoritmen vil koste dig 1 operation
O(log(n))-algoritmen vil koste dig 14 operationer
O(n)-algoritmen vil koste dig 1 operationer
O(n*log(n))-algoritmen vil koste dig 14 operationer
O(n2)-algoritmen vil koste dig 1 operationer

Jeg har ikke lavet regnestykket, men jeg vil sige, at med O(n2)-algoritmen har du tid til at drikke en kop kaffe (selv to!). Hvis du tilføjer yderligere 0 til datavolumen, har du tid til at tage en lur.

Lad os gå dybere

Til din information:

Et godt hash-tabelopslag finder et element i O(1).
Søgning i et velafbalanceret træ giver resultater i O(log(n)).
Søgning i et array giver resultater i O(n).
De bedste sorteringsalgoritmer har kompleksitet O(n*log(n)).
En dårlig sorteringsalgoritme har kompleksitet O(n2).

Bemærk: I de følgende dele vil vi se disse algoritmer og datastrukturer.

Der er flere typer algoritmers tidskompleksitet:

gennemsnitsscenarie
bedste tilfælde
og worst case scenario

Tidskompleksitet er ofte det værste tilfælde.

Jeg talte kun om tidskompleksiteten af algoritmen, men kompleksiteten gælder også for:

hukommelsesforbrug af algoritmen
disk I/O forbrugsalgoritme

Selvfølgelig er der komplikationer værre end n2, for eksempel:

n4: det er forfærdeligt! Nogle af de nævnte algoritmer har denne kompleksitet.
3n: det er endnu værre! En af de algoritmer, vi vil se i midten af denne artikel, har denne kompleksitet (og den bruges faktisk i mange databaser).
factorial n: du vil aldrig få dine resultater selv med en lille mængde data.
nn: Hvis du støder på denne kompleksitet, bør du spørge dig selv, om dette virkelig er dit aktivitetsområde...

Bemærk: Jeg gav dig ikke den egentlige definition af den store O-betegnelse, bare en idé. Du kan læse denne artikel på Википедии for den virkelige (asymptotiske) definition.

MergeSort

Hvad gør du, når du skal sortere en samling? Hvad? Du kalder sort()-funktionen... Ok, godt svar... Men for en database skal du forstå, hvordan denne sort()-funktion fungerer.

Der er flere gode sorteringsalgoritmer, så jeg vil fokusere på det vigtigste: flette sortering. Du forstår måske ikke, hvorfor sortering af data er nyttig lige nu, men du bør efter forespørgselsoptimeringsdelen. Desuden vil forståelsen af merge sort hjælpe os senere med at forstå den fælles database join-operation kaldet fusionere deltage (fusionsforening).

Fusionere

Som mange nyttige algoritmer er merge sort afhængig af et trick: at kombinere 2 sorterede arrays af størrelse N/2 til et N-element sorteret array koster kun N operationer. Denne operation kaldes sammenlægning.

Lad os se, hvad det betyder med et simpelt eksempel:

Denne figur viser, at for at bygge det endelige sorterede 8-element-array, behøver du kun at iterere én gang over de 2 4-element-arrays. Da begge 4-element arrays allerede er sorteret:

1) du sammenligner begge nuværende elementer i to arrays (i begyndelsen strøm = først)
2) tag derefter den mindste for at sætte den ind i en 8-elementarray
3) og gå til det næste element i arrayet, hvor du tog det mindste element
og gentag 1,2,3 indtil du når det sidste element i et af arrays.
Derefter tager du de resterende elementer i det andet array for at sætte dem i et 8 element array.

Dette virker, fordi begge 4-element arrays er sorteret, og så du behøver ikke at "gå tilbage" i disse arrays.

Nu hvor vi forstår tricket, her er min pseudokode til fletning:

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;

Merge sort opdeler et problem i mindre problemer og finder derefter resultaterne af de mindre problemer for at få resultatet af det oprindelige problem (bemærk: denne type algoritme kaldes divide and conquer). Hvis du ikke forstår denne algoritme, så fortvivl ikke; Jeg forstod det ikke første gang jeg så det. Hvis det kan hjælpe dig, ser jeg denne algoritme som en to-faset algoritme:

Divisionsfase, hvor arrayet er opdelt i mindre arrays
Sorteringsfasen er, hvor små arrays kombineres (ved hjælp af union) for at danne et større array.

Opdelingsfase

I divisionsfasen er arrayet opdelt i unitary arrays i 3 trin. Det formelle antal trin er log(N) (da N=8, log(N) = 3).

Hvordan ved jeg det?

Jeg er genial! I et ord - matematik. Ideen er, at hvert trin deler størrelsen af det originale array med 2. Antallet af trin er antallet af gange, du kan dele det originale array i to. Dette er den nøjagtige definition af en logaritme (grundtal 2).

Sorteringsfase

I sorteringsfasen starter du med unitære (single-element) arrays. Under hvert trin anvender du flere fletteoperationer, og de samlede omkostninger er N = 8 operationer:

I den første fase har du 4 sammenlægninger, der hver koster 2 operationer
I det andet trin har du 2 fletninger, der hver koster 4 operationer
I det tredje trin har du 1 fletning, som koster 8 operationer

Da der er log(N)-trin, samlede omkostninger N * log(N) operationer.

Fordele ved merge sort

Hvorfor er denne algoritme så kraftfuld?

Fordi:

Du kan ændre det for at reducere hukommelsesfodaftrykket, så du ikke opretter nye arrays, men direkte ændrer input-arrayet.

Bemærk: denne type algoritme kaldes in—placere (sortering uden ekstra hukommelse).

Du kan ændre det til at bruge diskplads og en lille mængde hukommelse på samme tid uden at pådrage sig betydelige disk I/O-omkostninger. Ideen er kun at indlæse de dele, der i øjeblikket behandles, i hukommelsen. Dette er vigtigt, når du skal sortere en multi-gigabyte tabel med kun en 100 megabyte hukommelsesbuffer.

Bemærk: denne type algoritme kaldes ekstern sortering.

Du kan ændre det til at køre på flere processer/tråde/servere.

For eksempel er distribueret flettesortering en af nøglekomponenterne Hadoop (som er en struktur i big data).

Denne algoritme kan gøre bly til guld (virkelig!).

Denne sorteringsalgoritme bruges i de fleste (hvis ikke alle) databaser, men den er ikke den eneste. Hvis du vil vide mere, kan du læse dette forskningsarbejde, som diskuterer fordele og ulemper ved almindelige databasesorteringsalgoritmer.

Array, træ og hash tabel

Nu hvor vi forstår ideen om tidskompleksitet og sortering, skal jeg fortælle dig om 3 datastrukturer. Dette er vigtigt, fordi de er grundlaget for moderne databaser. Jeg vil også introducere konceptet database indeks.

matrix

Et todimensionelt array er den enkleste datastruktur. Et bord kan opfattes som et array. For eksempel:

Dette 2-dimensionelle array er en tabel med rækker og kolonner:

Hver linje repræsenterer en enhed
Kolonner gemmer egenskaber, der beskriver objektet.
Hver kolonne gemmer data af en bestemt type (heltal, streng, dato...).

Dette er praktisk til lagring og visualisering af data, men når du skal finde en bestemt værdi, er dette ikke egnet.

For eksempel, hvis du vil finde alle de fyre, der arbejder i Storbritannien, skal du se på hver række for at afgøre, om den række tilhører Storbritannien. Det vil koste dig N transaktionerHvor N - antal linjer, hvilket ikke er dårligt, men kunne der være en hurtigere vej? Nu er det tid for os at stifte bekendtskab med træerne.

Bemærk: De fleste moderne databaser giver udvidede arrays til effektiv lagring af tabeller: heap-organiserede tabeller og indeksorganiserede tabeller. Men det ændrer ikke på problemet med hurtigt at finde en bestemt tilstand i en gruppe af kolonner.

Databasetræ og indeks

Et binært søgetræ er et binært træ med en speciel egenskab, nøglen ved hver node skal være:

større end alle de nøgler, der er gemt i det venstre undertræ
mindre end alle nøgler gemt i det højre undertræ

Lad os se, hvad det betyder visuelt

Idea

Dette træ har N = 15 elementer. Lad os sige, at jeg leder efter 208:

Jeg starter ved roden, hvis nøgle er 136. Siden 136<208 ser jeg på det højre undertræ af node 136.
398>208 derfor kigger jeg på venstre undertræ af node 398
250>208 derfor kigger jeg på venstre undertræ af node 250
200<208, derfor ser jeg på det højre undertræ af node 200. Men 200 har ikke noget højre undertræ, værdi eksisterer ikke (fordi hvis det findes, vil det være i det højre undertræ 200).

Lad os nu sige, at jeg leder efter 40

Jeg starter ved roden, hvis nøgle er 136. Siden 136 > 40 ser jeg på det venstre undertræ af node 136.
80 > 40, derfor ser jeg på det venstre undertræ af node 80
40 = 40, node eksisterer. Jeg henter række-id'et inde i noden (ikke vist på billedet) og kigger i tabellen efter det givne række-id.
At kende række-id'et giver mig mulighed for at vide præcis, hvor dataene er i tabellen, så jeg kan hente dem med det samme.

I sidste ende vil begge søgninger koste mig antallet af niveauer inde i træet. Hvis du læser delen om flettesortering omhyggeligt, bør du se, at der er log(N) niveauer. Det viser sig, søg omkostningslog(N), ikke dårligt!

Lad os vende tilbage til vores problem

Men dette er meget abstrakt, så lad os vende tilbage til vores problem. I stedet for et simpelt heltal kan du forestille dig en streng, der repræsenterer landet for en person i den foregående tabel. Lad os sige, at du har et træ, der indeholder feltet "land" (kolonne 3) i tabellen:

Hvis du vil vide, hvem der arbejder i Storbritannien
du ser på træet for at få den node, der repræsenterer Storbritannien
inde i "UKnode" finder du placeringen af britiske arbejderregistreringer.

Denne søgning vil koste log(N) operationer i stedet for N operationer, hvis du bruger arrayet direkte. Det du lige præsenterede var database indeks.

Du kan bygge et indekstræ for enhver gruppe af felter (streng, tal, 2 linjer, tal og streng, dato...), så længe du har en funktion til at sammenligne nøgler (dvs. feltgrupper), så du kan indstille rækkefølge blandt tasterne (hvilket er tilfældet for alle grundlæggende typer i databasen).

B+Træindeks

Selvom dette træ fungerer godt til at få en bestemt værdi, er der et STORT problem, når du har brug for det få flere elementer mellem to værdier. Dette vil koste O(N), fordi du bliver nødt til at se på hver knude i træet og tjekke, om den er mellem disse to værdier (f.eks. med en ordnet gennemkøring af træet). Desuden er denne operation ikke disk I/O-venlig, da du skal læse hele træet. Vi skal finde en måde at udføre effektivt på rækkeviddeanmodning. For at løse dette problem bruger moderne databaser en modificeret version af det tidligere træ kaldet B+Tree. I et B+træ-træ:

kun de laveste noder (blade) gemme oplysninger (placering af rækker i den relaterede tabel)
resten af noderne er her til routing til den rigtige node under søgning.

Som du kan se, er der flere noder her (to gange). Faktisk har du yderligere noder, "beslutningsknuder", som vil hjælpe dig med at finde den korrekte node (som gemmer placeringen af rækkerne i den tilknyttede tabel). Men søgekompleksiteten er stadig O(log(N)) (der er kun et niveau mere). Den store forskel er det noder på det lavere niveau er forbundet med deres efterfølgere.

Med dette B+Tree, hvis du leder efter værdier mellem 40 og 100:

Du skal bare kigge efter 40 (eller den nærmeste værdi efter 40, hvis 40 ikke findes), som du gjorde med det forrige træ.
Saml derefter 40 arvinger ved hjælp af direkte arvinger, indtil du når 100.

Lad os sige, at du finder M-efterfølgere, og træet har N noder. At finde en specifik node koster log(N) ligesom det forrige træ. Men når du først har fået denne node, får du M-efterfølgere i M-operationer med referencer til deres efterfølgere. Denne søgning koster kun M+log(N) operationer sammenlignet med N operationer på det forrige træ. Desuden behøver du ikke læse hele træet (kun M+log(N) noder), hvilket betyder mindre diskbrug. Hvis M er lille (f.eks. 200 rækker) og N er stor (1 rækker), vil der være STOR forskel.

Men der er nye problemer her (igen!). Hvis du tilføjer eller sletter en række i databasen (og derfor i det tilhørende B+Tree-indeks):

du skal opretholde orden mellem noderne inde i et B+Tree, ellers vil du ikke kunne finde noderne inde i et usorteret træ.
du skal beholde det mindst mulige antal niveauer i B+Tree, ellers bliver O(log(N)) tidskompleksiteten O(N).

Med andre ord skal B+Tree være selvbestilende og afbalanceret. Heldigvis er dette muligt med smarte sletnings- og indsætningsoperationer. Men dette har en pris: indsættelser og sletninger i et B+ træ koster O(log(N)). Det er derfor, nogle af jer har hørt det at bruge for mange indekser er ikke en god idé. Virkelig, du bremser hurtig indsættelse/opdatering/sletning af en række i en tabelfordi databasen skal opdatere tabellens indekser ved hjælp af en dyr O(log(N)) operation for hvert indeks. Desuden betyder tilføjelse af indekser mere arbejdsbyrde for transaktionsansvarlig (vil blive beskrevet i slutningen af artiklen).

For flere detaljer kan du se Wikipedia-artiklen om B+Træ. Hvis du vil have et eksempel på implementering af B+Tree i en database, så tag et kig denne artikel и denne artikel fra en førende MySQL-udvikler. De fokuserer begge på, hvordan InnoDB (MySQL-motoren) håndterer indekser.

Bemærk: En læser fortalte mig, at B+ træet skulle være fuldstændig afbalanceret på grund af optimeringer på lavt niveau.

Hastbar

Vores sidste vigtige datastruktur er hash-tabellen. Dette er meget nyttigt, når du hurtigt vil slå værdier op. Desuden vil forståelsen af en hash-tabel hjælpe os senere med at forstå en almindelig database join-operation kaldet en hash join ( hash join). Denne datastruktur bruges også af databasen til at gemme nogle interne ting (f.eks. låsebord eller bufferpulje, vi vil se begge disse begreber senere).

En hash-tabel er en datastruktur, der hurtigt finder et element ved dets nøgle. For at bygge en hash-tabel skal du definere:

ключ for dine elementer
hash funktion for nøgler. De beregnede nøglehasher angiver placeringen af elementerne (kaldet segmenter ).
funktion til at sammenligne nøgler. Når du har fundet det rigtige segment, skal du finde det element, du leder efter inden for segmentet, ved hjælp af denne sammenligning.

Simpelt eksempel

Lad os tage et klart eksempel:

Denne hash-tabel har 10 segmenter. Fordi jeg er doven, afbildede jeg kun 5 segmenter, men jeg ved, at du er smart, så jeg vil lade dig se de andre 5 af på egen hånd. Jeg brugte en hash-funktion modulo 10 af nøglen. Med andre ord gemmer jeg kun det sidste ciffer af elementets nøgle for at finde dets segment:

hvis det sidste ciffer er 0, falder elementet i segment 0,
hvis det sidste ciffer er 1, falder elementet i segment 1,
hvis det sidste ciffer er 2, falder elementet ind i område 2,
...

Den sammenligningsfunktion, jeg brugte, er simpelthen lighed mellem to heltal.

Lad os sige, at du vil have element 78:

Hash-tabellen beregner hash-koden for 78, som er 8.
Hash-tabellen ser på segment 8, og det første element, den finder, er 78.
Hun returnerer vare 78 til dig
Søgning koster kun 2 operationer (den ene til at beregne hashværdien og den anden til at slå elementet op i segmentet).

Lad os nu sige, at du vil have element 59:

Hash-tabellen beregner hash-koden for 59, som er 9.
Hash-tabellen søger i segment 9, det første fundne element er 99. Da 99!=59 er element 99 ikke et gyldigt element.
Ved at bruge den samme logik tages det andet element (9), det tredje (79), ..., det sidste (29).
Element ikke fundet.
Eftersøgningen kostede 7 operationer.

God hash funktion

Som du kan se, afhængigt af den værdi, du leder efter, er prisen ikke den samme!

Hvis jeg nu ændrer hash-funktionen modulo 1 af nøglen (det vil sige tager de sidste 000 cifre), koster det andet opslag kun 000 operation, da der ikke er nogen elementer i segment 6. Den virkelige udfordring er at finde en god hash-funktion, der vil skabe buckets indeholdende et meget lille antal elementer.

I mit eksempel er det nemt at finde en god hash-funktion. Men dette er et simpelt eksempel, at finde en god hash-funktion er sværere, når nøglen er:

streng (for eksempel - efternavn)
2 linjer (for eksempel - efternavn og fornavn)
2 linjer og dato (for eksempel - efternavn, fornavn og fødselsdato)
...

Med en god hash-funktion koster hash-tabelopslag O(1).

Array vs hash tabel

Hvorfor ikke bruge et array?

Hmm, godt spørgsmål.

Hashbordet kan være delvist indlæst i hukommelsen, og de resterende segmenter kan forblive på disken.
Med et array skal du bruge sammenhængende plads i hukommelsen. Hvis du læser et stort bord det er meget svært at finde tilstrækkelig sammenhængende plads.
Til en hash-tabel kan du vælge den nøgle, du ønsker (f.eks. land og persons efternavn).

For mere information kan du læse artiklen om JavaHashMap, som er en effektiv implementering af en hash-tabel; du behøver ikke at forstå Java for at forstå de begreber, der er dækket i denne artikel.

Kilde: www.habr.com

Sådan fungerer relationelle databaser (del 1)