Databasindexering i ett nötskal med B+tree och Hash i jämförelse

Folk sägs ofta att indexering är en bra teknik för att effektivt bearbeta frågor om din databas är tillräckligt stor. Det här inlägget är till för att sammanfatta vad databasindex är och återbesöka hash och B+Tree.

Index är en datastruktur som organiserar poster för att optimera vissa typer av hämtningsoperationer. Vi kan skapa index på ett fält i tabellen och sedan hämta alla poster som uppfyller sökvillkoren på search-key fält. Utan index skulle vår fråga sluta med att linjärt skannade hela innehållet i tabellen för att bara hämta en eller några få poster.

I det här inlägget skulle jag vilja sammanfatta prestanda och användningsfall för två vanliga indexeringstekniker:Hashindex och B+träd

Hashindex

Denna teknik används ofta för att skapa index i huvudminnet eftersom dess snabba hämtning av naturen. Den har genomsnittlig O(1) operationskomplexitet och O(n) lagringskomplexitet.
I många böcker använder människor termen bucket för att beteckna en lagringsenhet som lagrar en eller flera poster
Det finns två saker att diskutera när det gäller hash:

• Hash-funktion:mappar söknycklar (som dess indata) till ett heltal som representerar den nyckeln i hinken.
• Hashingschema:hur man hanterar nyckelkollision efter hashning.

Vissa människor frågar:varför kollision? Finns det någonsin en perfekt hashfunktion? Faktum är att låt oss säga att dina nycklar är en oändlig uppsättning, det är omöjligt att mappa dem till en uppsättning 32-bitars heltal utan att ha någon kollision. Det bör finnas en avvägning mellan beräkning och kollisionshastighet.

Det finns några hash-scheman värda att nämna:linjär sondering, chained hashing och utdragbar hashing. Uppslags-/infoga/ta bort-algoritmer varierar beroende på hash-schema, till exempel, kedjad hash-hantering med nyckelkollisioner genom att placera element har samma hash-värde i samma hink.

Proffs

• Hashindex är lämpligt för likhet eller primärnyckelsökning. Frågor kan dra nytta av hashindex för att få amorterad O(1)-uppslagskostnad. Till exempel:SELECT name, id FROM student WHERE id = '1315';

Nackdelar

Hashtabellen har några begränsningar:

• Räckviddsfrågor är inte effektiva. Hashtabell är baserad på enhetlig fördelning. Du har med andra ord ingen kontroll över var en indexpost ska placeras.
• Låg skalbarhet:prestandan för uppslagsoperationen kan försämras när det finns många kollisioner och det kräver att man ändrar storlek på hashtabellen och sedan omhasha befintliga indexposter.

B+Träd

Detta är en självbalanserande träddatastruktur som håller data i sorterad ordning och möjliggör snabb sökning inom varje nod, vanligtvis med binär sökning.
B+Tree är en standardindeximplementering i nästan alla relationsdatabassystem.

B+Tree är i grunden ett M-vägs sökträd som har följande struktur:

• perfekt balans:lövnoder har alltid samma höjd.
• varje inre nod förutom roten är minst halvfull (M/2 − 1 <=antal nycklar <=M − 1).
• varje inre nod med k-tangenter har k+1 icke-null-underordnade.

Varje nod i trädet har en array av sorterade nyckel-värdepar. Nyckel-värdeparet är konstruerat från (söknyckelvärde, pekare) för rot- och inre noder. Bladnodvärden kan vara två möjligheter:

• den faktiska posten
• pekaren till den faktiska posten

Slå upp ett värde v

• Börja med rotnod
• Medan noden inte är en lövnod gör vi:
  • Hitta den minsta Ki där Ki>=v
  • Om Ki ==v:ställ in aktuell nod till noden som pekas av Pi+1
  • Annas, ställ in aktuell nod till nod som pekas av Pi

Duplicera nycklar

I allmänhet kan söknyckeln vara dubblett, för att lösa detta kommer de flesta databasimplementationer med sammansatt söknyckel. Till exempel vill vi skapa ett index på student_name då bör vår sammansatta söknyckel vara (studentnamn, Ap) där Ap är den primära nyckeln i tabellen.

Proffs

Det finns två huvudfunktioner som B+tree erbjuder:

• Minimering av I/O-operationer
  • Reducerad höjd:B+Tree har ganska stor grenfaktor (värde mellan 50 och 2000 används ofta) vilket gör trädet fett och kort. Bilden nedan illustrerar ett B+Tree med höjden 2. Som vi kan se noder är utspridda krävs det färre noder för att korsa ner till ett löv. Kostnaden för att slå upp ett enskilt värde är trädets höjd + 1 för slumpmässig tillgång till tabellen.
• Skalbarhet:
  • Du har förutsägbar prestanda för alla fall, O(log(n)) i synnerhet. För databaser är det vanligtvis viktigare än att ha bättre bästa eller genomsnittliga fallprestanda.
  • Trädet förblir alltid balanserat av dess implementering. Ett B+Träd med n nycklar har alltid djupet O(log(n)). Prestandan kommer alltså inte att försämras om databasen växer sig större. Ett träd på fyra nivåer med en förgreningsfaktor på 500 kan lagra upp till 256 TB förutsatt att en sida är 4 KB.

• B+Tree är mest lämpad för intervallfrågor, till exempel "SELECT * FROM student WHERE age > 20 AND age < 22"

Slutsats

Även om hashindex presterar bättre när det gäller exakta matchningsfrågor, är B+Tree utan tvekan den mest använda indexstrukturen i RDBMS tack vare dess konsekventa prestanda i övergripande och hög skalbarhet.

Nyligen har det log-strukturerade sammanslagningsträdet (LSM-trädet) väckt stort intresse som en utmanare till B+-trädet, eftersom dess datastruktur skulle kunna möjliggöra bättre lagringsutrymmeseffektivitet. Jag ska undersöka det vidare och göra ett inlägg om det inom en snar framtid.