B+ TREE: Etsi, lisää ja poista Operaesimerkki

Mikä on B+-puu?

A B+ puu käytetään ensisijaisesti dynaamisen indeksoinnin toteuttamiseen useilla tasoilla. Verrattuna B-puuhun, B+-puu tallentaa tietoosoittimet vain puun lehtisolmuihin, mikä tekee hausta tarkempaa ja nopeampaa.

B+ Treen säännöt

Tässä ovat keskeiset säännöt B+ Treelle.

• Lehtiä käytetään tietojen tallentamiseen.
• Se on tallennettu puun sisäisiin solmuihin.
• Jos kohdeavaimen arvo on pienempi kuin sisäinen solmu, seurataan sen vasemmalla puolella olevaa pistettä.
• Jos kohdeavaimen arvo on suurempi tai yhtä suuri kuin sisäinen solmu, niin sen oikealla puolella olevaa pistettä seurataan.
• Juurella on vähintään kaksi lasta.

Miksi käyttää B+ Treeä

Tässä on syitä B+ Treen käyttämiseen:

• Avaimia käytetään ensisijaisesti auttamaan hakua ohjaamalla oikealle Leafille.
• B+ Tree käyttää "täyttökerrointa" hallitakseen puun kasvua ja laskua.
• B+-puissa lukuisia avaimia voidaan helposti sijoittaa muistisivulle, koska niissä ei ole sisäsolmuihin liittyviä tietoja. Siksi se käyttää nopeasti lehtisolmussa olevia puutietoja.
• Kaikkien elementtien kattava täydellinen skannaus on puu, joka tarvitsee vain yhden lineaarisen läpimenon, koska kaikki B+-puun lehtisolmut on linkitetty toisiinsa.

B+ Tree vs. B Tree

Tässä ovat tärkeimmät erot B+-puun ja B-puun välillä

Haku OperaTUKSEN

B+-puussa haku on yksi helpoimmista suoritettavista toimenpiteistä ja saada siitä nopeita ja tarkkoja tuloksia.

Seuraava hakualgoritmi on käytettävissä:

• Löytääksesi vaaditun tietueen, sinun on suoritettava binaarinen haku puussa olevissa tietueissa.
• Jos hakuavaimella on tarkka vastaavuus, vastaava tietue palautetaan käyttäjälle.
• Jos tarkkaa avainta ei löydy haun perusteella ylä-, nyky- tai lehtisolmusta, käyttäjälle näytetään "ei löydy -viesti".
• Hakuprosessi voidaan suorittaa uudelleen parempien ja tarkempien tulosten saamiseksi.

Haku Operaalgoritmi

 1. Call the binary search method on the records in the B+ Tree.
 2. If the search parameters match the exact key
            The accurate result is returned and displayed to the user
          Else, if the node being searched is the current and the exact key is not found by the algorithm
            Display the statement "Recordset cannot be found."

ulostulo:

Vastaava tietue, joka on asetettu täsmälleen avaimeen, näytetään käyttäjälle; muussa tapauksessa epäonnistunut yritys näytetään käyttäjälle.

liite OperaTUKSEN

Seuraavaa algoritmia voidaan soveltaa lisäysoperaatioon:

• 50 prosenttia solmujen elementeistä siirretään uudelle lehdelle varastointia varten.
• Uuden Leafin emo on linkitetty tarkasti vähimmäisavaimen arvoon ja uuteen paikkaan Puussa.
• Jaa emosolmu useisiin paikkoihin siltä varalta, että se saadaan täysin hyödynnettyä.
• Nyt parempien tulosten saavuttamiseksi keskinäppäin on liitetty kyseisen Leafin ylimmän tason solmuun.
• Jatka yllä olevissa vaiheissa selitetyn prosessin iterointia, kunnes huipputason solmua ei löydy.

liite Operaalgoritmi

1.	Even inserting at-least 1 entry into the leaf container does not make it full then add the record  
     2. Else, divide the node into more locations to fit more records.
      a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the tree
      b. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.
      c. Divide the top-level node if it gets full of keys and addresses.
          i. Similarly,  insert a key in the center of the top-level node in the hierarchy of the Tree.
     d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore. 

3) Build a new top-level root node of 1 Key and 2 indicators.  

ulostulo:

Algoritmi määrittää elementin ja lisää sen onnistuneesti vaadittuun lehtisolmuun.

Yllä oleva B+ Tree -esimerkki on selitetty seuraavissa vaiheissa:

• Ensinnäkin meillä on 3 solmua, ja ensimmäiset 3 elementtiä, jotka ovat 1, 4 ja 6, lisätään sopiviin paikkoihin solmuissa.
• Tietosarjan seuraava arvo on 12, joka on tehtävä osaksi puuta.
• Tämän saavuttamiseksi jaa solmu, lisää 6 osoitinelementiksi.
• Nyt luodaan puun oikeanpuoleinen hierarkia, ja loput data-arvot säädetään vastaavasti pitämällä mielessä sovellettavat säännöt, jotka ovat yhtä suuria tai suurempia kuin arvot oikealla oleviin avainarvosolmuihin nähden.

Poista OperaTUKSEN

B+-puun poistomenettelyn monimutkaisuus ylittää lisäys- ja hakutoiminnon.

Seuraavaa algoritmia voidaan soveltaa poistettaessa elementtiä B+-puusta:

• Ensinnäkin meidän on löydettävä puusta lehtimerkintä, jossa on avain ja osoitin. , poista lehtimerkintä puusta, jos lehti täyttää tarkat tietueen poistamisen ehdot.
• Siinä tapauksessa, että lehtisolmu täyttää vain tyydyttävän puolitäyteisen kertoimen, toimenpide on suoritettu; Muutoin Leaf-solmussa on vähimmäismerkintöjä, eikä sitä voi poistaa.
• Muut linkitetyt solmut oikealla ja vasemmalla voivat vapauttaa kaikki merkinnät ja siirtää ne Leafille. Jos nämä kriteerit eivät täyty, niiden tulisi yhdistää lehtisolmu ja siihen linkitetty solmu puuhierarkiassa.
• Kun lehtisolmu yhdistetään sen oikealla tai vasemmalla puolella olevien naapuriensa kanssa, ylätason solmuun osoittavan lehtisolmun tai linkitetyn naapurin arvojen merkinnät poistetaan.

Yllä oleva esimerkki havainnollistaa menettelyä, jolla elementti poistetaan tietyn järjestyksen B+-puusta.

• Ensinnäkin poistettavan elementin tarkat sijainnit tunnistetaan puussa.
• Tässä poistettava elementti voidaan tunnistaa tarkasti vain lehtitasolla, ei indeksin sijoittelussa. Näin ollen elementti voidaan poistaa vaikuttamatta poistosäännöihin, jotka ovat pelkän vähimmäisavaimen arvo.

• Yllä olevassa esimerkissä meidän on poistettava 31 puusta.
• Meidän on löydettävä 31:n esiintymät hakemistosta ja lehdestä.
• Näemme, että 31 on saatavilla sekä indeksi- että lehtisolmutasolla. Siksi poistamme sen molemmista tapauksista.
• Mutta meidän on täytettävä indeksi, joka osoittaa 42. Katsomme nyt oikeaa alle 25-vuotiasta lasta ja otamme vähimmäisarvon ja asetamme sen indeksiksi. Joten 42 on ainoa läsnä oleva arvo, siitä tulee indeksi.

Poista Operaalgoritmi

1) Start at the root and go up to leaf node containing the key K
2) Find the node n on the path from the root to the leaf node containing K
    A. If n is root, remove K
         a. if root has more than one key, done
         b. if root has only K
            i) if any of its child nodes can lend a node
               Borrow key from the child and adjust child links
            ii) Otherwise merge the children nodes. It will be a new root
         c. If n is an internal node, remove K
            i) If n has at least ceil(m/2) keys, done!
            ii) If n has less than ceil(m/2) keys,
                If a sibling can lend a key,
                Borrow key from the sibling and adjust keys in n and the parent node
                    Adjust child links
                Else
                    Merge n with its sibling
                    Adjust child links
         d. If n is a leaf node, remove K
            i) If n has at least ceil(M/2) elements, done!
                In case the smallest key is deleted, push up the next key
            ii) If n has less than ceil(m/2) elements
            If the sibling can lend a key
                Borrow key from a sibling and adjust keys in n and its parent node
            Else
                Merge n and its sibling
                Adjust keys in the parent node

ulostulo:

Avain "K" poistetaan, ja avaimet lainataan sisaruksilta n:n ja sen pääsolmujen arvojen säätämiseksi tarvittaessa.

Yhteenveto

• B+ Tree on itsetasapainottava tietorakenne Tarkkojen ja nopeampien tietojen haku-, lisäys- ja poistotoimenpiteiden suorittamiseen
• Voimme helposti hakea täydelliset tiedot tai osittaiset tiedot, koska linkitetyn puurakenteen läpikäyminen tekee siitä tehokkaan.
• B+-puurakenne kasvaa ja kutistuu tallennettujen tietueiden määrän kasvaessa/vähentyessä.
• Tietojen tallentaminen lehtisolmuihin ja sitä seuraava sisäisten solmujen haarautuminen lyhentää ilmeisesti puun korkeutta, mikä vähentää levyn syöttö- ja tulostustoimintoja ja kuluttaa lopulta paljon vähemmän tilaa tallennuslaitteissa.