B BOOM in gegevensstructuur: bewerkingsvoorbeeld zoeken, invoegen, verwijderen

Wat is een B-boom?

B Tree is een zelfbalancerende gegevensstructuur op basis van een specifieke set regels voor het zoeken, invoegen en verwijderen van gegevens op een snellere en geheugenefficiëntere manier. Om dit te bereiken, worden de volgende regels gevolgd om een B Tree te maken.

Een B-Tree is een speciaal soort boom in een datastructuur. In 1972 werd deze methode voor het eerst geïntroduceerd door McCreight, en Bayer noemde het Height Balanced m-way Search Tree. Het helpt u om gesorteerde gegevens te bewaren en verschillende bewerkingen toe te staan, zoals invoegen, zoeken en verwijderen in minder tijd.

In deze B-Tree tutorial leer je:

Wat is een B-boom?
Waarom B-Tree gebruiken
Geschiedenis van B Tree
Zoekoperatie
Plaats operatie
Bewerking verwijderen

Regels voor B-Tree

Hier zijn belangrijke regels voor het maken van B_Tree

Alle bladeren worden op hetzelfde niveau gemaakt.
B-Tree wordt bepaald door een aantal graden, ook wel 'volgorde' genoemd (gespecificeerd door een externe actor, zoals een programmeur), ook wel 'volgorde' genoemd
```
m
```
verder. De waarde van
```
m
```
hangt af van de blokgrootte op de schijf waarop de gegevens zich primair bevinden.
De linker substructuur van het knooppunt heeft lagere waarden dan de rechterkant van de substructuur. Dit betekent dat de knooppunten ook in oplopende volgorde van links naar rechts worden gesorteerd.
Het maximale aantal onderliggende knooppunten, een hoofdknooppunt en de onderliggende knooppunten dat kan bevatten, wordt berekend met deze formule:
```
m - 1
```
Bijvoorbeeld:
```
m = 4max keys: 4 - 1 = 3
```

Elk knooppunt, behalve root, moet minimumsleutels bevatten van
```
[m/2]-1
```
Bijvoorbeeld:
```
m = 4min keys: 4/2-1 = 1
```
Het maximale aantal onderliggende knooppunten dat een knooppunt kan hebben, is gelijk aan de graad, dat wil zeggen
```
m
```
Het minimum aantal kinderen dat een knooppunt kan hebben, is de helft van de bestelling, namelijk m / 2 (de plafondwaarde wordt genomen).
Alle sleutels in een knooppunt worden in oplopende volgorde gesorteerd.

Waarom B-Tree gebruiken

Hier zijn redenen om B-Tree te gebruiken

Vermindert het aantal leesbewerkingen op de schijf
B-bomen kunnen eenvoudig worden geoptimaliseerd om de grootte (dat is het aantal onderliggende knooppunten) aan te passen aan de schijfgrootte
Het is een speciaal ontworpen techniek om een grote hoeveelheid gegevens te verwerken.
Het is een handig algoritme voor databases en bestandssystemen.
Een goede keuze als het gaat om het lezen en schrijven van grote blokken gegevens

Geschiedenis van B Tree

Gegevens worden in blokken op de schijf opgeslagen. Deze gegevens worden, wanneer ze in het hoofdgeheugen (of RAM) worden gebracht, datastructuur genoemd.
In het geval van enorme gegevens, moet voor het doorzoeken van één record op de schijf de hele schijf worden gelezen; dit verhoogt het tijd- en hoofdgeheugenverbruik vanwege de hoge schijftoegangsfrequentie en gegevensgrootte.
Om dit te ondervangen, worden indextabellen gemaakt die de recordreferentie van de records opslaan op basis van de blokken waarin ze zich bevinden. Dit vermindert drastisch het tijd- en geheugenverbruik.
Omdat we enorme gegevens hebben, kunnen we indextabellen met meerdere niveaus maken.
Een index met meerdere niveaus kan worden ontworpen door B Tree te gebruiken om de gegevens op een zelfbalancerende manier gesorteerd te houden.

Zoekoperatie

De zoekbewerking is de eenvoudigste bewerking op B Tree.

Het volgende algoritme wordt toegepast:

Laat de sleutel (de waarde) die moet worden gezocht door "k".
Begin met zoeken vanaf de wortel en ga recursief naar beneden.
Als k kleiner is dan de wortelwaarde, zoek dan naar de linker substructuur, als k groter is dan de wortelwaarde, zoek dan in de rechter substructuur.
Als het knooppunt de gevonden k heeft, retourneert u eenvoudig het knooppunt.
Als de k niet in het knooppunt wordt gevonden, ga dan met een grotere sleutel naar het kind.
Als k niet in de boom wordt gevonden, retourneren we NULL.

Plaats operatie

