Hvordan relasjonelle databaser fungerer (Del 1)

Hei, Habr! Jeg presenterer for deg oversettelsen av artikkelen
"Hvordan fungerer en relasjonell database".

NÄr det gjelder relasjonelle databaser, kan jeg ikke la vÊre Ä tenke at noe mangler. De brukes overalt. Det finnes mange forskjellige databaser: fra den lille og nyttige SQLite til den kraftige Teradata. Men det finnes bare noen fÄ artikler som forklarer hvordan en database fungerer. Du kan sÞke selv med forespÞrselen "howdoesarelationaldatabasework" for Ä se hvor fÄ resultater det er. Dessuten er disse artiklene korte. Hvis du derimot leter etter de siste mote-teknologiene (BigData, NoSQL eller JavaScript), vil du finne flere dybdeartikler som forklarer hvordan de fungerer.

Er relasjonelle databaser for gamle og kjedelige til Ă„ forklare utenfor universitetets kurs, forskningsarbeid og bĂžker?

Hvordan relasjonelle databaser fungerer (Del 1)

Som utvikler hater jeg Ä bruke det jeg ikke forstÄr. Og hvis databaser har vÊrt i bruk i over 40 Är, mÄ det vÊre en grunn. I lÞpet av disse Ärene har jeg brukt hundrevis av timer pÄ Ä virkelig forstÄ disse merkelige svarte boksene jeg bruker hver dag. Relasjonsdatabaser svÊrt interessante, fordi de er basert pÄ nyttige og gjenbrukbare konsepter.Hvis du er interessert i Ä forstÄ databaser, men aldri har hatt tid eller lyst til Ä grave deg inn i dette omfattende temaet, vil du like denne artikkelen.

Selv om tittelen pÄ denne artikkelen er Äpenbar, er mÄlet med denne artikkelen ikke Ä forstÄ hvordan man bruker en database.FÞlgende, bÞr du allerede vite hvordan man skriver en enkel sammenkobling og grunnleggende spÞrringer, CRUD; ellers vil du kanskje ikke forstÄ denne artikkelen. Dette er det eneste du trenger Ä vite, jeg vil forklare alt annet.

Jeg begynner med noen grunnleggende konsepter innen datavitenskap, som tidskompleksitet av algoritmer (BigO). Jeg vet at noen av dere hater dette konseptet, men uten det vil du ikke kunne forstÄ nyansene inne i databasen. Siden dette er et stort tema, skal jeg fokusere pÄ det som jeg anser for viktig: hvordan databasen behandler SQL spÞrring.Jeg vil bare presentere grunnleggende databaskonsepter, slik at du ved slutten av artikkelen har en forstÄelse av hva som skjer under panseret.

Sidan detta Àr en lÄng och teknisk artikel som omfattar mÄnga algoritmer och datastrukturer, ta dig tid att lÀsa den. Vissa koncept kan vara svÄra att förstÄ; du kan hoppa över dem och ÀndÄ fÄ en allmÀn uppfattning.

För er som Àr mer insatta Àr denna artikel uppdelad i 3 delar:

  • Översikt över lĂ„gnivĂ„- och högnivĂ„databasekomponenter
  • Översikt över frĂ„gaoptimeringsprocessen
  • Översikt över transaktionshantering och buffertpoolen

ÅtergĂ„ till grunderna

MĂ„nga Ă„r sedan (i en avlĂ€gsen, avlĂ€gsen galax
), var utvecklare tvungna att exakt veta hur mĂ„nga operationer de kodade. De visste sina algoritmer och datastrukturer utan och innan, eftersom de inte kunde ha rĂ„d med att slösa CPU och minne av sina lĂ„ngsamma datorer.

I denna del pÄminner jag dig om nÄgra av dessa koncept, eftersom de Àr nödvÀndiga för att förstÄ databaser. Jag kommer ocksÄ att introducera konceptet databasindex.

O(1) vs O(n2)

För nĂ€rvarande bryr sig mĂ„nga utvecklare inte om tidskomplexiteten av algoritmer
 och de har rĂ€tt!

