B BOOM in gegevensstructuur: voorbeeld van zoek-, invoeg- en verwijderbewerking

Wat is een B-boom?

B Boom is een zelfbalancerende datastructuur gebaseerd op een specifieke set regels voor het zoeken, invoegen en verwijderen van de gegevens op een snellere en geheugenefficiënte manier. Om dit te bereiken, volgt het volgendewing regels worden gevolgd om een ​​B-boom te creëren.

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 gegevens gesorteerd te bewaren en verschillende bewerkingen, zoals invoegen, zoeken en verwijderen, in minder tijd mogelijk te maken.

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 voornamelijk 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
    

Regels voor B-Tree

  • 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.
  • In het geval van grote hoeveelheden gegevens vereist het zoeken naar één record op de schijf dat de hele schijf wordt 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 de tijd- en geheugenconsumptie drastisch.
  • Omdat we over enorme gegevens beschikken, kunnen we indextabellen met meerdere niveaus maken.
  • Index op meerdere niveaus kan worden ontworpen met behulp van B Tree om de gegevens op een zelfbalancerende manier gesorteerd te houden.

Zoekbewerking

De zoekbewerking is de eenvoudigste handeling op B Tree.

De following algoritme wordt toegepast:

  • Laat de sleutel (de waarde) die moet worden gezocht met “k”.
  • Begin met zoeken vanaf de wortel en ga 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.

Bewerking invoegen

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

De following algoritme is van toepassing:

  • Voer de zoekbewerking uit en vind de juiste plaats van invoeging.
  • 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 De following is niet waar over het invoegalgoritme:

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

Bewerking invoegen

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.

Bewerking invoegen

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.

Bewerking invoegen

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.

Bewerking invoegen

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.

Bewerking invoegen

Bewerking verwijderen

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

De following algoritme is van toepassing:

  • Voer de zoekbewerking uit en zoek de doelsleutel in de knooppunten
  • Er waren drie voorwaarden van toepassing op basis van de locatie van de doelsleutel, zoals uitgelegd in het volgendewing secties

Als de doelsleutel zich in het bladknooppunt bevindt

  • Het doel bevindt zich in het bladknooppunt, meer dan min-sleutels.
  • Het verwijderen hiervan schendt het eigendom van B Tree niet
  • Het doel bevindt zich in het bladknooppunt en heeft min. sleutelknooppunten
  • Als u dit verwijdert, schendt u het eigendom van B Tree
  • Doelknooppunt 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
  • Het doel 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 begrijpen met een voorbeeld.

Bewerking verwijderen

Het bovenstaande diagram toont verschillende gevallen van verwijderbewerkingen 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 maximale aantal onderliggende knooppunten dat elk knooppunt kan hebben is 5. Terwijl het minimum en maximum aantal sleutels dat elk knooppunt kan hebben kan hebben zijn respectievelijk 2 en 4.

Bewerking verwijderen

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

Bewerking verwijderen

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

Nu het volgendewing diagram legt uit hoe u deze sleutel verwijdert:

Bewerking 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)

De following Het voorbeeld illustreert hoe u een sleutel verwijdert die een waarde nodig heeft van zijn opvolger in de juiste volgorde.

Bewerking verwijderen

  • 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:

Bewerking verwijderen

  • 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

Bewerking pseudocode verwijderen

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.

Samengevat

  • 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, die altijd begint vanaf 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 in verschillende gevallen, en vervolgens de B Tree-knooppunten dienovereenkomstig worden geherstructureerd.
  • De verwijderbewerking van B Tree zoekt eerst naar de doelsleutel die moet worden verwijderd, verwijdert deze en evalueert de geldigheid op basis van verschillende gevallen, zoals minimum- en maximumsleutels van het doelknooppunt, broers en zussen en ouder.