B-puu tietorakenteessa: Hae, Lisää, Poista

Mikä on B-puu?

B Puu on itseään tasapainottava tietorakenne, joka perustuu tiettyyn sääntöjoukkoon tiedon hakemiseksi, lisäämiseksi ja poistamiseksi nopeammin ja muistitehokkaammin. Tämän saavuttamiseksi B-puu luodaan seuraavien sääntöjen mukaisesti.

B-puu on erityinen puutyyppi tietorakenteessa. McCreight ja Bayer esittelivät tämän menetelmän ensimmäisen kerran vuonna 1972 ja nimesivät sen korkeustasapainotetuksi m-suuntaiseksi hakupuuksi. Se auttaa säilyttämään tiedot lajiteltuina ja mahdollistaa erilaisia ​​toimintoja, kuten lisäyksen, haun ja poiston, lyhyemmässä ajassa.

B-Treen säännöt

Tässä on tärkeitä sääntöjä B-puun luomiseen:

• Kaikki lehdet luodaan samalle tasolle.
• B-puu määräytyy asteiden lukumäärän perusteella, jota kutsutaan myös "järjestykseksi" (jonka määrittää ulkoinen toimija, kuten ohjelmoija), johon viitataan nimellä 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.
• Juurisolmun ja sen lapsisolmujen sisältämien avainten enimmäismäärä lasketaan seuraavalla kaavalla: m − 1. Esimerkiksi:

  m = 4
  max keys: 4 − 1 = 3