Men nÀr du hanterar stora mÀngder data (jag pratar inte om tusentals) eller om du kÀmpar för millisekunder, blir det avgörande att förstÄ detta koncept. Och som du förstÄr mÄste databaser hantera bÄda situationerna! Jag ska inte lÄta dig spendera mer tid Àn nödvÀndigt för att fÄnga kÀrnan. Detta kommer hjÀlpa oss senare att förstÄ kostnadsbaserad optimering (cost based optimization).

Konseptet

Tidskomplexiteten av en algoritm anvÀnds för att se hur lÄng tid det tar för algoritmen att utföra för en given mÀngd data. För att beskriva denna komplexitet anvÀnds matematiska beteckningar för stora O. Denna notation anvÀnds med en funktion som beskriver hur mÄnga operationer algoritmen behöver för en given mÀngd inmatningsdata.

Till exempel, nÀr jag sÀger "denna algoritm har komplexitet O (some_function() )", betyder det att för att bearbeta en viss mÀngd data behövs some_function(a_certain_amount_of_data) operationer.

Samtidig det viktiga Àr inte mÀngden data**, utan hur ** antalet operationer ökar med ökande datamÀngd. Tidskomplexiteten ger inte det exakta antalet operationer, men Àr ett bra sÀtt att uppskatta körtiden.

Hvordan relasjonelle databaser fungerer (Del 1)

I denne grafen kan du se forholdet mellom antall operasjoner og mengden inndata for ulike typer tidskompleksitet. Jeg har brukt en logaritmisk skala for Ă„ vise dem. Med andre ord, mengden data Ăžker raskt fra 1 til 1 milliard. Vi kan se at:

  • O(1) eller konstant kompleksitet forblir konstant (ellers ville det ikke bli kalt konstant kompleksitet).
  • O(log(n)) forblir lav selv med milliarder av data.
  • Verste kompleksitet — O(n2), hvor antallet operasjoner vokser raskt.
  • De to Ăžvrige kompleksitetene Ăžker ogsĂ„ raskt.

Eksempler

Ved en liten mengde data er forskjellen mellom O(1) og O(n2) ubetydelig. La oss for eksempel anta at du har en algoritme som mÄ behandle 2000 elementer.

  • Algoritmen O(1) vil koste deg 1 operasjon
  • Algoritmen O(log(n)) vil koste deg 7 operasjoner
  • Algoritmen O(n) vil koste deg 2 000 operasjoner
  • Algoritmen O(n * log(n)) vil koste deg 14 000 operasjoner
  • Algoritmen O(n2) 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 tiden til Ä blinke med Þynene. Faktisk kan moderne prosessorer hÄndtere hundrevis av millioner av operasjoner per sekund. Det er derfor ytelse og optimalisering ikke er et problem i mange IT-prosjekter.

Som jeg allerede har sagt, er det fortsatt viktig Ä vite om dette konseptet nÄr man arbeider med store mengder data. Hvis algoritmen denne gangen mÄ behandle 1 000 000 elementer (som ikke er sÄ mye for en database):

  • Algoritmen O(1) vil koste deg 1 operasjon
  • Algoritmen O(log(n)) vil koste deg 14 operasjoner
  • Algoritmen O(n) vil koste deg 1 000 000 operasjoner
  • Algoritmen O(n * log(n)) vil koste deg 14 000 000 operasjoner
  • Algoritmen O(n2) vil koste deg 1 000 000 000 000 operasjoner

Jeg gjorde ikke beregningene, men jeg vil si at med algoritmen O(n2) har du tid til Ă„ ta en kaffe (kanskje til og med to!). Hvis du legger til enda en 0 til mengden data, har du tid til Ă„ ta en lur.

La oss gÄ dypere

Til informasjon:

  • SĂžk i en god hashtabell finner et element pĂ„ O(1).
  • SĂžk i et godt balansert tre gir resultatet pĂ„ O(log(n)).
  • SĂžk i en liste gir resultatet pĂ„ O(n).
  • De beste sorteringsalgoritmene har kompleksitet O(n * log(n)).
  • En dĂ„rlig sorteringsalgoritme har kompleksitet O(n2).

Merk: I de neste delene vil vi se disse algoritmene og datastrukturene.

