B BOOM in gegevensstructuur: zoeken, invoegen, verwijderen Operavoorbeeld

Regels voor B-Tree

Hier volgen 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 “orde” genoemd (gespecificeerd door een externe actor, zoals een programmeur), ook wel

  m

  verder. De waarde van

  m

  hangt af van de blokgrootte op de schijf waarop de gegevens zich primair bevinden.

• De linker subboom van het knooppunt heeft lagere waarden dan de rechterkant van de subboom. Dit betekent dat de knooppunten ook oplopend van links naar rechts worden gesorteerd.
• Het maximale aantal onderliggende knooppunten, zowel een hoofdknooppunt als de onderliggende knooppunten, wordt berekend met deze formule:

  m – 1

  Bijvoorbeeld:

  m = 4
  max keys: 4 – 1 = 3
  

• Elk knooppunt, behalve de root, moet minimaal sleutels bevatten van

  [m/2]-1

  Bijvoorbeeld:

  m = 4
  min keys: 4/2-1 = 1
  

• Het maximale aantal onderliggende knooppunten dat een knooppunt kan hebben, is gelijk aan de graad ervan

  m

• Het minimale aantal kinderen dat een knooppunt kan hebben is de helft van de orde, namelijk m/2 (de plafondwaarde wordt genomen).
• Alle sleutels in een knooppunt worden in oplopende volgorde gesorteerd.

Waarom B-Tree gebruiken?

Hier volgen enkele redenen om B-Tree te gebruiken

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

Geschiedenis van B-boom

• Gegevens worden in blokken op de schijf opgeslagen. Wanneer deze gegevens in het hoofdgeheugen (of RAM) worden gebracht, wordt dit de gegevensstructuur genoemd.
• Bij grote hoeveelheden gegevens moet bij het zoeken naar één record op de schijf de hele schijf worden gelezen. Dit leidt tot meer tijd en geheugengebruik vanwege de hoge frequentie van toegang tot de schijf en de grote hoeveelheid gegevens.
• 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 de tijd- en geheugenconsumptie drastisch.
• Omdat we over enorme gegevens beschikken, kunnen we indextabellen met meerdere niveaus maken.
• Een index met meerdere niveaus kan worden ontworpen met behulp van een B-boom voor het bijhouden van gegevens.ping De gegevens worden op een zelfbalancerende manier gesorteerd.

Zoeken Operatie

De zoekopdracht is de eenvoudigste bewerking op B Tree.

Het volgende algoritme wordt toegepast:

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

Invoegen Operatie

Omdat B Tree een zelfbalancerende boom is, kunt u niet met geweld een sleutel in een willekeurig knooppunt plaatsen.

Het volgende algoritme is van toepassing:

• Voer de zoekopdracht uit en vind de juiste invoegplaats.
• Plaats de nieuwe sleutel op de juiste locatie, maar als het knooppunt al een maximaal aantal sleutels heeft:
• Het knooppunt zal, samen met een nieuw ingevoegde sleutel, zich splitsen van het middelste element.
• Het middelste element wordt het bovenliggende element 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 er een nieuwe waarde ingevoegd

In het bovenstaande voorbeeld:

• Zoek de juiste positie in het knooppunt naar de sleutel
• Steek de sleutel in het doelknooppunt en controleer op regels
• Heeft het knooppunt na het invoegen meer dan gelijk aan een minimumaantal sleutels, namelijk 1? In dit geval is dat inderdaad het geval. Controleer de volgende regel.
• Heeft het knooppunt na het invoegen meer dan het maximale aantal sleutels, namelijk 3? In dit geval is dat niet het geval. Dit betekent dat de B-boom geen enkele regel overtreedt en dat de invoeging voltooid is.

In het bovenstaande voorbeeld:

• Het knooppunt heeft het maximale aantal sleutels bereikt
• Het knooppunt zal splitsen en de middelste sleutel zal het hoofdknooppunt worden van de overige twee knooppunten.
• Bij een even aantal sleutels wordt het middelste knooppunt geselecteerd door middel van een linkse of een rechtse bias.

In het bovenstaande voorbeeld:

• Het knooppunt heeft minder dan het maximale aantal sleutels
• 1 wordt ingevoegd naast 3, maar de regel voor oplopende volgorde wordt geschonden
• Om dit op te lossen, worden de sleutels gesorteerd

Op dezelfde manier kunnen 13 en 2 eenvoudig in het knooppunt worden ingevoegd, omdat ze voldoen aan de regel voor minder dan de maximale sleutel voor de knooppunten.

In het bovenstaande voorbeeld:

• Het knooppunt heeft sleutels die gelijk zijn aan het maximale aantal sleutels.
• De sleutel is ingevoegd in het doelknooppunt, maar schendt de regel van het maximale aantal sleutels.
• Het doelknooppunt wordt gesplitst en de middelste sleutel is nu, door links te vertekenen, de ouder van de nieuwe onderliggende knooppunten.
• De nieuwe knooppunten zijn in oplopende volgorde gerangschikt.

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

Verwijdering Operatie

De verwijderbewerking kent meer regels dan de invoeg- en zoekbewerkingen.

Het volgende algoritme is van toepassing:

• Voer de zoekopdracht uit en vind de doelsleutel in de knooppunten
• Er worden 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

