B PUU tietorakenteessa: Hae, Lisää, Poista Operaesimerkki

B-Treen säännöt

Tässä on tärkeitä sääntöjä B_Treen luomiseen

• Kaikki lehdet luodaan samalle tasolle.
• B-puu määräytyy asteen määrällä, jota kutsutaan myös "järjestykseksi" (ulkopuolisen toimijan, kuten ohjelmoijan, määrittelemä).

  m

  eteenpäin. Arvo

  m

  riippuu sen levyn lohkon koosta, jolla tiedot ensisijaisesti sijaitsevat.

• Solmun vasemmalla alipuulla on pienemmät arvot kuin alipuun oikealla puolella. Tämä tarkoittaa, että solmut lajitellaan myös nousevaan järjestykseen vasemmalta oikealle.
• Lapsisolmujen, juurisolmun ja sen alisolmujen enimmäismäärä lasketaan seuraavalla kaavalla:

  m – 1

  Esimerkiksi:

  m = 4
  max keys: 4 – 1 = 3
  

• Jokaisessa solmussa, paitsi juuri, on oltava vähintään avaimet

  [m/2]-1

  Esimerkiksi:

  m = 4
  min keys: 4/2-1 = 1
  

• Solmun lapsisolmujen enimmäismäärä on yhtä suuri kuin sen aste, joka on

  m

• Pienin lapsia solmulla voi olla puolet tilauksesta, joka on m/2 (kattoarvo otetaan).
• Kaikki solmun avaimet lajitellaan kasvavassa järjestyksessä.

Miksi käyttää B-Treeä

Tässä on syitä käyttää B-Tree

• Vähentää levylle tehtyjen lukujen määrää
• B Puut voidaan helposti optimoida säätämään kokoaan (eli lapsisolmujen määrää) levyn koon mukaan
• Se on erityisesti suunniteltu tekniikka suuren tietomäärän käsittelemiseen.
• Se on hyödyllinen algoritmi tietokantoihin ja tiedostojärjestelmiin.
• Hyvä valinta, kun haluat lukea ja kirjoittaa suuria tietolohkoja

B-puun historia

• Tiedot tallennetaan levylle lohkoina, tätä tietoa, kun se tuodaan päämuistiin (tai RAM-muistiin), kutsutaan tietorakenteeksi.
• Jos dataa on valtavasti, yhden tietueen etsiminen levyltä vaatii koko levyn lukemisen; tämä lisää aikaa ja päämuistin kulutusta suuren levyn käyttötaajuuden ja tietokoon vuoksi.
• Tämän ratkaisemiseksi luodaan indeksitaulukoita, jotka tallentavat tietueiden tietueviitteet niiden lohkojen perusteella. Tämä vähentää huomattavasti aikaa ja muistin kulutusta.
• Koska meillä on valtavasti dataa, voimme luoda monitasoisia indeksitaulukoita.
• Monitasoinen indeksi voidaan suunnitella käyttämällä B-puuta, jotta tiedot lajitellaan itsetasapainotteisesti.

Haku OperaTUKSEN

Hakutoiminto on B-puun yksinkertaisin toimenpide.

Käytetään seuraavaa algoritmia:

• Anna haettavan avaimen (arvon) "k".
• Aloita haku juuresta ja kulje rekursiivisesti alaspäin.
• Jos k on pienempi kuin juuriarvo, etsi vasen alipuu, jos k on suurempi kuin juuriarvo, etsi oikea alipuu.
• Jos solmulla on löydetty k, palauta solmu.
• Jos k:tä ei löydy solmusta, siirry alaspäin lapselle suuremmalla avaimella.
• Jos k:tä ei löydy puusta, palautetaan NULL.

liite OperaTUKSEN

Koska B-puu on itsetasapainottava puu, et voi pakottaa avainta mihin tahansa solmuun.

Käytetään seuraavaa algoritmia:

• Suorita hakutoiminto ja etsi sopiva lisäyspaikka.
• Aseta uusi avain oikeaan paikkaan, mutta jos solmulla on jo enimmäismäärä avaimia:
• Solmu yhdessä äskettäin lisätyn avaimen kanssa irtoaa keskimmäisestä elementistä.
• Keskimmäisestä elementistä tulee kahden muun alisolmun pääelementti.
• Solmujen on järjestettävä avaimet uudelleen nousevaan järjestykseen.