Det finnes flere typer tidskompleksitet for algoritmer:

  • den gjennomsnittlige scenariet
  • det beste utfallet
  • og det dĂ„rligste scenariet

Tidskompleksitet er ofte det dÄrligste scenariet.

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

  • minneforbruket til algoritmen
  • disk I/O-forbruket til algoritmen

SelvfĂžlgelig finnes det komplekser som er verre enn nÂČ, som for eksempel:

  • n⁎: dette er fryktelig! Noen av de nevnte algoritmene har denne kompleksiteten.
  • 3n: dette er enda verre! En av algoritmene vi skal se pĂ„ senere i artikkelen har denne kompleksiteten (og den brukes faktisk i mange databaser).
  • fakultet n: du fĂ„r aldri resultatene dine selv med et lite datasett.
  • nn: hvis du stĂžter pĂ„ denne kompleksiteten, bĂžr du spĂžrre deg selv om dette virkelig er ditt felt 


Merk: Jeg har gitt deg ikke en reell definisjon av betegnelsen «stor O», men bare en idé. Du kan lese denne artikkelen i Wikipedia for den reelle (asymptotiske) definisjonen.

MergeSort (SammenslÄing sortering)

Hva gjÞr du nÄr du trenger Ä sortere en samling? Hva? Du kaller funksjonen sort()
 Ok, godt svar
 Men for databaser mÄ du forstÄ hvordan denne sort()-funksjonen fungerer.

Det finnes flere gode sorteringsalgoritmer, sÄ jeg vil fokusere pÄ den viktigste: sammenslÄingssortering. Kanskje du ikke forstÄr nÄ hvorfor datainndeling er nyttig, men du mÄ forstÄ det etter delen om optimalisering av forespÞrslene. Videre vil forstÄelse av sammenslÄingssortering hjelpe oss senere med Ä forstÄ den generelle join-operasjonen i databaser, kalt merge join (sammenslÄing).

Merge (SammenslÄing)

Som mange nyttige algoritmer er sammenslÄingssorteringen basert pÄ en gimmik: Ä slÄ sammen 2 sorterede arrays av stÞrrelse N/2 i et N-element sortert array koster bare N operasjoner. Denne operasjonen kalles sammenslÄing.

La oss se hva dette betyr med et enkelt eksempel:

Hvordan relasjonelle databaser fungerer (Del 1)

I denne illustrasjonen ser vi at for Ä konstruere det endelige sorterte arrayet pÄ 8 elementer, trenger du bare Ä iterere én gang over 2x 4-element arrays. Siden begge 4-element arrays allerede er sortert:

  • 1) du sammenligner begge nĂ„vĂŠrende elementer i de to arrayene (i starten er det nĂ„vĂŠrende = fĂžrste)
  • 2) sĂ„ ta det minste tallet, og plasser det i et array med 8 elementer
  • 3) og gĂ„ videre til neste element i arrayet der du tok det minste elementet
  • og gjenta 1, 2, 3, inntil du nĂ„r det siste elementet i et av arrayene.
  • Deretter tar du de Ăžvrige elementene fra det andre arrayet for Ă„ plassere dem i et array med 8 elementer.

Dette fungerer fordi begge 4-element arrayene er sortert, og dermed trenger du ikke Ä "gÄ tilbake" i disse arrayene.

NÄ som vi har forstÄtt dette trikset, her er pseudokoden min for sammenslÄing:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //rekursive kall
   [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);

   //kombinere de 2 smÄ ordnede arrayene til et stort
   array result := merge(new_left_array,new_right_array);
   return result;

SammenslÄingssortering deler opp oppgaven i mindre oppgaver, og deretter finner resultatene av de mindre oppgavene for Ä fÄ resultatet av den opprinnelige oppgaven (merk: denne typen algoritme kalles del og hersk). Hvis du ikke forstÄr denne algoritmen, ikke bekymre deg; jeg forsto det ikke fÞrste gangen jeg sÄ den. Hvis det kan hjelpe deg, ser jeg denne algoritmen som en to-fase algoritme:

  • Delingsfase, hvor arrayet deles opp i mindre array
  • Sorteringsfase, hvor smĂ„ array kombineres (ved hjelp av sammenslĂ„ing) for Ă„ danne et stĂžrre array.

