Database-indexering in een notendop met B+tree en Hash in vergelijking

Er wordt vaak gezegd dat indexeren een go-to-techniek is om query's efficiënt te verwerken voor het geval uw database groot genoeg is. Dit bericht is bedoeld om samen te vatten wat de database-index is en om hash en B+Tree opnieuw te bezoeken.

Index is een gegevensstructuur die records organiseert om bepaalde soorten ophaalbewerkingen te optimaliseren. We kunnen een index maken op een veld van de tabel en vervolgens alle records ophalen die voldoen aan de zoekvoorwaarden op search-key veld. Zonder index zou onze query uiteindelijk de volledige inhoud van de tabel lineair scannen om slechts één of enkele records op te halen.

In dit bericht wil ik de prestaties en gebruiksscenario's van twee veelgebruikte indexeringstechnieken samenvatten:Hash-index en B+boom

Hash-index

Deze techniek wordt veel gebruikt voor het maken van indices in het hoofdgeheugen omdat het van nature snel wordt opgehaald. Het heeft een gemiddelde O(1)-operatiecomplexiteit en O(n)-opslagcomplexiteit.
In veel boeken gebruiken mensen de term bucket om een ​​opslageenheid aan te duiden waarin een of meer records zijn opgeslagen
Er zijn twee dingen om te bespreken als het gaat om hashen:

• Hash-functie:wijst zoeksleutels (als invoer) toe aan een geheel getal dat die sleutel in de bucket vertegenwoordigt.
• Hashschema:hoe om te gaan met sleutelbotsing na hashen.

Sommige mensen vragen:waarom botsing? Bestaat er ooit een perfecte hashfunctie? In feite, laten we zeggen dat uw sleutels een oneindige set zijn, het is onmogelijk om ze toe te wijzen aan een set van 32-bits gehele getallen zonder dat er botsingen optreden. Er moet een afweging zijn tussen berekening en botsingssnelheid.

Er zijn een paar hash-schema's die het vermelden waard zijn:lineaire sondering, geketende hashing en uitbreidbare hashing. Algoritmen voor opzoeken/invoegen/verwijderen verschillen per hash-schema. Geketende hashing gaat bijvoorbeeld om met sleutelbotsingen door elementen met dezelfde hash-waarde in dezelfde bucket te plaatsen.

Voordelen

• Hash-index is geschikt voor het opzoeken van gelijkheid of primaire sleutels. Query's kunnen profiteren van de hash-index om afgeschreven O(1)-opzoekkosten te krijgen. Bijvoorbeeld:SELECT name, id FROM student WHERE id = '1315';

Nadelen

Hash-tabel heeft enkele beperkingen:

• Bereikquery's zijn niet efficiënt. De hashtabel is gebaseerd op een uniforme verdeling. Met andere woorden, u heeft geen controle over waar een indexitem wordt geplaatst.
• Lage schaalbaarheid:de prestaties van de opzoekbewerking kunnen verslechteren wanneer er veel botsingen zijn en het vereist om de hashtabel te verkleinen en vervolgens bestaande indexitems opnieuw te hashen.

B+Boom

Dit is een zelfbalancerende boomgegevensstructuur die gegevens in gesorteerde volgorde houdt en snel zoeken binnen elk knooppunt mogelijk maakt, meestal met behulp van binair zoeken.
B+Tree is een standaard indeximplementatie in bijna alle relationele databasesystemen.

B+Tree is in feite een M-way zoekboom die de volgende structuur heeft:

• perfect in balans:bladknopen hebben altijd dezelfde hoogte.
• elke binnenste knoop behalve de wortel is minstens halfvol (M/2 − 1 <=aantal sleutels <=M − 1).
• elk binnenknooppunt met k-sleutels heeft k+1 niet-null-kinderen.

Elk knooppunt van de boom heeft een reeks gesorteerde sleutel-waardeparen. Het sleutel/waarde-paar is opgebouwd uit (zoeksleutelwaarde, aanwijzer) voor root en inner nodes. Bladknooppuntwaarden kunnen 2 mogelijkheden zijn:

• het werkelijke record
• de aanwijzer naar het werkelijke record

Zoek een waarde op v

• Begin met hoofdknooppunt
• Hoewel het knooppunt geen bladknooppunt is, doen we dat wel:
  • Zoek de kleinste Ki waar Ki>=v
  • If Ki ==v:stel huidige knoop in op de knoop die door Pi+1 wordt aangeduid
  • Anders stelt u het huidige knooppunt in op het door Pi aangewezen knooppunt

Dubbele sleutels

Over het algemeen kan de zoeksleutel duplicaat zijn, om dit op te lossen, komen de meeste database-implementaties met een samengestelde zoeksleutel. We willen bijvoorbeeld een index maken op student_name dan zou onze samengestelde zoeksleutel (student_name, Ap) moeten zijn, waarbij Ap de primaire sleutel van de tabel is.

Voordelen

Er zijn twee belangrijke functies die B+tree biedt:

• I/O-bewerkingen minimaliseren
  • Gereduceerde hoogte:B+Tree heeft een vrij grote vertakkingsfactor (waarde tussen 50 en 2000 vaak gebruikt) waardoor de boom dik en kort is. De onderstaande afbeelding illustreert een B+Tree met een hoogte van 2. Zoals we kunnen zien, zijn knooppunten uitgespreid, er zijn minder knooppunten nodig om naar een blad te gaan. De kosten van het opzoeken van een enkele waarde zijn de hoogte van de boom + 1 voor de willekeurige toegang tot de tabel.
• Schaalbaarheid:
  • Je hebt voorspelbare prestaties voor alle gevallen, O(log(n)) in het bijzonder. Voor databases is het meestal belangrijker dan betere beste of gemiddelde caseprestaties.
  • De boom blijft altijd in evenwicht door zijn implementatie. Een B+Tree met n sleutels heeft altijd een diepte van O(log(n)). De prestaties zullen dus niet afnemen als de database groter wordt. Een boomstructuur met vier niveaus met een vertakkingsfactor van 500 kan tot 256 TB opslaan, op voorwaarde dat een pagina 4 KB groot is.

• B+Tree is het meest geschikt voor bereikquery's, bijvoorbeeld "SELECT * FROM student WHERE age > 20 AND age < 22"

Conclusie

Hoewel de hash-index beter presteert in termen van exacte match-query's, is B+Tree misschien wel de meest gebruikte indexstructuur in RDBMS dankzij de consistente prestaties in algemene en hoge schaalbaarheid.

Onlangs heeft de log-gestructureerde merge tree (LSM-tree) veel belangstelling gewekt als concurrent voor B+-tree, omdat de datastructuur een efficiënter gebruik van opslagruimte mogelijk zou kunnen maken. Ik zal het verder onderzoeken en er in de nabije toekomst een bericht over plaatsen.