Hei, Habr! Jeg presenterer for din oppmerksomhet en oversettelse av artikkelen
"Hvordan fungerer en relasjonsdatabase".

Når det kommer til relasjonsdatabaser kan jeg ikke unngå å tenke at noe mangler. De brukes overalt. Det er mange forskjellige databaser tilgjengelig, fra den lille og nyttige SQLite til den kraftige Teradata. Men det er bare noen få artikler som forklarer hvordan databasen fungerer. Du kan søke selv ved å bruke "howdoesarelationaldatabasework" for å se hvor få resultater det er. Dessuten er disse artiklene korte. Hvis du leter etter de nyeste buzzy-teknologiene (BigData, NoSQL eller JavaScript), vil du finne mer dyptgående artikler som forklarer hvordan de fungerer.

Er relasjonsdatabaser for gamle og for kjedelige til å forklares utenfor universitetskurs, forskningsartikler og bøker?

Som utvikler hater jeg å bruke noe jeg ikke forstår. Og hvis databaser har vært brukt i mer enn 40 år, må det være en grunn. Gjennom årene har jeg brukt hundrevis av timer på å virkelig forstå disse merkelige svarte boksene som jeg bruker hver dag. Relasjonelle databaser veldig interessant fordi de basert på nyttige og gjenbrukbare konsepter. Hvis du er interessert i å forstå en database, men aldri har hatt tid eller lyst til å fordype deg i dette brede emnet, bør du nyte denne artikkelen.

Selv om tittelen på denne artikkelen er eksplisitt, Hensikten med denne artikkelen er ikke å forstå hvordan du bruker databasen. derfor, du bør allerede vite hvordan du skriver en enkel tilkoblingsforespørsel og grunnleggende spørsmål ULIK; ellers forstår du kanskje ikke denne artikkelen. Det er det eneste du trenger å vite, jeg skal forklare resten.

Jeg starter med noen grunnleggende datavitenskap, for eksempel tidskompleksiteten til algoritmer (BigO). Jeg vet at noen av dere hater dette konseptet, men uten det vil dere ikke kunne forstå forviklingene i databasen. Siden dette er et stort tema, Jeg skal fokusere på det jeg synes er viktig: hvordan databasen behandler SQL forespørsel. Jeg skal bare introdusere grunnleggende databasekonsepterslik at du på slutten av artikkelen har en ide om hva som skjer under panseret.

Siden dette er en lang og teknisk artikkel som involverer mange algoritmer og datastrukturer, ta deg tid til å lese gjennom den. Noen begreper kan være vanskelige å forstå; du kan hoppe over dem og fortsatt få den generelle ideen.

For de mer kunnskapsrike blant dere, er denne artikkelen delt inn i 3 deler:

Oversikt over databasekomponenter på lavt og høyt nivå
Oversikt over spørringsoptimaliseringsprosessen
Oversikt over Transaksjons- og Buffer Pool Management

Tilbake til det grunnleggende

For mange år siden (i en galakse langt, langt unna...) måtte utviklere vite nøyaktig hvor mange operasjoner de koder. De kunne sine algoritmer og datastrukturer utenat fordi de ikke hadde råd til å kaste bort CPU og minne til sine trege datamaskiner.

I denne delen vil jeg minne deg på noen av disse konseptene da de er avgjørende for å forstå databasen. Jeg vil også introdusere konseptet databaseindeks.

O(1) vs O(n2)

I dag bryr mange utviklere seg ikke om tidskompleksiteten til algoritmer... og de har rett!

Men når du har å gjøre med mye data (jeg snakker ikke tusenvis) eller hvis du sliter på millisekunder, blir det kritisk å forstå dette konseptet. Og som du kan forestille deg, må databaser håndtere begge situasjoner! Jeg vil ikke få deg til å bruke mer tid enn nødvendig for å få frem poenget. Dette vil hjelpe oss å forstå konseptet med kostnadsbasert optimalisering senere (koste basert optimalisering).

Konseptet