Delingsfase (Division phase)

Hvordan relasjonelle databaser fungerer (Del 1)

I delingsfasen deles arrayet opp i enhetlige array i 3 trinn. Det formelle antallet trinn er log(N) (siden N=8, log(N) = 3).

Hvordan vet jeg dette?

Jeg er et geni! Kort sagt – matematikk. Ideen er at hvert trinn deler stĂžrrelsen pĂ„ det opprinnelige arrayet i 2. Antallet trinn er antallet ganger du kan dele det opprinnelige arrayet i to. Dette er den nĂžyaktige definisjonen av logaritmen (med base 2).

Sorteringsfase (Sorting phase)

Hvordan relasjonelle databaser fungerer (Del 1)

I sorteringsfasen begynner du med enhetlige (enkelt-element) arrays. I lÞpet av hvert trinn bruker du flere sammenslÄingsoperasjoner, og den totale kostnaden er N = 8 operasjoner:

  • I fĂžrste trinn har du 4 sammenslĂ„inger som koster 2 operasjoner hver
  • I andre trinn har du 2 sammenslĂ„inger som koster 4 operasjoner hver
  • I tredje trinn har du 1 sammenslĂ„ing som koster 8 operasjoner

Siden det er log (N) trinn, den totale kostnaden N * log(N) operasjoner.

Fordelene med sammenslÄingssortering

Hvorfor er denne algoritmen sÄ kraftig?

Fordi:

  • Du kan endre den for Ă„ redusere minnebruken, slik at du ikke oppretter nye matriser, men i stedet direkte endrer inngangsmatrisen.

Merk: denne typen algoritmer kalles in—place (sortering uten ekstra minne).

  • Du kan endre den for samtidig Ă„ bruke diskplass og lite minne uten betydelige kostnader for disk-I/O. Ideen er Ă„ laste inn i minnet bare de delene som for Ăžyeblikket behandles. Dette er viktig nĂ„r du mĂ„ sortere en tabell som er flere gigabyte stor, kun med en minnebuffer pĂ„ 100 megabyte.

Merk: denne typen algoritmer kalles ekstern sortering.

  • Du kan endre den for Ă„ kjĂžre pĂ„ flere prosesser / trĂ„der / servere.

For eksempel er distribuert sammenslÄingssortering en av nÞkkelkomponentene Hadoop (som er en struktur i store data).

  • Denne algoritmen kan forvandle bly til gull (sant!).

Denne sorteringsalgoritmen brukes i de fleste (om ikke alle) databaser, men den er ikke den eneste. Hvis du vil lĂŠre mer, kan du lese dette forskningsarbeidet, som diskuterer fordeler og ulemper ved vanlige sorteringsalgoritmer i databaser.

Array, Tre og Hash-tabell

NÄ som vi forstÄr ideen om tidskompleksitet og sortering, mÄ jeg fortelle deg om 3 datatyper. Dette er viktig, fordi de er grunnlaget for moderne databaser.. Jeg vil ogsÄ introdusere begrepet databasindex.

Array

Et todimensjonalt array er den enkleste datatypen. En tabell kan betraktes som et array. For eksempel:

Hvordan relasjonelle databaser fungerer (Del 1)

Dette 2-dimensjonale arrayet representerer en tabell med rader og kolonner:

  • Hver rad representerer en enhet.
  • Kolonnene lagrer egenskaper som beskriver enheten.
  • Hver kolonne lagrer data av en bestemt type (integer, string, date 
).

Det er sÄ praktisk Ä lagre og visualisere data, men nÄr du mÄ finne en bestemt verdi, passer det ikke.

For eksempel, hvis du Ăžnsker Ă„ finne alle guttene som jobber i Storbritannia, mĂ„ du gĂ„ gjennom hver rad for Ă„ bestemme om denne raden tilhĂžrer Storbritannia. Dette vil koste deg N operasjoner., hvor N — antall rader, som er bra, men kan det vĂŠre en raskere mĂ„te? NĂ„ er det pĂ„ tide Ă„ bli kjent med trĂŠr.