TIP	Seuraava ei pidä paikkaansa lisäysalgoritmista: Koska solmu on täynnä, se jakautuu ja sitten lisätään uusi arvo

Yllä olevassa esimerkissä:

• Etsi avainta sopivasta paikasta solmussa
• Aseta avain kohdesolmuun ja tarkista säännöt
• Onko solmulla lisäyksen jälkeen enemmän kuin yhtä suuri kuin vähimmäismäärä avaimia, joka on 1? Tässä tapauksessa kyllä. Tarkista seuraava sääntö.
• Onko solmussa lisäyksen jälkeen enemmän kuin enimmäismäärä avaimia, joka on 3? Tässä tapauksessa ei, ei. Tämä tarkoittaa, että B-puu ei riko mitään sääntöjä ja lisäys on valmis.

Yllä olevassa esimerkissä:

• Solmu on saavuttanut avainten enimmäismäärän
• Solmu jakautuu ja keskimmäisestä avaimesta tulee kahden muun solmun juurisolmu.
• Jos avaimia on parillinen määrä, keskisolmu valitaan vasemmalla tai oikealla.

Yllä olevassa esimerkissä:

• Solmulla on alle max avaimia
• 1 on lisätty numeron 3 viereen, mutta nousevan järjestyksen sääntöä rikotaan
• Tämän korjaamiseksi avaimet lajitellaan

Samoin 13 ja 2 voidaan lisätä helposti solmuun, koska ne täyttävät solmujen maksimiavainten säännön.

Yllä olevassa esimerkissä:

• Solmulla on avaimet, jotka ovat yhtä suuria kuin avaimet.
• Avain on lisätty kohdesolmuun, mutta se rikkoo avainten enimmäismäärän sääntöä.
• Kohdesolmu on jaettu, ja keskimmäinen avain vasemmalla biasilla on nyt uusien alisolmujen pää.
• Uudet solmut on järjestetty nousevaan järjestykseen.

Vastaavasti yllä olevien sääntöjen ja tapausten perusteella loput arvot voidaan lisätä helposti B-puuhun.

Poista OperaTUKSEN

Poistotoiminnolla on enemmän sääntöjä kuin lisäys- ja hakuoperaatioilla.

Käytetään seuraavaa algoritmia:

• Suorita hakutoiminto ja etsi kohdeavain solmuista
• Kohdeavaimen sijainnin perusteella sovelletaan kolmea ehtoa, kuten seuraavissa osissa selitetään

Jos kohdeavain on lehtisolmussa

• Target on lehtisolmussa, enemmän kuin min avaimia.
• Tämän poistaminen ei loukkaa B Treen omaisuutta
• Target on lehtisolmussa, siinä on min avainsolmuja
• Tämän poistaminen loukkaa B Treen omaisuutta
• Target solmu voi lainata avaimen välittömästä vasemmasta solmusta tai välittömästä oikeasta solmusta (sisarus)
• Sisarus sanoo Joo jos siinä on enemmän kuin vähimmäismäärä avaimia
• Avain lainataan pääsolmulta, maksimiarvo siirretään pääsolmulle, pääsolmun maksimiarvo siirretään kohdesolmuun ja poistetaan kohdearvo.
• Target on lehtisolmussa, mutta yhdelläkään sisaruksella ei ole vähintään vähimmäismäärää avaimia
• Etsi avainta
• Yhdistä sisarusten kanssa ja vähintään yläsolmujen kanssa
• Avainten kokonaismäärä on nyt yli min
• Kohdeavain korvataan yläsolmun vähimmäismäärällä

Jos kohdeavain on sisäisessä solmussa

• Joko valitse, järjestyksen edeltäjä tai järjestyksen seuraaja
• Järjestyksen edeltäjän tapauksessa valitaan suurin avain sen vasemmasta alipuusta
• Järjestyksen seuraajan tapauksessa valitaan vähimmäisavain sen oikeasta alipuusta
• Jos kohdeavaimen järjestyksen edeltäjässä on enemmän kuin min avaimia, vain silloin se voi korvata kohdeavaimen järjestyksen edeltäjän max.
• Jos kohdeavaimen järjestyksen edeltäjässä ei ole enempää kuin min avaimia, etsi järjestyksen seuraajan vähimmäisavain.
• Jos kohdeavaimen järjestyksen edeltäjällä ja seuraajalla on molemmilla vähemmän kuin min avaimet, yhdistä edeltäjä ja seuraaja.

