Mikä on B + puu?
B + Tree on käytetty etupäässä toteuttamiseksi dynaaminen indeksointi monilla tasoilla. Verrattuna B- puuhun, B + puu tallentaa datan osoittimet vain puun lehtisolmuihin, mikä tekee hausta tarkemman ja nopeamman.
Tässä B + Tree -oppaassa opit:
- Mikä on B + puu?
- B + Puun säännöt
- Miksi käyttää B + Puuta
- B + puu vs. B puu
- Hakutoiminto
- Lisää toiminta
- Poista toiminto
B + Puun säännöt
Tässä ovat olennaiset säännöt B + Puun suhteen.
- Lehtiä käytetään tietueiden tallentamiseen.
- Se tallentui puun sisäisiin solmuihin.
- Jos kohdeavaimen arvo on pienempi kuin sisäinen solmu, seuraa vain sen vasemmalla puolella olevaa pistettä.
- Jos kohdeavaimen arvo on suurempi tai yhtä suuri kuin sisäinen solmu, seuraa vain sen oikealla puolella olevaa pistettä.
- Juuressa on vähintään kaksi lasta.
Miksi käyttää B + Puuta
Tässä on syitä käyttää B + Puuta:
- Avainta käytetään ensisijaisesti apuna etsinnässä ohjaamalla oikeaan Leafiin.
- B + Tree käyttää "täytekerrointa" puun kasvun ja pienenemisen hallintaan.
- B + -puissa lukuisat avaimet voidaan helposti sijoittaa muistisivulle, koska niillä ei ole sisäisiin solmuihin liittyviä tietoja. Siksi se käyttää nopeasti puun tietoja, jotka ovat lehtisolmussa.
- Kaikkien elementtien kattava täydellinen skannaus on puu, joka tarvitsee vain yhden lineaarisen kulun, koska kaikki B + -puun lehtisolmut ovat yhteydessä toisiinsa.
B + puu vs. B puu
Tässä ovat tärkeimmät erot B + Puun ja B Puun välillä
| B + puu | B puu |
| Hakunäppäimet voidaan toistaa. | Hakunäppäimet eivät voi olla tarpeettomia. |
| Tiedot tallennetaan vain lehtisolmuihin. | Sekä lehtisolmut että sisäiset solmut voivat tallentaa tietoja |
| Lehtisolmuun tallennetut tiedot tekevät hausta tarkemman ja nopeamman. | Haku on hidasta johtuen Leafiin ja sisäisiin solmuihin tallennetuista tiedoista. |
| Poisto ei ole vaikeaa, koska elementti poistetaan vain lehtisolmusta. | Elementtien poistaminen on monimutkainen ja aikaa vievä prosessi. |
| Linkitetyt lehtisolmut tekevät hausta tehokkaan ja nopean. | Et voi linkittää lehtisolmuja. |
Hakutoiminto
B + Puussa haku on yksi helpoimmista toimenpiteistä suorittaa ja saada siitä nopeita ja tarkkoja tuloksia.
Seuraava hakualgoritmi on käytettävissä:
- Vaaditun tietueen löytämiseksi sinun on suoritettava binäärihaku puun käytettävissä olevista tietueista.
- Jos hakuavain on täsmälleen sama, vastaava tietue palautetaan käyttäjälle.
- Jos tarkkaa avainta ei löydy vanhemman, nykyisen tai lehtisolmun haun kautta, käyttäjälle näytetään "ei löydy viesti".
- Hakuprosessi voidaan suorittaa uudelleen parempien ja tarkempien tulosten saamiseksi.
Hakutoiminnon algoritmi
1. Call the binary search method on the records in the B+ Tree.2. If the search parameters match the exact keyThe accurate result is returned and displayed to the userElse, if the node being searched is the current and the exact key is not found by the algorithmDisplay the statement "Recordset cannot be found."
Tuotos :
Hyväksytty tietue asetettu täsmälleen avaimelle näytetään käyttäjälle; muuten epäonnistunut yritys näytetään käyttäjälle.
Lisää toiminta
Seuraava algoritmi soveltuu lisäystoimintoon:
- 50 prosenttia solmujen elementeistä siirretään uuteen lehteen varastointia varten.
- Uuden lehden vanhempi on linkitetty tarkasti avaimen vähimmäisarvoon ja uuteen sijaintiin puussa.
- Jaa vanhempi solmu useampaan sijaintiin, jos sitä käytetään kokonaan.
- Parempien tulosten saavuttamiseksi keskinäppäin liittyy kyseisen lehden ylätason solmuun.
- Kunnes ylätason solmua ei löydy, jatka yllä olevissa vaiheissa selitetyn prosessin toistamista.
Lisää käyttöalgoritmi
1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record2. 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 treeb. 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.
Tuotos :
Algoritmi määrittää elementin ja lisää sen onnistuneesti vaadittuun lehtisolmuun.
Yllä oleva esimerkki B + Tree -esimerkistä selitetään alla olevissa vaiheissa:
- Ensinnäkin, meillä on 3 solmua, ja ensimmäiset 3 elementtiä, jotka ovat 1, 4 ja 6, lisätään solmujen sopiviin paikkoihin.
- Seuraava arvosarja on 12, joka on tehtävä osaksi puuta.
- Tämän saavuttamiseksi jaa solmu, lisää 6 osoitinelementtinä.
- Nyt luodaan puun oikeanpuoleinen hierarkia ja jäljellä olevat data-arvot mukautetaan vastaavasti pitämällä mielessä sovellettavat säännöt, jotka ovat yhtä suuria tai suurempia kuin arvot oikealla olevia avainarvosolmuja vastaan.
Poista toiminto
B + Puun poistomenettelyn monimutkaisuus ylittää lisäys- ja hakutoiminnot.
Seuraava algoritmi on käytettävissä poistettaessa elementti B + -puusta:
- Ensinnäkin meidän on löydettävä puusta lehti, joka pitää avainta ja osoitinta. , poista lehtien merkintä puusta, jos lehti täyttää tietueen poistamisen tarkat ehdot.
- Jos lehtisolmu saavuttaa tyydyttävän kertoimen olla vain puoliksi täynnä, toiminto on suoritettu loppuun; muuten Leaf-solmussa on vähimmäismerkintöjä, eikä sitä voida poistaa.
- Muut linkitetyt solmut oikealla ja vasemmalla voivat vapauttaa kaikki merkinnät ja siirtää ne sitten Leafiin. Jos nämä ehdot eivät täyty, niiden tulisi yhdistää lehtisolmu ja siihen liitetty solmu puuhierarkiassa.
- Yhdistettäessä lehtisolmu sen oikealla tai vasemmalla puolella oleviin naapureihin, ylätason solmuun osoittavat lehtisolmun tai linkitetyn naapurin arvojen merkinnät poistetaan.
Yllä oleva esimerkki kuvaa menettelyä elementin poistamiseksi tietyn järjestyksen B + -puusta.
- Ensinnäkin poistettavan elementin tarkat sijainnit tunnistetaan puussa.
- Tässä poistettava elementti voidaan tunnistaa tarkasti vain lehtien tasolla eikä hakemistosijoituksessa. Siksi elementti voidaan poistaa vaikuttamatta poistosääntöihin, mikä on paljain vähimmäisavaimen arvo.
- Edellä olevassa esimerkissä meidän on poistettava 31 puusta.
- Meidän on löydettävä hakemisto 31: stä hakemistoista ja lehdistä.
- Voimme nähdä, että 31 on saatavana sekä hakemisto- että lehti-solmutasolla. Siksi poistamme sen molemmista instansseista.
- Mutta meidän on täytettävä indeksi osoittamalla 42. Tarkastelemme nyt oikeaa alle 25-vuotiasta lasta ja otamme vähimmäisarvon ja sijoitamme sen indeksiin. Joten 42 on ainoa läsnä oleva arvo, siitä tulee indeksi.
Poista käyttöalgoritmi
1) Start at the root and go up to leaf node containing the key K2) Find the node n on the path from the root to the leaf node containing KA. If n is root, remove Ka. if root has more than one key, doneb. if root has only Ki) if any of its child nodes can lend a nodeBorrow key from the child and adjust child linksii) Otherwise merge the children nodes. It will be a new rootc. If n is an internal node, remove Ki) 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 nodeAdjust child linksElseMerge n with its siblingAdjust child linksd. If n is a leaf node, remove Ki) If n has at least ceil(M/2) elements, done!In case the smallest key is deleted, push up the next keyii) If n has less than ceil(m/2) elementsIf the sibling can lend a keyBorrow key from a sibling and adjust keys in n and its parent nodeElseMerge n and its siblingAdjust keys in the parent node
Tuotos :
Avain "K" poistetaan ja avaimet lainataan sisaruksilta n: n ja sen vanhempien solmujen arvojen säätämiseksi tarvittaessa.
Yhteenveto:
- B + Tree on itsestään tasapainottava tietorakenne tarkan ja nopeamman etsinnän, lisäämisen ja poistamisen suorittamiseksi tiedoista
- Voimme helposti noutaa täydelliset tai osittaiset tiedot, koska linkitetyn puurakenteen läpi käyminen tekee siitä tehokasta.
- B + -puurakenne kasvaa ja kutistuu tallennettujen tietueiden määrän kasvaessa / vähentyessä.
- Tietojen tallentaminen lehtisolmuihin ja myöhempi sisäisten solmujen haarautuminen lyhentää ilmeisesti puun korkeutta, mikä vähentää levyn syöttö- ja tulostustoimintoja ja kuluttaa lopulta paljon vähemmän tilaa tallennuslaitteilla.