Tidskompleksiteten til algoritmen brukes til å se hvor lang tid det vil ta å utføre en algoritme for en gitt mengde data. For å beskrive denne kompleksiteten bruker vi matematisk notasjon med stor O. Denne notasjonen brukes med en funksjon som beskriver hvor mange operasjoner en algoritme trenger for et gitt antall innganger.

For eksempel, når jeg sier "denne algoritmen har kompleksitet O(some_function())", betyr det at algoritmen krever some_function(a_certain_amount_of_data) operasjoner for å behandle en viss mengde data.

I dette tilfellet, Det er ikke mengden data som betyr noe**, ellers ** hvordan antall operasjoner øker med økende datavolum. Tidskompleksitet gir ikke et eksakt antall operasjoner, men er en god måte å estimere utførelsestid på.

I denne grafen kan du se antall operasjoner kontra mengden inndata for ulike typer algoritmetidskompleksiteter. Jeg brukte en logaritmisk skala for å vise dem. Datamengden øker med andre ord raskt fra 1 til 1 milliard. Vi kan se at:

O(1) eller konstant kompleksitet forblir konstant (ellers ville det ikke blitt kalt konstant kompleksitet).
O(logg(n)) forblir lav selv med milliarder av data.
Verste vanskelighetsgrad - O(n2), hvor antall operasjoner vokser raskt.
De to andre komplikasjonene øker like raskt.

Примеры

Med en liten mengde data er forskjellen mellom O(1) og O(n2) ubetydelig. La oss for eksempel si at du har en algoritme som trenger å behandle 2000 elementer.

O(1)-algoritmen vil koste deg 1 operasjon
O(log(n))-algoritmen vil koste deg 7 operasjoner
O(n)-algoritmen vil koste deg 2 operasjoner
O(n*log(n))-algoritmen vil koste deg 14 000 operasjoner
O(n2)-algoritmen vil koste deg 4 000 000 operasjoner

Forskjellen mellom O(1) og O(n2) virker stor (4 millioner operasjoner), men du vil miste maksimalt 2 ms, bare tid til å blinke med øynene. Faktisk kan moderne prosessorer behandle hundrevis av millioner operasjoner per sekund. Dette er grunnen til at ytelse og optimalisering ikke er et problem i mange IT-prosjekter.

Som sagt er det fortsatt viktig å kjenne til dette konseptet når man jobber med enorme mengder data. Hvis algoritmen denne gangen må behandle 1 000 000 elementer (som ikke er så mye for en database):

O(1)-algoritmen vil koste deg 1 operasjon
O(log(n))-algoritmen vil koste deg 14 operasjoner
O(n)-algoritmen vil koste deg 1 000 000 operasjoner
O(n*log(n))-algoritmen vil koste deg 14 000 000 operasjoner
O(n2)-algoritmen vil koste deg 1 000 000 000 000 operasjoner

Jeg har ikke gjort regnestykket, men jeg vil si at med O(n2)-algoritmen har du tid til å drikke en kaffe (til og med to!). Hvis du legger til ytterligere 0 til datavolumet, vil du ha tid til å ta en lur.

La oss gå dypere

For din informasjon:

Et godt hash-tabelloppslag finner et element i O(1).
Søking i et velbalansert tre gir resultater i O(log(n)).
Søking i en matrise gir resultater i O(n).
De beste sorteringsalgoritmene har kompleksitet O(n*log(n)).
En dårlig sorteringsalgoritme har kompleksitet O(n2).

Merk: I de følgende delene vil vi se disse algoritmene og datastrukturene.

Det finnes flere typer algoritmetidskompleksitet:

gjennomsnittlig case scenario
beste scenario
og verste fall

Tidskompleksitet er ofte det verste scenarioet.

Jeg snakket bare om tidskompleksiteten til algoritmen, men kompleksiteten gjelder også for:

minneforbruk av algoritmen
disk I/O-forbruksalgoritme

Selvfølgelig er det komplikasjoner verre enn n2, for eksempel:

n4: dette er forferdelig! Noen av de nevnte algoritmene har denne kompleksiteten.
3n: dette er enda verre! En av algoritmene vi vil se i midten av denne artikkelen har denne kompleksiteten (og den brukes faktisk i mange databaser).
faktoriell n: du vil aldri få resultatene dine selv med en liten mengde data.
nn: Hvis du møter denne kompleksiteten, bør du spørre deg selv om dette virkelig er ditt aktivitetsfelt...