Merk: de fleste moderne databaser tilbyr utvidede matriser for effektiv lagring av tabeller: heap-organizedtables og index-organizedtables. Men dette endrer ikke problemet med rask sĂžking av bestemte betingelser i en gruppe kolonner.

Database-tre og indeks

Et binÊrt sÞketre er et binÊrt tre med en spesiell egenskap, nÞkkelen i hver node mÄ vÊre:

  • stĂžrre enn alle nĂžklene som er lagret i venstre undertre
  • mindre enn alle nĂžklene som er lagret i hĂžyre undertre

La oss se hva dette betyr visuelt

Ideen

Hvordan relasjonelle databaser fungerer (Del 1)

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

  • Jeg begynner med roten, hvis nĂžkkel er 136. Siden 136<208, ser jeg pĂ„ hĂžyre undertre til node 136.
  • 398>208, derfor ser jeg pĂ„ venstre undertre til node 398
  • 250>208, derfor ser jeg pĂ„ venstre undertre til node 250
  • 200<208, derfor ser jeg pĂ„ hĂžyre undertre til node 200. Men 200 har ikke noe hĂžyre undertre, verdien finnes ikke (fordi, hvis den fantes, ville den vĂŠrt i hĂžyre undertre til 200).

NĂ„, la oss si at jeg leter etter 40

  • Jeg begynner med roten, hvis nĂžkkel er 136. Siden 136 > 40, ser jeg pĂ„ venstre undertre til node 136.
  • 80 > 40, derfor ser jeg pĂ„ venstre undertre til node 80
  • 40= 40, noden eksisterer. Jeg henter radidentifikatoren inne i noden (dette er ikke pĂ„ bildet) og ser i tabellen for den gitte radidentifikatoren.
  • Å kjenne radidentifikatoren lar meg vite hvor dataene faktisk ligger i tabellen, og derfor kan jeg hente dem umiddelbart.

Til slutt vil begge sÞkene koste meg antall nivÄer inne i treet. Hvis du leser nÞye delen om sammenfletting, mÄ du se at det her er log (N) nivÄer. SÄ det viser seg at kostnaden for sÞk er log(N), ikke dÄrlig!

La oss gÄ tilbake til problemet vÄrt

Men dette er veldig abstrakt, sÄ la oss gÄ tilbake til problemet vÄrt. I stedet for et enkelt heltall, forestill deg en streng som representerer et lands navn i den forrige tabellen. La oss si at du har et tre som inneholder feltet "country" (kolonne 3) i tabellen:

  • Hvis du vil vite hvem som jobber i Storbritannia
  • ser du pĂ„ treet for Ă„ fĂ„ noden som representerer Storbritannia
  • inni "UKnode" finner du plasseringen av postene til arbeidstakere i Storbritannia.

Denne sĂžket vil koste log(N) operasjoner i stedet for N operasjoner hvis du bruker et array direkte. Det du nettopp har presentert, var databaseindeks.

Du kan bygge et indeks tre for hvilken som helst gruppe av felt (streng, tall, 2 strenger, tall og streng, dato...) sÄ lenge du har en funksjon for Ä sammenligne nÞkler (dvs. grupper av felt) slik at du kan sette rekkefÞlgen mellom nÞklene (som er tilfelle for alle grunnleggende typer i databasen).

B+TreIndeks

Selv om dette treet fungerer godt for Ä fÄ en bestemt verdi, er det et STORT problem nÄr du trenger Ä hente flere elementer mellom to verdier. Dette vil koste O(N) fordi du mÄ se pÄ hver node i treet og sjekke om den ligger mellom disse to verdiene (for eksempel ved en sortert traversering av treet). Videre, denne operasjonen er ikke praktisk for disk I/O, da du mÄ lese hele treet. Vi trenger Ä finne en mÄte Ä effektivt utfÞre intervalforespÞrselen. For Ä lÞse dette problemet, bruker moderne databaser en modifisert versjon av det tidligere treet kalt B+Tre. I B+Tre treet:

  • bare de nederste nodene (bladene) lagrer informasjonen (plasseringen av radene i den tilknyttede tabellen)
  • de andre nodene er her for ruting til riktig node under sĂžk.