Jos kohdeavain on juurisolmussa

• Korvaa järjestyksessä edeltävän alipuun enimmäiselementillä
• Jos kohteella on poistamisen jälkeen vähemmän kuin min avaimia, kohdesolmu lainaa maksimiarvon sisaruksestaan ​​sisaruksen vanhemman kautta.
• Vanhemman enimmäisarvon ottaa kohde, mutta sisaruksen enimmäisarvon solmut.

Ymmärretään nyt poistotoiminto esimerkin avulla.

Yllä oleva kaavio näyttää erilaisia ​​poistotoimintoja B-puussa. Tämä B-puu on luokkaa 5, mikä tarkoittaa, että missä tahansa solmussa voi olla vähintään 3 lapsisolmua ja suurin sallittu määrä lapsisolmuja missä tahansa solmussa on 5. Kun taas minkään solmun avainten vähimmäis- ja enimmäismäärä voi olla 2 ja 4, vastaavasti.

Yllä olevassa esimerkissä:

• Kohdesolmulla on poistettava kohdeavain
• Kohdesolmulla on avaimia enemmän kuin vähimmäisavaimia
• Poista vain avain

Yllä olevassa esimerkissä:

• Kohdesolmulla on avaimet, jotka vastaavat vähimmäisavaimia, joten sitä ei voi poistaa suoraan, koska se rikkoo ehtoja

Nyt seuraava kaavio selittää, kuinka tämä avain poistetaan:

• Kohdesolmu lainaa avaimen välittömältä sisarukselta, tässä tapauksessa järjestyksen edeltäjältä (vasen sisarus), koska sillä ei ole järjestyksessä seuraajaa (oikea sisarus)
• Järjestyksen edeltäjän maksimiarvo siirretään ylätasolle ja ylätaso siirtää maksimiarvon kohdesolmuun (katso alla oleva kaavio)

Seuraava esimerkki havainnollistaa, kuinka avain, joka tarvitsee arvon, poistetaan järjestyksen seuraajasta.

• Kohdesolmu lainaa avaimen välittömältä sisarukselta, tässä tapauksessa järjestyksen seuraajalta (oikea sisarus), koska sen järjestyksen edeltäjällä (vasemmalla sisaruksella) on avaimet samat kuin vähimmäisavaimet.
• Järjestyksen seuraajan minimiarvo siirretään ylätasolle ja ylätason maksimiarvo kohdesolmuun.

Alla olevassa esimerkissä kohdesolmulla ei ole yhtään sisarusta, joka voisi antaa avaimensa kohdesolmulle. Siksi yhdistäminen on välttämätöntä.

Katso tällaisen avaimen poistamismenettely:

• Yhdistä kohdesolmu minkä tahansa sen välittömän sisaruksen kanssa sekä pääavaimen kanssa
• Pääsolmun avain valitaan, joka on kahden yhdistävän solmun välissä
• Poista kohdeavain yhdistetystä solmusta

Poista Operapseudokoodi

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

ulostulo:

Suurin elementti poistetaan B-puusta.

Yhteenveto

• B Tree on itsetasapainottava tietorakenne, joka parantaa tietojen etsimistä, lisäämistä ja poistamista levyltä.
• B Puuta säätelee määritetyn asteen mukaan
• B Puun avaimet ja solmut on järjestetty nousevaan järjestykseen.
• B Treen hakuoperaatio on yksinkertaisin, joka alkaa aina juuresta ja alkaa tarkistaa onko kohdeavain suurempi vai pienempi kuin solmun arvo.
• B-puun lisäysoperaatio on melko yksityiskohtainen, joka ensin löytää sopivan lisäyskohdan kohdeavaimelle, lisää sen, arvioi B-puun validiteetin eri tapauksia vastaan ​​ja sitten järjestää uudelleen B-puun solmut sen mukaisesti.
• B-puun poistotoiminto etsii ensin poistettavan kohdeavaimen, poistaa sen ja arvioi kelvollisuuden useiden tapausten perusteella, kuten kohdesolmun, sisarusten ja vanhemman minimi- ja maksimiavaimet.