Merk: Jeg ga deg ikke den faktiske definisjonen av den store O-betegnelsen, bare en idé. Du kan lese denne artikkelen på Wikipedia for den virkelige (asymptotiske) definisjonen.

MergeSort

Hva gjør du når du skal sortere en samling? Hva? Du kaller sort()-funksjonen... Ok, godt svar... Men for en database må du forstå hvordan denne sort()-funksjonen fungerer.

Det er flere gode sorteringsalgoritmer, så jeg vil fokusere på det viktigste: slå sammen sortering. Du forstår kanskje ikke hvorfor sortering av data er nyttig akkurat nå, men du bør gjøre det etter spørringsoptimaliseringsdelen. Dessuten vil forståelsen av merge sort hjelpe oss senere å forstå den vanlige database join-operasjonen kalt fusjonere bli medlem (sammenslåingsforening).

Slå sammen

Som mange nyttige algoritmer, er merge sort avhengig av et triks: å kombinere 2 sorterte arrays av størrelse N/2 til en N-element sortert array koster bare N operasjoner. Denne operasjonen kalles sammenslåing.

La oss se hva dette betyr med et enkelt eksempel:

Denne figuren viser at for å bygge den endelige sorterte 8-element-arrayen, trenger du bare å iterere én gang over de 2 4-element-arrayene. Siden begge 4-elements matriser allerede er sortert:

1) du sammenligner begge gjeldende elementene i to matriser (i begynnelsen strøm = først)
2) ta deretter den minste for å sette den inn i en 8-elementarray
3) og gå til neste element i matrisen der du tok det minste elementet
og gjenta 1,2,3 til du kommer til det siste elementet i en av arrayene.
Deretter tar du de resterende elementene i den andre matrisen for å sette dem inn i en matrise med 8 elementer.

Dette fungerer fordi begge 4-elements arrays er sortert, så du trenger ikke å "gå tilbake" i disse arrayene.

Nå som vi forstår trikset, her er min pseudokode for sammenslåing:

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 deler et problem i mindre problemer og finner deretter resultatene av de mindre problemene for å få resultatet av det opprinnelige problemet (merk: denne typen algoritme kalles divide and conquer). Hvis du ikke forstår denne algoritmen, ikke bekymre deg; Jeg skjønte det ikke første gang jeg så det. Hvis det kan hjelpe deg, ser jeg denne algoritmen som en tofasealgoritme:

Delingsfase, hvor matrisen er delt inn i mindre matriser
Sorteringsfasen er der små matriser kombineres (ved hjelp av union) for å danne en større matrise.

Delingsfase

I delingsstadiet deles matrisen inn i enhetlige matriser i 3 trinn. Det formelle antallet trinn er log(N) (siden N=8, log(N) = 3).

Hvordan vet jeg dette?

Jeg er genial! I et ord - matematikk. Tanken er at hvert trinn deler størrelsen på den originale matrisen med 2. Antall steg er antall ganger du kan dele den originale matrisen i to. Dette er den nøyaktige definisjonen av en logaritme (grunntall 2).

Sorteringsfase

I sorteringsfasen starter du med enhetlige (single-element) arrays. I løpet av hvert trinn bruker du flere fletteoperasjoner og den totale kostnaden er N = 8 operasjoner:

I det første trinnet har du 4 fusjoner som koster 2 operasjoner hver
I det andre trinnet har du 2 fusjoner som koster 4 operasjoner hver
I det tredje trinnet har du 1 fusjon som koster 8 operasjoner

Siden det er log(N)-trinn, totalkostnad N * log(N) operasjoner.

Fordeler med merge sort

Hvorfor er denne algoritmen så kraftig?

Fordi:

Du kan endre det for å redusere minnefotavtrykket slik at du ikke oppretter nye arrays, men direkte modifiserer inngangsarrayet.

Merk: denne typen algoritme kalles in-plass (sortering uten ekstra minne).