Aangezien B Tree een zelfbalancerende boom is, kunt u niet geforceerd een sleutel in een willekeurig knooppunt invoegen.

Het volgende algoritme is van toepassing:

Voer de zoekbewerking uit en zoek de juiste plaats van invoeging.
Plaats de nieuwe sleutel op de juiste locatie, maar als het knooppunt al een maximum aantal sleutels heeft:
Het knooppunt, samen met een nieuw ingevoegde sleutel, wordt gesplitst van het middelste element.
Het middelste element wordt de ouder voor de andere twee onderliggende knooppunten.
De knooppunten moeten de sleutels in oplopende volgorde herschikken.

TIP

Het volgende is niet waar over het invoegalgoritme:

Omdat het knooppunt vol is, wordt het gesplitst en wordt een nieuwe waarde ingevoegd

In het bovenstaande voorbeeld:

Zoek de juiste positie in het knooppunt voor de sleutel
Plaats de sleutel in het doelknooppunt en controleer op regels
Heeft het knooppunt na het invoegen meer dan gelijk aan een minimum aantal sleutels, namelijk 1? In dit geval wel. Controleer de volgende regel.
Heeft het knooppunt na het invoegen meer dan een maximum aantal sleutels, namelijk 3? Nee, in dit geval niet. Dit betekent dat de B Tree geen regels overtreedt en dat het invoegen is voltooid.

In het bovenstaande voorbeeld:

Het knooppunt heeft het maximale aantal sleutels bereikt
Het knooppunt wordt gesplitst en de middelste sleutel wordt het hoofdknooppunt van de overige twee knooppunten.
In het geval van een even aantal toetsen, wordt het middelste knooppunt geselecteerd door bias naar links of naar rechts.

In het bovenstaande voorbeeld:

Het knooppunt heeft minder dan max. Sleutels
1 wordt naast 3 ingevoegd, maar de regel van oplopende volgorde is geschonden
Om dit op te lossen, worden de sleutels gesorteerd

Evenzo kunnen 13 en 2 gemakkelijk in het knooppunt worden ingevoegd omdat ze voldoen aan de regel voor minder dan max. Sleutels voor de knooppunten.

In het bovenstaande voorbeeld:

Het knooppunt heeft sleutels die gelijk zijn aan max. Sleutels.
De sleutel wordt in het doelknooppunt ingevoegd, maar is in strijd met de regel van max. Sleutels.
Het doelknooppunt is gesplitst en de middelste toets door left bias is nu de ouder van de nieuwe kindknooppunten.
De nieuwe knooppunten zijn gerangschikt in oplopende volgorde.

Op dezelfde manier kunnen, op basis van de bovenstaande regels en gevallen, de rest van de waarden eenvoudig in de B-structuur worden ingevoegd.

Bewerking verwijderen

De verwijderbewerking heeft meer regels dan invoeg- en zoekbewerkingen.

Het volgende algoritme is van toepassing:

Voer de zoekbewerking uit en zoek de doelsleutel in de knooppunten
Drie voorwaarden toegepast op basis van de locatie van de doelsleutel, zoals uitgelegd in de volgende secties

Als de doelsleutel zich in het bladknooppunt bevindt

Het doel is in het bladknooppunt, meer dan min-toetsen.
- Als u dit verwijdert, wordt de eigendom van B Tree niet geschonden
Doel is in bladknooppunt, het heeft min-sleutelknooppunten
- Als u dit verwijdert, wordt het eigendom van B Tree geschonden
- Doelknooppunt kan sleutel lenen van direct linkerknooppunt of direct rechterknooppunt (broer of zus)
- De broer of zus zal ja zeggen als het meer dan het minimum aantal sleutels heeft
- De sleutel wordt geleend van het bovenliggende knooppunt, de maximale waarde wordt overgedragen aan een ouder, de maximale waarde van het bovenliggende knooppunt wordt overgedragen naar het doelknooppunt en verwijdert de doelwaarde
Het doel bevindt zich in het bladknooppunt, maar geen enkele broer of zus heeft meer dan een minimaal aantal sleutels
- Zoek de sleutel
- Samenvoegen met broers en zussen en het minimum aan bovenliggende knooppunten
- Het totale aantal sleutels is nu meer dan min
- De doelsleutel wordt vervangen door het minimum van een bovenliggend knooppunt

Als de doelsleutel zich in een intern knooppunt bevindt

Ofwel kiezen, in volgorde voorganger of in volgorde opvolger
In het geval dat de voorganger in de juiste volgorde is, wordt de maximale sleutel van de linker substructuur geselecteerd
In het geval van een in-order opvolger, wordt de minimumsleutel van de rechter substructuur geselecteerd
Als de in-order voorganger van de doelsleutel meer dan de min-toetsen heeft, kan deze alleen de doelsleutel vervangen door de max van de in-order voorganger
Als de in-order-voorganger van de doelsleutel niet meer dan min-toetsen heeft, zoek dan naar de minimum-key van de in-order-opvolger.
Als de in-order voorganger en opvolger van de doelsleutel beide minder dan min-toetsen hebben, voeg dan de voorganger en opvolger samen.