• Target bevindt zich in het bladknooppunt, meer dan min-toetsen.
• Het verwijderen hiervan schendt het eigendom van B Tree niet
• Target bevindt zich in het bladknooppunt en heeft min. sleutelknooppunten
• Als u dit verwijdert, schendt u het eigendom van B Tree
• Target knooppunt kan sleutel lenen van onmiddellijk linkerknooppunt of onmiddellijk rechterknooppunt (broer of zus)
• De broer of zus zal het zeggen ja als het meer dan het minimumaantal sleutels heeft
• De sleutel wordt geleend van het bovenliggende knooppunt, de maximale waarde wordt overgedragen naar een bovenliggend knooppunt, de maximale waarde van het bovenliggende knooppunt wordt overgedragen naar het doelknooppunt en de doelwaarde wordt verwijderd
• Target bevindt zich in het bladknooppunt, maar geen enkele broer of zus heeft meer dan een minimaal aantal sleutels
• Zoek naar sleutel
• Samenvoegen met broers en zussen en het minimum aan bovenliggende knooppunten
• Het totaal aantal sleutels bedraagt ​​nu meer dan min
• De doelsleutel wordt vervangen door het minimum van een bovenliggend knooppunt

Als de doelsleutel zich in een intern knooppunt bevindt

• Kies, in volgorde voorganger of in volgorde opvolger
• Als de voorganger in de verkeerde volgorde staat, wordt de maximale sleutel uit de linker subboom geselecteerd
• In het geval van een opvolger in de juiste volgorde, zal de minimumsleutel uit de rechter subboom worden geselecteerd
• Als de voorganger van de doelsleutel meer dan de min-sleutels heeft, kan hij alleen de doelsleutel vervangen door de max van de voorganger in de juiste volgorde
• Als de voorganger van de doelsleutel niet meer dan min-sleutels heeft, zoek dan naar de minimumsleutel van de opvolger in de juiste volgorde.
• Als de voorganger en de opvolger van de doelsleutel beide minder dan min-sleutels hebben, voeg dan de voorganger en de opvolger samen.

Als de doelsleutel zich in een hoofdknooppunt bevindt

• Vervangen door het maximale element van de voorgaande subboom in de juiste volgorde
• Als het doel na verwijdering minder dan min-sleutels heeft, dan zal het doelknooppunt de maximale waarde lenen van zijn broer of zus via de ouder van de broer of zus.
• De maximale waarde van de ouder wordt ingenomen door een doel, maar met de knooppunten van de maximale waarde van de broer of zus.

Laten we nu de verwijderbewerking aan de hand van een voorbeeld toelichten.

Het bovenstaande diagram toont verschillende gevallen van delete-bewerkingen in een B-Tree. Deze B-Tree is van orde 5, wat betekent dat het minimale aantal child nodes dat een node kan hebben 3 is, en het maximale aantal child nodes dat een node kan hebben 5 is. Terwijl het minimale en maximale aantal sleutels dat een node kan hebben respectievelijk 2 en 4 zijn.

In het bovenstaande voorbeeld:

• Het doelknooppunt heeft de doelsleutel die moet worden verwijderd
• Het doelknooppunt heeft meer sleutels dan de minimumsleutels
• Verwijder eenvoudigweg de sleutel

In het bovenstaande voorbeeld:

• Het doelknooppunt heeft sleutels die gelijk zijn aan de minimumsleutels en kan deze dus niet rechtstreeks verwijderen, omdat dit de voorwaarden schendt

Het volgende diagram legt uit hoe u deze sleutel kunt verwijderen:

• Het doelknooppunt zal een sleutel lenen van de directe broer of zus, in dit geval de voorganger in de juiste volgorde (linker broer of zus), omdat het geen opvolger in de juiste volgorde heeft (rechter broer of zus)
• De maximale waarde van de voorganger in volgorde wordt overgedragen naar 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 van zijn opvolger.

• Het doelknooppunt zal een sleutel lenen van de directe broer of zus, in dit geval de opvolger in de juiste volgorde (rechter broer of zus), omdat de voorganger in de juiste volgorde (linker broer of zus) sleutels heeft die gelijk zijn aan de minimumsleutels.
• De minimumwaarde van de opvolger in de juiste volgorde wordt overgedragen naar de ouder, en de ouder zal de maximale waarde overdragen aan het doelknooppunt.

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

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 en past tussen de twee samenvoegende knooppunten
• Verwijder de doelsleutel uit het samengevoegde knooppunt

Verwijdering Operatie Pseudo Code

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

uitgang:

Het grootste element wordt uit de B-Tree verwijderd.

Samenvatting

• B Tree is een zelfbalancerende datastructuur voor het beter zoeken, invoegen en verwijderen van gegevens van de schijf.
• B Tree wordt geregeld volgens de aangegeven graad
• B Boomsleutels en knooppunten zijn in oplopende volgorde gerangschikt.
• De zoekbewerking van B Tree is de eenvoudigste. Deze begint altijd bij de root en controleert of de doelsleutel groter of kleiner is dan de knooppuntwaarde.
• De invoegbewerking van B Tree is vrij gedetailleerd. Eerst wordt een geschikte invoegpositie voor de doelsleutel gevonden, deze wordt ingevoegd, de geldigheid van B Tree wordt geëvalueerd ten opzichte van verschillende gevallen en vervolgens worden de B Tree-knooppunten dienovereenkomstig herstructureerd.
• De verwijderbewerking van B Tree zoekt eerst naar de te verwijderen doelsleutel, verwijdert deze en evalueert de geldigheid op basis van verschillende gevallen, zoals de minimale en maximale sleutels van het doelknooppunt, de onderliggende knooppunten en het bovenliggende knooppunt.