Du kan endre den for å bruke diskplass og en liten mengde minne samtidig uten å pådra seg betydelige disk I/O-kostnader. Ideen er å laste inn i minnet kun de delene som for øyeblikket blir behandlet. Dette er viktig når du trenger å sortere en multi-gigabyte-tabell med bare en 100-megabyte minnebuffer.

Merk: denne typen algoritme kalles ekstern sortering.

Du kan endre den til å kjøre på flere prosesser/tråder/servere.

For eksempel er distribuert sammenslåingssortering en av nøkkelkomponentene Hadoop (som er en struktur i big data).

Denne algoritmen kan gjøre bly til gull (virkelig!).

Denne sorteringsalgoritmen brukes i de fleste (om ikke alle) databaser, men den er ikke den eneste. Vil du vite mer kan du lese dette forskningsarbeid, som diskuterer fordeler og ulemper med vanlige databasesorteringsalgoritmer.

Array-, tre- og hasjtabell

Nå som vi forstår ideen om tidskompleksitet og sortering, bør jeg fortelle deg om 3 datastrukturer. Dette er viktig fordi de er grunnlaget for moderne databaser. Jeg vil også introdusere konseptet databaseindeks.

matrise

En todimensjonal matrise er den enkleste datastrukturen. En tabell kan betraktes som en matrise. For eksempel:

Denne 2-dimensjonale matrisen er en tabell med rader og kolonner:

Hver linje representerer en enhet
Kolonner lagrer egenskaper som beskriver enheten.
Hver kolonne lagrer data av en bestemt type (heltall, streng, dato...).

Dette er praktisk for å lagre og visualisere data, men når du trenger å finne en bestemt verdi, er dette ikke egnet.

For eksempel, hvis du ønsker å finne alle gutta som jobber i Storbritannia, må du se på hver rad for å finne ut om den raden tilhører Storbritannia. Det vil koste deg N transaksjonerDer N - antall linjer, som ikke er dårlig, men kan det være en raskere vei? Nå er det på tide for oss å bli kjent med trærne.

Merk: De fleste moderne databaser tilbyr utvidede arrays for å lagre tabeller effektivt: heaporganiserte tabeller og indeksorganiserte tabeller. Men dette endrer ikke problemet med å raskt finne en spesifikk tilstand i en gruppe kolonner.

Databasetre og indeks

Et binært søketre er et binært tre med en spesiell egenskap, nøkkelen ved hver node må være:

større enn alle nøklene som er lagret i det venstre undertreet
mindre enn alle nøkler som er lagret i høyre undertre

La oss se hva dette betyr visuelt

Idé

Dette treet har N = 15 elementer. La oss si at jeg ser etter 208:

Jeg starter på roten hvis nøkkel er 136. Siden 136<208 ser jeg på det høyre undertreet til node 136.
398>208 derfor ser jeg på det venstre undertreet til node 398
250>208 derfor ser jeg på det venstre undertreet til node 250
200<208, derfor ser jeg på høyre undertre til node 200. Men 200 har ikke noe høyre undertre, verdi eksisterer ikke (fordi hvis det eksisterer, vil det være i høyre undertre 200).

La oss nå si at jeg ser etter 40

Jeg starter ved roten hvis nøkkel er 136. Siden 136 > 40, ser jeg på venstre undertre til node 136.
80 > 40, derfor ser jeg på det venstre undertreet til node 80
40 = 40, node eksisterer. Jeg henter rad-ID-en inne i noden (ikke vist på bildet) og ser i tabellen etter gitt rad-ID.
Når jeg kjenner rad-ID-en, kan jeg vite nøyaktig hvor dataene er i tabellen, slik at jeg kan hente dem umiddelbart.

Til slutt vil begge søkene koste meg antall nivåer inne i treet. Hvis du leser delen om merge sort nøye, bør du se at det er log(N) nivåer. Det viser seg, søkekostnadslogg(N), ikke verst!

La oss gå tilbake til problemet vårt

Men dette er veldig abstrakt, så la oss komme tilbake til problemet vårt. I stedet for et enkelt heltall, se for deg en streng som representerer landet til noen i den forrige tabellen. La oss si at du har et tre som inneholder "land"-feltet (kolonne 3) i tabellen:

Hvis du vil vite hvem som jobber i Storbritannia
du ser på treet for å få noden som representerer Storbritannia
inne i "UKnode" finner du plasseringen av britiske arbeiderposter.

Dette søket vil koste log(N) operasjoner i stedet for N operasjoner hvis du bruker arrayet direkte. Det du nettopp presenterte var databaseindeks.

Du kan bygge et indekstre for en hvilken som helst gruppe med felt (streng, tall, 2 linjer, tall og streng, dato...) så lenge du har en funksjon for å sammenligne nøkler (dvs. feltgrupper) slik at du kan sette rekkefølge blant nøklene (noe som er tilfellet for alle grunnleggende typer i databasen).

B+Treindeks

Selv om dette treet fungerer bra for å få en bestemt verdi, er det et STORT problem når du trenger det få flere elementer mellom to verdier. Dette vil koste O(N) fordi du må se på hver node i treet og sjekke om den er mellom disse to verdiene (f.eks. med en ordnet kryssing av treet). Dessuten er denne operasjonen ikke disk I/O-vennlig siden du må lese hele treet. Vi må finne en måte å utføre effektivt på rekkeviddeforespørsel. For å løse dette problemet bruker moderne databaser en modifisert versjon av det forrige treet kalt B+Tree. I et B+Tre:

bare de laveste nodene (blader) lagre informasjon (plassering av rader i den relaterte tabellen)
resten av nodene er her for ruting til riktig node under søk.

Som du kan se, er det flere noder her (to ganger). Faktisk har du flere noder, "beslutningsnoder", som vil hjelpe deg med å finne den riktige noden (som lagrer plasseringen av radene i den tilhørende tabellen). Men søkekompleksiteten er fortsatt O(log(N)) (det er bare ett nivå til). Den store forskjellen er det noder på lavere nivå er koblet til deres etterfølgere.

Med dette B+Treet, hvis du leter etter verdier mellom 40 og 100:

Du trenger bare å se etter 40 (eller den nærmeste verdien etter 40 hvis 40 ikke eksisterer) som du gjorde med forrige tre.
Deretter samler du 40 arvinger ved å bruke direkte arvinger til du når 100.

La oss si at du finner M etterfølgere og treet har N noder. Å finne en spesifikk node koster logg(N) som det forrige treet. Men når du først får denne noden, vil du få M-etterfølgere i M-operasjoner med referanser til deres etterfølgere. Dette søket koster bare M+log(N) operasjoner sammenlignet med N operasjoner på forrige tre. Dessuten trenger du ikke å lese hele treet (bare M+log(N)-noder), noe som betyr mindre diskbruk. Hvis M er liten (f.eks. 200 rader) og N er stor (1 rader), vil det være STOR forskjell.

Men det er nye problemer her (igjen!). Hvis du legger til eller sletter en rad i databasen (og derfor i den tilhørende B+Tree-indeksen):

du må opprettholde orden mellom nodene inne i et B+Tre, ellers vil du ikke kunne finne nodene inne i et usortert tre.
du må beholde et minimum mulig antall nivåer i B+Tre, ellers blir O(log(N))-tidskompleksiteten O(N).

B+Tree skal med andre ord være selvbestillende og balansert. Heldigvis er dette mulig med smarte slette- og innsettingsoperasjoner. Men dette har en kostnad: innsettinger og slettinger i et B+-tre koster O(log(N)). Det er derfor noen av dere har hørt det å bruke for mange indekser er ikke en god idé. Egentlig, du bremser rask innsetting/oppdatering/sletting av en rad i en tabellfordi databasen må oppdatere tabellens indekser ved å bruke en dyr O(log(N)) operasjon for hver indeks. Dessuten betyr å legge til indekser mer arbeidsbelastning for transaksjonsansvarlig (vil bli beskrevet på slutten av artikkelen).

For mer informasjon, kan du se Wikipedia-artikkelen om B+Tre. Hvis du vil ha et eksempel på implementering av B+Tree i en database, ta en titt denne artikkelen и denne artikkelen fra en ledende MySQL-utvikler. De fokuserer begge på hvordan InnoDB (MySQL-motoren) håndterer indekser.