Hvordan relasjonelle databaser fungerer (Del 1)

Som du kan se, er det flere noder her (dobbelt sÄ mange). Faktisk har du ekstra noder, "beslutningstagere", som hjelper deg Ä finne riktig node (som lagrer plasseringen av radene i den tilknyttede tabellen). Men sÞke kompliserteheten er fortsatt O(log(N)) (det er bare et annet lag). Den store forskjellen er at nodene pÄ det nederste nivÄet er knyttet til sine etterkommere.

Med dette B+Tre, hvis du leter etter verdier fra 40 til 100:

  • Du trenger bare Ă„ sĂžke etter 40 (eller den nĂŠrmeste verdien etter 40, hvis 40 ikke eksisterer), som du gjorde med det tidligere treet.
  • Deretter samler du etterkommerne til 40, ved Ă„ bruke direkte referanser til etterkommerne, til du nĂ„r 100.

Anta at du fant M etterkommere, og treet har N noder. Å sĂžke etter en bestemt node koster log(N) slik som i det tidligere treet. Men, nĂ„r du har fĂ„tt denne noden, fĂ„r du M etterkommere i M operasjoner med referanser til deres etterkommere. Dette sĂžket koster bare M+log(N) operasjoner sammenlignet med N operasjoner med det forrige treet. Dessuten trenger du ikke Ă„ lese hele treet (kun M + log (N) noder), noe som betyr mindre diskbruk. Hvis M er lite (for eksempel 200 rader) og N er stort (1 000 000 rader), vil dette vĂŠre en STOR forskjell.

Men her er det nye problemer (igjen!). Hvis du legger til eller fjerner en rad i databasen (og dermed i den tilknyttede B+Tree-indeksen):

  • mĂ„ du opprettholde rekkefĂžlgen mellom nodene inne i B+Tree, ellers kan du ikke finne nodene inne i et usortert tre.
  • du mĂ„ bevare et minimum av nivĂ„er i B+Tree, ellers vil den tidsmessige kompleksiteten i O(log(N)) bli O(N).

Med andre ord, B+Tree mÄ vÊre selvordnende og balansert. Heldigvis er dette mulig med smarte slettings- og innsettingsoperasjoner. Men det kommer til en kostnad: innsetting og sletting i B+ treet koster O(log(N)). Det er derfor noen av dere har hÞrt at Ä bruke for mange indekser ikke er en sÄ god idé. Faktisk, du bremser rask innsetting / oppdatering / sletting av rader i tabellen, siden databasen mÄ oppdatere tabelens indekser med kostbare O(log(N)) operasjoner for hver indeks. I tillegg betyr det Ä legge til indekser en stÞrre belastning for transaksjonsbehandleren (som vil bli beskrevet mot slutten av artikkelen).

For mer informasjon, kan du se artikkelen pÄ Wikipedia om B+Tree. Hvis du Þnsker et eksempel pÄ implementering av B+Tree i en database, se denne artikkelen og denne artikkelen fra en ledende MySQL-utvikler. Begge fokuserer pÄ hvordan InnoDB (MySQL-motoren) hÄndterer indekser.

Merk: leseren fortalte meg at, pÄ grunn av lavnivÄoptimaliseringer, mÄ B+ treet vÊre fullstendig balansert.

Hashtable (Hash-table)

VÄr siste viktige datastruktur er hashtabellen. Den er veldig nyttig nÄr du vil raskt sÞke etter verdier. I tillegg vil forstÄelsen av hashtabeller hjelpe oss senere med Ä forstÄ den generelle operasjonen for sammenkobling i databasen, kalt hash-sammenkobling ( hash join). Denne datastrukturen brukes ogsÄ av databasen for Ä lagre noen interne ting (for eksempel, lÄsetabell eller bufferpool, vi vil se begge disse konseptene senere).