• Jokaisen solmun, juurta lukuun ottamatta, on sisällettävä vähintään yksi avain [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ä B-puun käyttöön:

• Vähentää levylle tehtyjen lukukertojen määrää.
• B-puita voidaan helposti optimoida säätämään niiden kokoa (eli lapsisolmujen lukumää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 on kyse suurten tietolohkojen lukemisesta ja kirjoittamisesta.

B-puun historia

• Data tallennetaan levylle lohkoihin. Kun tätä dataa tuodaan keskusmuistiin (RAM), sitä kutsutaan datarakenteeksi.
• Suurilla tietomäärillä yhden tietueen etsiminen levyltä vaatii koko levyn lukemista; tämä lisää aikaa ja keskusmuistin kulutusta levyn suuren käyttötiheyden ja datakoon vuoksi.
• Tämän ratkaisemiseksi luodaan indeksitaulukoita, jotka tallentavat tietueiden tietueviitteet niiden lohkojen perusteella, joissa ne sijaitsevat. Tämä vähentää merkittävästi ajan ja muistin kulutusta.
• Koska meillä on valtavasti dataa, voimme luoda monitasoisia indeksitaulukoita.
• Monitasoinen indeksi voidaan suunnitella käyttämällä B-puuta kee-funktiolleping tiedot lajiteltuna itseään tasapainottavalla tavalla.

Haku OperaTUKSEN

Hakuoperaatio on B-puun yksinkertaisin operaatio. Seuraavaa algoritmia sovelletaan:

• Olkoon etsittävä avain (arvo) ”k”.
• Aloita haku juuresta ja kulje rekursiivisesti alaspäin.
• Jos k on pienempi kuin juuren arvo, etsitään vasemmasta alipuusta; jos k on suurempi kuin juuren arvo, etsitään oikeasta alipuusta.
• 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 itseään tasapainottava puu, avainta ei voi pakottaa lisäämään mihin tahansa solmuun. Seuraava algoritmi pätee:

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

Yllä olevassa esimerkissä:

• Etsi avainta sopivasta kohdasta solmussa.
• Aseta avain kohdesolmuun ja tarkista säännöt.
• Onko solmulla lisäyksen jälkeen enemmän tai yhtä paljon avaimia kuin vähimmäismäärä avaimia, joka on 1? Tässä tapauksessa kyllä, on. Tarkista seuraava sääntö.
• Onko solmulla lisäyksen jälkeen enemmän avaimia kuin sallittu enimmäismäärä, joka on 3? Tässä tapauksessa ei, sillä ei ole. 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 näppäimiä on parillinen määrä, keskimmäinen solmu valitaan vasemmalle tai oikealle suuntautuvalla tavalla.

Yllä olevassa esimerkissä:

• Solmulla on alle maksimimäärä avaimia.
• Numero 1 lisätään luvun 3 viereen, mutta nousevan järjestyksen sääntöä rikotaan.
• Tämän korjaamiseksi avaimet lajitellaan.

Vastaavasti 13 ja 2 voidaan helposti lisätä solmuun, koska ne täyttävät solmujen "alle maksimimäärä avaimia" -säännön.

Yllä olevassa esimerkissä:

• Solmulla on avaimet, jotka ovat yhtä suuria kuin avaimet.
• Avain lisätään 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

Poisto-operaatiolla on enemmän sääntöjä kuin lisäys- ja hakuoperaatioilla. Seuraava algoritmi pätee:

• Suorita haku ja etsi kohdeavain solmuista.
• Kohdeavaimen sijainnin perusteella sovelletaan kolmea ehtoa, kuten seuraavissa osioissa selitetään.

Jos kohdeavain on lehtisolmussa

• Target on lehtisolmussa, enemmän kuin min avaimia. Tämän poistaminen ei riko B-puun ominaisuutta.
• Target on lehtisolmussa ja sillä on min avainsolmuja. Tämän poistaminen rikkoo B-puun ominaisuutta.
• Kohdesolmu voi lainata avaimen välittömästi vasemmalla tai välittömästi oikealla olevalta solmulta (sisarussolmulta).
• 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 kohdesolmulle ja kohdearvo poistetaan.
• Target on lehtisolmussa, mutta sisarussolmuilla ei ole enempää avaimia kuin vähimmäismäärä: etsi avain, yhdistä sisarussolmuihin ja vähimmäismäärään pääsolmuja, avainten kokonaismäärä on nyt suurempi kuin vähimmäismäärä ja kohdeavain korvataan pääsolmun vähimmäisavaimen arvolla.

Jos kohdeavain on sisäisessä solmussa

• Valitse joko edeltäjä järjestyksessä tai seuraaja järjestyksessä.
• Jos edeltäjä on järjestyksessä, valitaan sen vasemmasta alipuusta suurin avain.
• Jos seuraaja on järjestyksessä, valitaan sen oikeanpuoleisesta alipuusta pienin avain.
• Vain jos kohdeavaimen järjestyksessä olevalla edeltäjällä on enemmän kuin min-avaimia, se voi korvata kohdeavaimen järjestyksessä olevan edeltäjän max-avaimella.
• Jos kohdeavaimen järjestyksessä olevalla edeltäjällä ei ole enempää kuin min-avaimia, etsi järjestyksessä olevan seuraajan minimiavain.
• 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ä olevan edeltäjän alipuun suurimmalla elementillä.
• Jos kohteessa on poiston jälkeen vähemmän kuin min-avaimia, kohdesolmu lainaa maksimiarvon sisarsolmultaan sisarsolmun yläsolmun kautta.
• Kohde ottaa pääsolmun maksimiarvon, mutta sisarsolmun maksimiarvon solmut käyttävät samaa arvoa.

Ymmärretään nyt poistotoiminto esimerkin avulla.

Yllä oleva kaavio näyttää erilaisia ​​​​tapauksia poistooperaatiosta B-puussa. Tämä B-puu on luokkaa 5, mikä tarkoittaa, että solmulla voi olla pienin mahdollinen määrä lapsisolmuja 3 ja suurin mahdollinen määrä 5. Solmulla voi olla pienin mahdollinen määrä avaimia 2 ja suurin mahdollinen määrä 4.

Yllä olevassa esimerkissä:

• Kohdesolmulla on poistettava kohdeavain.
• Kohdesolmulla on avaimia enemmän kuin vähimmäisavainten määrä.
• Poista vain avain.

Yllä olevassa esimerkissä:

• Kohdesolmulla on avaimia, jotka ovat yhtä suuret kuin vähimmäisavaimet, joten emme voi poistaa sitä suoraan, koska se rikkoo ehtoja.

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

• Kohdesolmu lainaa avaimen välittömältä sisarsolmulta, tässä tapauksessa järjestyksessä olevalta edeltäjältä (vasen sisarsolmu), koska sillä ei ole järjestyksessä olevaa seuraajaa (oikea sisarsolmu).
• Järjestyksessä olevan edeltäjän maksimiarvo siirretään pääsolmulle, ja pääsolmu siirtää maksimiarvon kohdesolmulle (katso alla oleva kaavio).

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

• Kohdesolmu lainaa avaimen välittömältä sisarsolmulta, tässä tapauksessa järjestyksessä olevalta seuraajalta (oikea sisarsolmu), koska sen järjestyksessä olevalla edeltäjällä (vasen sisarsolmu) on avaimet, jotka ovat yhtä suuret kuin vähimmäisavaimet.
• Järjestyksen seuraajan minimiarvo siirretään ylätasolle ja ylätason maksimiarvo kohdesolmuun.

Alla olevassa esimerkissä kohdesolmulla ei ole sisarsolmua, joka voisi antaa avaimensa kohdesolmulle. Siksi yhdistäminen on tarpeen. Katso tällaisen avaimen poistaminen:

• Yhdistä kohdesolmu mihin tahansa sen välittömistä sisarsolmuista pääavaimen kanssa.
• Yläsolmun avain valitaan kahden yhdistyvän solmun väliin.
• Poista kohdeavain yhdistetystä solmusta.

Poista Operation Pseudo Code

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

lähtö: Suurin elementti poistetaan B-puusta.

UKK