Merk: En leser fortalte meg at B+-treet burde være fullstendig balansert på grunn av optimaliseringer på lavt nivå.

Hastbar

Vår siste viktige datastruktur er hashtabellen. Dette er veldig nyttig når du raskt vil slå opp verdier. Dessuten vil forståelsen av en hash-tabell hjelpe oss senere å forstå en vanlig database-join-operasjon kalt en hash-join ( hasj bli med). Denne datastrukturen brukes også av databasen til å lagre noen interne ting (f.eks. låsebord eller bufferbasseng, vi skal se begge disse konseptene senere).

En hashtabell er en datastruktur som raskt finner et element etter nøkkelen. For å bygge en hashtabell må du definere:

ключ for elementene dine
hash-funksjon for nøkler. De beregnede nøkkelhasjene gir plasseringen av elementene (kalt segmenter ).
funksjon for å sammenligne nøkler. Når du har funnet riktig segment, må du finne elementet du leter etter innenfor segmentet ved hjelp av denne sammenligningen.

Enkelt eksempel

La oss ta et tydelig eksempel:

Denne hashtabellen har 10 segmenter. Fordi jeg er lat, har jeg bare avbildet 5 segmenter, men jeg vet at du er smart, så jeg lar deg se de andre 5 på egen hånd. Jeg brukte en hash-funksjon modulo 10 av nøkkelen. Med andre ord lagrer jeg bare det siste sifferet i elementets nøkkel for å finne segmentet:

hvis det siste sifferet er 0, faller elementet inn i segment 0,
hvis det siste sifferet er 1, faller elementet inn i segment 1,
hvis det siste sifferet er 2, faller elementet inn i område 2,
...

Sammenligningsfunksjonen jeg brukte er rett og slett likhet mellom to heltall.

La oss si at du ønsker å få element 78:

Hash-tabellen beregner hash-koden for 78, som er 8.
Hash-tabellen ser på segment 8, og det første elementet den finner er 78.
Hun returnerer vare 78 til deg
Søk koster kun 2 operasjoner (en for å beregne hash-verdien og den andre for å slå opp elementet i segmentet).

La oss nå si at du ønsker å få element 59:

Hash-tabellen beregner hash-koden for 59, som er 9.
Hash-tabellen søker i segment 9, det første elementet som ble funnet er 99. Siden 99!=59 er ikke element 99 et gyldig element.
Ved å bruke samme logikk blir det andre elementet (9), det tredje (79), ..., det siste (29) tatt.
Element ikke funnet.
Søket kostet 7 operasjoner.

God hash-funksjon

Som du kan se, avhengig av verdien du leter etter, er kostnaden ikke den samme!

Hvis jeg nå endrer hash-funksjonen modulo 1 av nøkkelen (det vil si å ta de siste 000 sifrene), koster det andre oppslaget kun 000 operasjon siden det ikke er noen elementer i segment 6. Den virkelige utfordringen er å finne en god hash-funksjon som vil lage bøtter som inneholder et svært lite antall elementer.

I mitt eksempel er det enkelt å finne en god hash-funksjon. Men dette er et enkelt eksempel, å finne en god hash-funksjon er vanskeligere når nøkkelen er:

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

Med en god hashfunksjon koster hashtabelloppslag O(1).

Array vs hash-tabell

Hvorfor ikke bruke en array?

Hmm, godt spørsmål.

Hash-tabellen kan være delvis lastet inn i minnet, og de resterende segmentene kan forbli på disken.
Med en matrise må du bruke sammenhengende plass i minnet. Hvis du laster et stort bord det er veldig vanskelig å finne nok sammenhengende plass.
For en hashtabell kan du velge nøkkelen du ønsker (for eksempel land og persons etternavn).

For mer informasjon kan du lese artikkelen om JavaHashMap, som er en effektiv implementering av en hashtabell; du trenger ikke å forstå Java for å forstå konseptene som dekkes i denne artikkelen.

Kilde: www.habr.com

Hvordan relasjonsdatabaser fungerer (del 1)