B+ PUUD: otsige, lisage ja kustutage OperaNäide

Mis on B+ puu?

A B+ puu kasutatakse peamiselt dünaamilise indekseerimise rakendamiseks mitmel tasandil. Võrreldes B-puuga salvestab B+ puu andmeosutajad ainult puu lehtede sõlmedesse, mis muudab otsingu protsessi täpsemaks ja kiiremaks.

B+ puu reeglid

Siin on olulised reeglid B+ puu jaoks.

• Lehti kasutatakse andmekirjete salvestamiseks.
• Seda hoitakse puu sisemistes sõlmedes.
• Kui sihtvõtme väärtus on väiksem kui sisemine sõlm, siis järgitakse selle vasakpoolset punkti.
• Kui sihtvõtme väärtus on sisemisest sõlmest suurem või sellega võrdne, siis järgitakse sellest paremal asuvat punkti.
• Juurel on minimaalselt kaks last.

Miks kasutada B+ puud

Siin on B+ puu kasutamise põhjused:

• Võtmeid kasutatakse peamiselt otsingu hõlbustamiseks, suunates õigele lehele.
• B+ Tree kasutab puu suurenemise ja vähenemise juhtimiseks täitetegurit.
• B+ puude puhul saab arvukalt võtmeid hõlpsasti mälulehele paigutada, kuna neil puuduvad sisemiste sõlmedega seotud andmed. Seetõttu pääseb see kiiresti juurde lehesõlmes olevatele puuandmetele.
• Kõigi elementide põhjalik täielik skaneerimine on puu, mis vajab ainult ühte lineaarset läbimist, kuna kõik B+ puu lehtede sõlmed on omavahel seotud.

B+ puu vs. puu B

Siin on peamised erinevused B+ Tree ja B Tree vahel

Otsing Operamine

B+ Tree'is on otsing üks lihtsamaid protseduure, mida saab teha ning saada sellest kiireid ja täpseid tulemusi.

Kasutatav on järgmine otsingualgoritm:

• Vajaliku kirje leidmiseks peate käivitama käsu binaarotsing puus saadaolevatel kirjetel.
• Otsinguvõtmega täpse vaste korral tagastatakse vastav kirje kasutajale.
• Kui täpset võtit ei leidu otsinguga vanem-, voolu- või lehesõlmes, kuvatakse kasutajale teade "ei leitud".
• Paremate ja täpsemate tulemuste saamiseks saab otsinguprotsessi uuesti käivitada.

Otsing OperaAlgoritm

 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."

Väljund:

Täpse võtmega vastendatud kirje kuvatakse kasutajale; vastasel juhul näidatakse kasutajale ebaõnnestunud katset.

Sisesta Operamine

Sisestamistoimingu jaoks kehtib järgmine algoritm:

• 50 protsenti sõlmedes olevatest elementidest viiakse ladustamiseks uuele lehele.
• Uue lehe vanem on täpselt seotud minimaalse võtmeväärtusega ja uue asukohaga puus.
• Jagage emasõlm mitmeks asukohaks juhuks, kui see täielikult ära kasutatakse.
• Nüüd on paremate tulemuste saavutamiseks keskklahv seotud selle lehe tipptaseme sõlmega.
• Kuni tipptaseme sõlme ei leita, jätkake ülaltoodud sammudes kirjeldatud protsessi kordamist.

Sisesta OperaAlgoritm

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.  

Väljund:

Algoritm määrab elemendi ja sisestab selle edukalt vajalikku lehesõlme.

Ülaltoodud B+ puu näidisnäidet selgitatakse järgmiste sammudega.

• Esiteks on meil 3 sõlme ja esimesed 3 elementi, milleks on 1, 4 ja 6, lisatakse sõlmede sobivatesse kohtadesse.
• Järgmine väärtus andmeseerias on 12, mis tuleb muuta puu osaks.
• Selle saavutamiseks jagage sõlm, lisage osutielemendiks 6.
• Nüüd luuakse puu parempoolne hierarhia ja kee kohandab vastavalt ülejäänud andmeväärtusi.ping pidage meeles paremal asuvate võtme-väärtuse sõlmede suhtes kehtivaid võrdsete või suuremate väärtuste reegleid.

kustutama Operamine

Kustutusprotseduuri keerukus B+ puus ületab sisestamise ja otsingu funktsioonide keerukuse.

B+ puust elemendi kustutamisel on rakendatav järgmine algoritm:

• Esiteks peame leidma puust lehekirje, mis hoiab võtit ja kursorit. , kustutage puust lehekirje, kui leht vastab täpsetele kirje kustutamise tingimustele.
• Kui lehe sõlm vastab rahuldavale pooleldi täisoleku tegurile, on toiming lõpetatud; vastasel juhul on sõlmel Leaf minimaalsed kirjed ja seda ei saa kustutada.
• Teised lingitud sõlmed paremal ja vasakul saavad kõik kirjed vabastada ja seejärel lehele teisaldada. Kui need kriteeriumid ei ole täidetud, peaksid nad ühendama puu hierarhias lehesõlme ja sellega seotud sõlme.
• Lehesõlme ühendamisel selle parem- või vasakpoolsete naabritega kustutatakse lehesõlme või lingitud naabri väärtuste kirjed, mis osutavad tipptaseme sõlmele.

Ülaltoodud näide illustreerib protseduuri elemendi eemaldamiseks konkreetse järjestuse B+ puust.

• Esiteks tuvastatakse puus kustutatava elemendi täpsed asukohad.
• Siin saab kustutatavat elementi täpselt tuvastada ainult lehtede tasemel, mitte indeksi paigutuses. Seega saab elemendi kustutada, ilma et see mõjutaks kustutamise reegleid, mis on minimaalse võtme väärtus.

• Ülaltoodud näites peame puust kustutama 31.
• Peame leidma loendis Index ja Leaf 31 eksemplarid.
• Näeme, et 31 on saadaval nii indeksi kui ka lehesõlme tasemel. Seetõttu kustutame selle mõlemast eksemplarist.
• Kuid me peame täitma indeksi, mis osutab 42-le. Nüüd vaatame õiget alla 25-aastast last, võtame minimaalse väärtuse ja asetame selle indeksina. Seega, kui 42 on ainus olemasolev väärtus, saab sellest indeks.

kustutama OperaAlgoritm

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

Väljund:

Võti “K” kustutatakse ja võtmed laenatakse õdedelt-vendadelt väärtuste kohandamiseks n-is ja selle ülemsõlmedes, kui vaja.

kokkuvõte

• B+ Tree on isetasakaalustaja andmete struktuur andmete täpseks ja kiiremaks otsimiseks, sisestamiseks ja kustutamiseks
• Saame hõlpsasti hankida täielikke või osalisi andmeid, kuna lingitud puustruktuuri läbimine muudab selle tõhusaks.
• B+ puu struktuur kasvab ja kahaneb koos salvestatud kirjete arvu suurenemise/vähenemisega.
• Andmete salvestamine lehtede sõlmedesse ja sellele järgnev sisemiste sõlmede hargnemine lühendab ilmselt puu kõrgust, mis vähendab ketta sisend- ja väljundtoiminguid, kulutades lõppkokkuvõttes salvestusseadmetes palju vähem ruumi.