B+ TREE: Hae, lisää ja poista OperaTIONS
Sarah Chen
⚡ Älykäs yhteenveto
B+ Tree on monitasoinen dynaaminen indeksi, joka tallentaa dataosoittimia vain linkitettyihin lehtisolmuihin, mikä tekee hauista tarkkoja ja nopeita. Se kattaa B+ Tree -säännöt, miten se eroaa B-puusta sekä haku-, lisäys- ja poistotoiminnot.
Mikä on B+-puu?
A B+ puu käytetään ensisijaisesti dynaamisen indeksoinnin toteuttamiseen useilla tasoilla. B-puuhun verrattuna B+-puu tallentaa dataosoittimet vain puun lehtisolmuihin, mikä tekee hakuprosessista tarkemman ja nopeamman.
B+ Treen säännöt
Tässä ovat B+ -puun keskeiset säännöt.
- Lehtiä käytetään tietojen tallentamiseen.
- Tietueet tallennetaan puun sisäisiin solmuihin.
- Jos kohdeavaimen arvo on pienempi kuin sisäisen solmun arvo, seurataan sen vasemmalla puolella olevaa osoitinta.
- Jos kohdeavaimen arvo on suurempi tai yhtä suuri kuin sisäisen solmun arvo, seurataan sen oikealla puolella olevaa osoitinta.
- Juurella on vähintään kaksi lasta.
Miksi käyttää B+ Treeä
Tässä on syitä B+ Treen käyttöön:
- Avaimia käytetään ensisijaisesti haun helpottamiseen ohjaamalla oikealle lehdelle.
- B+-puu käyttää "täyttökerrointa" puun kasvun ja pienenemisen hallintaan.
- B+-puissa lukuisia avaimia voidaan helposti sijoittaa muistisivulle, koska niissä ei ole sisäsolmuihin liittyviä tietoja. Siksi se käyttää nopeasti lehtisolmussa olevia puutietoja.
- Kattava ja täysi skannaus kaikista elementeistä vaatii vain yhden lineaarisen läpikäynnin, koska B+-puun kaikki lehtisolmut ovat linkitetty toisiinsa.
B+ Tree vs. B Tree
Tässä ovat tärkeimmät erot B+-puun ja B-puun välillä.
| B+ puu | B Puu |
|---|---|
| Hakunäppäimiä voidaan toistaa. | Hakuavaimet eivät voi olla redundantteja. |
| Tiedot tallennetaan vain lehtien solmuihin. | Sekä lehtisolmut että sisäiset solmut voivat tallentaa dataa. |
| Lehtisolmuun tallennetut tiedot tekevät hausta tarkempaa ja nopeampaa. | Haku on hidasta lehti- ja sisäsolmuihin tallennetun datan vuoksi. |
| Poisto ei ole vaikeaa, koska elementti poistetaan vain lehtisolmusta. | Elementtien poistaminen on monimutkainen ja aikaa vievä prosessi. |
| Linkitetty lehtisolmut tekevät hausta tehokkaan ja nopean. | Et voi linkittää lehtisolmuja. |
Haku OperaTUKSEN
B+-puussa haku on yksi helpoimmista menetelmistä suorittaa ja antaa 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."
lähtö: 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 lehden vanhempi linkitetään tarkasti pienimpään avainarvoon ja uuteen sijaintiin puussa.
- Jaa emosolmu useisiin paikkoihin siltä varalta, että se saadaan täysin hyödynnettyä.
- Nyt parempien tulosten saavuttamiseksi keskimmäinen avain liitetään kyseisen lehden ylimmän tason solmuun.
- Jatka yllä olevissa vaiheissa selitetyn prosessin iterointia, kunnes huipputason solmua ei löydy.
liite Operaalgoritmi
1. If 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.
lähtö: Algoritmi määrittää elementin ja lisää sen onnistuneesti vaadittuun lehtisolmuun.
Yllä oleva B+ Tree -esimerkki on selitetty seuraavissa vaiheissa:
- Ensinnäkin meillä on kolme solmua, ja kolme ensimmäistä elementtiä, jotka ovat 1, 4 ja 6, lisätään sopiviin paikkoihin solmuissa.
- Seuraava arvo datasarjassa on 12, joka on lisättävä puuhun.
- Tämän saavuttamiseksi jaa solmu ja lisää siihen osoitinelementtinä luku 6.
- Nyt luodaan puun oikea hierarkia ja kee säätää jäljellä olevia data-arvoja vastaavasti.ping pidä mielessä oikealla puolella olevien avain-arvo-solmujen sovellettavat yhtä suuri kuin tai suurempi kuin -arvojen säännöt.
Poista OperaTUKSEN
B+-puun poistomenettelyn monimutkaisuus ylittää lisäys- ja hakutoiminnon.
Seuraavaa algoritmia voidaan soveltaa poistettaessa elementtiä B+-puusta:
- Ensin meidän on löydettävä puusta lehtimerkintä, joka sisältää avaimen ja osoittimen, ja sitten poistettava lehtimerkintä puusta, jos lehti täyttää tietueen poiston tarkat ehdot.
- Jos lehtisolmu täyttää vain puoliksi täyttymisen vaatimuksen, operaatio on suoritettu loppuun; muussa tapauksessa lehtisolmulla on vähimmäismäärä merkintöjä eikä sitä voida poistaa.
- Muut linkitetyt solmut oikealla ja vasemmalla voivat tyhjentää mitä tahansa merkintöjä ja siirtää ne sitten lehteen. Jos näitä kriteerejä ei täytetä, niiden tulisi yhdistää lehtisolmu ja siihen linkitetty solmu puuhierarkiassa.
- Kun lehtisolmu yhdistetään sen oikealla tai vasemmalla puolella oleviin naapureihin, ylimmän tason solmuun osoittavien lehtisolmun tai linkitetyn naapurin arvojen merkinnät poistetaan.
Yllä oleva esimerkki havainnollistaa menettelyä tietyn kertaluvun elementin poistamiseksi B+-puusta.
- Ensinnäkin poistettavan elementin tarkat sijainnit tunnistetaan puussa.
- Tässä poistettava elementti voidaan tunnistaa tarkasti vain lehtitasolla eikä indeksin sijoittelun perusteella. Näin ollen elementti voidaan poistaa vaikuttamatta poistosääntöihin, jotka ovat minimi-avaimen arvo.
- Yllä olevassa esimerkissä meidän on poistettava 31 puusta.
- Meidän täytyy löytää luvun 31 esiintymät hakemistosta ja lehdestä.
- Näemme, että 31 on käytettävissä sekä indeksi- että lehtisolmun tasolla. Siksi poistamme sen molemmista instansseista.
- Mutta meidän on täytettävä lukuun 42 osoittava indeksi. Tarkastelemme nyt oikeaa alle 25-vuotiasta lasta ja otamme pienimmän arvon ja sijoitamme sen indeksiksi. Koska 42 on ainoa läsnä oleva arvo, siitä tulee indeksi.
Poista Operaalgoritmi
1) Start at the root and go up to the 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
lähtö: Avain ”K” poistetaan ja avaimet lainataan sisarussolmuilta n:n ja sen yläsolmujen arvojen säätämiseksi tarvittaessa.
