Databaseindeksering i en nøddeskal med B+træ og Hash i sammenligning

Folk bliver ofte sagt, at indeksering er en go-to-teknik til at behandle forespørgsler effektivt, hvis din database er stor nok. Dette indlæg er for at opsummere, hvad databaseindeks er og gense hash og B+Tree.

Indeks er en datastruktur, der organiserer registreringer for at optimere visse former for genfindingsoperationer. Vi kan oprette indeks på et felt i tabellen og derefter hente alle poster, der opfylder søgebetingelserne på search-key Mark. Uden indeks ville vores forespørgsel ende med at scanne hele indholdet i tabellen lineært for kun at hente én eller nogle få poster.

I dette indlæg vil jeg gerne opsummere ydeevnen og anvendelsen af ​​to almindelige indekseringsteknikker:Hash-indeks og B+træ

Hash-indeks

Denne teknik er meget brugt til at skabe indekser i hovedhukommelsen fordi dens hurtige genfinding fra naturens side. Den har gennemsnitlig O(1)-operationskompleksitet og O(n)-lagringskompleksitet.
I mange bøger bruger folk udtrykket bucket for at angive en lagerenhed, der gemmer en eller flere poster
Der er to ting at diskutere, når det kommer til hashing:

• Hash-funktion:knytter søgenøgler (som input) til et heltal, der repræsenterer denne nøgle i bøtten.
• Hashing-skema:hvordan man håndterer nøglekollision efter hashing.

Nogle mennesker spørger:hvorfor kollision? Findes der nogensinde en perfekt hash-funktion? Faktisk, lad os sige, at dine nøgler er et uendeligt sæt, det er umuligt at kortlægge dem i et sæt 32-bit heltal uden at have nogen kollision. Der bør være en afvejning mellem beregning og kollisionshastighed.

Der er et par hashing-skemaer, der er værd at nævne:lineær probing, chained hashing og udvidelig hashing. Opslags-/indsæt-/slet-algoritmer varierer efter hashing-skema, for eksempel kædet hashing-aftale med nøglekollisioner ved at placere elementer, der har samme hashværdi i samme bucket.

Fordele

• Hash-indeks er velegnet til lighed eller primærnøgleopslag. Forespørgsler kan drage fordel af hash-indeks for at få amortiseret O(1) opslagsomkostning. For eksempel:SELECT name, id FROM student WHERE id = '1315';

Ulemper

Hash-tabel har nogle begrænsninger:

• Rangeforespørgsler er ikke effektive. Hash-tabel er baseret på ensartet fordeling. Med andre ord har du ingen kontrol over, hvor en indekspost skal placeres.
• Lav skalerbarhed:Opslagsoperationens ydeevne kan forringes, når der er mange kollisioner, og det kræver at ændre størrelsen på hash-tabellen og derefter genhash eksisterende indeksposter.

B+Træ

Dette er en selvbalancerende trædatastruktur, der holder data i sorteret rækkefølge og tillader hurtig søgning inden for hver node, typisk ved hjælp af binær søgning.
B+Tree er en standard indeksimplementering i næsten alle relationelle databasesystemer.

B+Tree er grundlæggende et M-vejs søgetræ, der har følgende struktur:

• perfekt balance:bladknuder har altid samme højde.
• hver indre node bortset fra roden er mindst halvfuld (M/2 − 1 <=antal nøgler <=M − 1).
• hver indre node med k taster har k+1 underordnede ikke-nul.

Hver knude i træet har en række sorterede nøgleværdi-par. Nøgle-værdi-parret er konstrueret ud fra (søge-nøgleværdi, pointer) for rod- og indre noder. Bladknudeværdier kan være 2 muligheder:

• den faktiske post
• markøren til den faktiske registrering

Slå en værdi v op

• Start med rodnode
• Mens node ikke er en bladnode, gør vi:
  • Find den mindste Ki, hvor Ki>=v
  • Hvis Ki ==v:Indstil den aktuelle node til den node, der peges af Pi+1
  • Ellers skal du indstille den aktuelle node til node, der peges af Pi

Dubleret nøgler

Generelt kan søgenøgle være duplikat, for at løse dette kommer de fleste databaseimplementeringer med sammensat søgenøgle. For eksempel vil vi oprette et indeks på student_name så skal vores sammensatte søgenøgle være (elev_navn, Ap), hvor Ap er den primære nøgle i tabellen.

Fordele

Der er to hovedfunktioner, som B+tree tilbyder:

• Minimering af I/O-operationer
  • Reduceret højde:B+Tree har ret stor forgreningsfaktor (værdi mellem 50 og 2000 ofte brugt), hvilket gør træet fedt og kort. Nedenstående figur illustrerer et B+Tree med højden 2. Som vi kan se, knudepunkter er spredt ud, kræver det færre knuder at krydse ned til et blad. Omkostningerne ved at slå en enkelt værdi op er højden af ​​træet + 1 for den tilfældige adgang til bordet.
• Skalerbarhed:
  • Du har forudsigelig ydeevne for alle tilfælde, især O(log(n)). For databaser er det normalt vigtigere end at have bedre bedste eller gennemsnitlige sagsydelse.
  • Træet forbliver altid afbalanceret af dets implementering. Et B+træ med n nøgler har altid en dybde på O(log(n)). Ydelsen forringes således ikke, hvis databasen vokser sig større. Et træ med fire niveauer med en forgreningsfaktor på 500 kan gemme op til 256 TB, forudsat at en side er på 4 KB.

• B+Tree er bedst egnet til intervalforespørgsler, f.eks. "SELECT * FROM student WHERE age > 20 AND age < 22"

Konklusion

Selvom hash-indeks klarer sig bedre med hensyn til eksakt match-forespørgsler, er B+Tree uden tvivl den mest udbredte indeksstruktur i RDBMS takket være dens konsekvente ydeevne i overordnet og høj skalerbarhed.

For nylig har det log-strukturerede fusionstræ (LSM-træ) tiltrukket sig betydelig interesse som en konkurrent til B+-træet, fordi dets datastruktur kunne muliggøre en bedre udnyttelse af lagerplads. Jeg vil undersøge det nærmere og lave et indlæg om det i den nærmeste fremtid.