Als de doelsleutel zich in een hoofdknooppunt bevindt

Vervangen door het maximumelement van de in-order voorganger-substructuur
Als het doelwit na verwijdering minder dan min-sleutels heeft, zal het doelknooppunt de maximale waarde van zijn broer of zus lenen via de ouder van zijn broer of zus.
De maximale waarde van de ouder wordt ingenomen door een doelwit, maar met de knooppunten van de maximale waarde van de broer of zus.

Laten we nu de verwijderbewerking begrijpen met een voorbeeld.

Het bovenstaande diagram toont verschillende gevallen van verwijderoperaties in een B-Tree. Deze B-Tree is van orde 5, wat betekent dat het minimum aantal onderliggende knooppunten dat elk knooppunt kan hebben, 3 is, en het maximum aantal kindknooppunten dat elk knooppunt kan hebben 5. Terwijl het minimum en een maximum aantal sleutels elk knooppunt kunnen respectievelijk 2 en 4 hebben.

In het bovenstaande voorbeeld:

Het doelknooppunt heeft de doelsleutel die moet worden verwijderd
Het doelknooppunt heeft meer sleutels dan het minimum
Verwijder gewoon de sleutel

In het bovenstaande voorbeeld:

Het doelknooppunt heeft sleutels die gelijk zijn aan de minimumsleutels, dus het kan niet direct worden verwijderd omdat het de voorwaarden schendt

Nu legt het volgende diagram uit hoe u deze sleutel kunt verwijderen:

Het doelknooppunt leent een sleutel van directe broer of zus, in dit geval, in volgorde voorganger (linker broer of zus) omdat het geen in volgorde opvolger heeft (rechter broer of zus)
De maximale waarde van de in volgorde voorganger zal worden overgedragen aan de ouder, en de ouder zal de maximale waarde overbrengen naar het doelknooppunt (zie het onderstaande diagram)

Het volgende voorbeeld illustreert hoe u een sleutel verwijdert die een waarde nodig heeft uit zijn in-order opvolger.

Het doelknooppunt leent een sleutel van de directe broer of zus, in dit geval de opvolger in de juiste volgorde (rechter broer of zus) omdat zijn voorganger in de juiste volgorde (linker broer of zus) sleutels heeft die gelijk zijn aan de minimumsleutels.
De minimumwaarde van de in-order opvolger wordt overgedragen aan de ouder en de ouder draagt de maximumwaarde over naar het doelknooppunt.

In het onderstaande voorbeeld heeft het doelknooppunt geen broer of zus die zijn sleutel aan het doelknooppunt kan geven. Daarom is samenvoegen vereist.

Zie de procedure voor het verwijderen van een dergelijke sleutel:

Voeg het doelknooppunt samen met een van zijn directe broers en zussen samen met de bovenliggende sleutel
- De sleutel van het bovenliggende knooppunt wordt geselecteerd tussen de broers en zussen tussen de twee samenvoegende knooppunten
Verwijder de doelsleutel uit het samengevoegde knooppunt

Verwijder operatie pseudo-code

private int removeBiggestElement(){if (root has no child)remove and return the last elementelse {answer = subset[childCount-1].removeBiggestElement()if (subset[childCount-1].dataCount < MINIMUM)fixShort (childCount-1)return answer}}

Uitgang :

Het grootste element wordt verwijderd uit de B-Tree.

Overzicht:

B Tree is een zelfbalancerende gegevensstructuur voor het beter zoeken, invoegen en verwijderen van gegevens van de schijf.
B Tree wordt gereguleerd door de opgegeven graad
B Boomsleutels en knooppunten zijn in oplopende volgorde gerangschikt.
De zoekbewerking van B Tree is de eenvoudigste, die altijd begint bij de root en begint te controleren of de doelsleutel groter of kleiner is dan de knooppuntwaarde.
De invoegbewerking van B Tree is tamelijk gedetailleerd, waarbij eerst een geschikte invoegpositie voor de doelsleutel wordt gevonden, deze wordt ingevoegd, de geldigheid van B Tree wordt geëvalueerd ten opzichte van verschillende gevallen, en vervolgens de B Tree-knooppunten dienovereenkomstig herstructureren.
De verwijderingsoperatie van B Tree zoekt eerst naar de doelsleutel die moet worden verwijderd, verwijdert deze, evalueert de geldigheid op basis van verschillende gevallen, zoals minimum- en maximumsleutels van het doelknooppunt, broers en zussen en ouder.