En hash-tabell er en datakonstruksjon som raskt finner et element basert pÄ nÞkkelen. For Ä bygge en hash-tabell mÄ du definere:

  • nĂžkkel for elementene dine
  • en hash-funksjon for nĂžklene. De beregnede hashene for nĂžklene gir plasseringen av elementene (kalt segmenter ).
  • en funksjon for Ă„ sammenligne nĂžkler. NĂ„r du har funnet riktig segment, mĂ„ du finne elementet du leter etter i segmentet, ved hjelp av denne sammenligningen.

Et enkelt eksempel

La oss ta et konkret eksempel:

Hvordan relasjonelle databaser fungerer (Del 1)

Denne hash-tabellen har 10 segmenter. Siden jeg er lat, har jeg bare illustrert 5 segmenter, men jeg vet at du er smart, sÄ jeg lar deg forestille deg de 5 andre selv. Jeg har brukt en hash-funksjon som tar modulus 10 av nÞkkelen. Med andre ord, beholdere bare det siste sifferet av nÞkkelen for Ä finne segmentet:

  • hvis det siste sifferet er 0, gĂ„r elementet til segment 0,
  • hvis det siste sifferet er 1, gĂ„r elementet til segment 1,
  • hvis det siste sifferet er 2, gĂ„r elementet til segment 2,
  • 


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

Anta at du Ăžnsker Ă„ hente elementet 78:

  • Hash-tabellen beregner hash-koden for 78, som er 8.
  • Hash-tabellen ser i segment 8, og det fĂžrste elementet den finner, er 78.
  • Den returnerer elementet 78 til deg
  • SĂžket kostet bare 2 operasjoner (en for Ă„ beregne hash-funksjonsverdien og en annen for Ă„ finne elementet innen segmentet).

NĂ„, antatt at du vil hente elementet 59:

  • Hash-tabellen beregner hash-koden for 59, som er 9.
  • Hash-tabellen sĂžker i segment 9, det fĂžrste funnet elementet er 99. Siden 99!=59, er ikke elementet 99 det riktige elementet.
  • Ved Ă„ bruke denne samme logikken, tas det andre elementet (9), tredje (79), 
, siste (29).
  • Elementet ble ikke funnet.
  • SĂžket kostet 7 operasjoner.

En god hash-funksjon

Som du ser, avhenger kostnaden av verdien du leter etter!

Hvis jeg nÄ endrer hash-funksjonen til modulus 1 000 000 av nÞkkelen (det vil si, tar de siste 6 sifrene), vil det andre sÞket koste bare 1 operasjon, siden det ikke finnes elementer i segment 000059. Den virkelige oppgaven er Ä finne en god hash-funksjon som lager segmenter som inneholder svÊrt fÄ elementer..

I mitt eksempel er det enkelt Ä finne en god hash-funksjon. Men dette er et enkelt eksempel; det er vanskeligere Ä finne en god hash-funksjon nÄr nÞkkelen er:

  • en streng (for eksempel et etternavn)
  • to strenger (for eksempel et etternavn og et fornavn)
  • to strenger og en dato (for eksempel et etternavn, et fornavn og fĂždselsdato)
  • 


Med en god hash-funksjon finner du i en hash-tabell i O(1).

Array vs. hash-tabell

Hvorfor ikke bruke array?

Hmm, godt spÞrsmÄl.

  • Hash-tabellen kan vĂŠre delvis lastet inn i minnet, mens de Ăžvrige segmentene kan vĂŠre lagret pĂ„ disken.
  • Med et array mĂ„ du bruke kontinuerlig minneplass. Hvis du laster inn en stor tabell, er det veldig vanskelig Ă„ finne tilstrekkelig kontinuerlig plass.
  • For hash-tabellen kan du velge Ăžnsket nĂžkkel (for eksempel landet og etternavnet til en person).

For mer informasjon kan du lese artikkelen om JavaHashMap, som er en effektiv implementering av hash-tabellen; du trenger ikke Ä forstÄ Java for Ä forstÄ konseptene som er presentert i denne artikkelen.

Kilde: habr.com

KjĂžp pĂ„litelig hosting for nettsteder med DDoS-beskyttelse, VPS VDS-servere đŸ”„ KjĂžp pĂ„litelig hosting for nettsteder med DDoS-beskyttelse, VPS VDS-servere | ProHoster