B-puu andmestruktuuris: otsing, lisamine, kustutamine

Mis on B-puu?

B puu on isetasakaalustuv andmestruktuur, mis põhineb kindlal reeglite komplektil andmete kiiremaks ja mälusäästlikumaks otsimiseks, sisestamiseks ja kustutamiseks. Selle saavutamiseks järgitakse B-puu loomiseks järgmisi reegleid.

B-puu on andmestruktuuris spetsiaalne puutüüp. Selle meetodi tutvustasid esmakordselt McCreight ja Bayer 1972. aastal, nimetades selle kõrguselt tasakaalustatud m-suunaliseks otsingupuuks. See aitab säilitada andmeid sorteeritult ja võimaldab lühema ajaga teha mitmesuguseid toiminguid, nagu sisestamine, otsimine ja kustutamine.

B-puu reeglid

B-puu loomise olulised reeglid on järgmised:

• Kõik lehed luuakse samal tasemel.
• B-puu määratakse astmete arvu järgi, mida nimetatakse ka "järjekorraks" (mille määrab väline tegija, näiteks programmeerija), millele viidatakse kui m edasi. Väärtus m sõltub ploki suurusest kettal, millel andmed peamiselt asuvad.
• Sõlme vasakpoolsel alampuul on väiksemad väärtused kui alampuu paremal poolel. See tähendab, et sõlmed sorteeritakse ka kasvavas järjekorras vasakult paremale.
• Juursõlme ja selle tütarsõlmede maksimaalne võtmete arv arvutatakse järgmise valemi abil: m − 1. Näiteks:

  m = 4
  max keys: 4 − 1 = 3

• Iga sõlm, välja arvatud juur, peab sisaldama minimaalset arvu võtmeid [m/2] − 1. Näiteks:

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

• Maksimaalne alamsõlmede arv, mis sõlmel võib olla, on võrdne selle astmega, mis on m.
• Minimaalsed lapsed, mis sõlmel võivad olla, on pool järjekorrast, mis on m/2 (võetakse ülemmäära).
• Kõik sõlme võtmed sorteeritakse kasvavas järjekorras.

Miks kasutada B-puud

B-puu kasutamise põhjused on järgmised:

• Vähendab kettale tehtud lugemiste arvu.
• B-puid saab hõlpsalt optimeerida, et kohandada nende suurust (st lapsesõlmede arvu) vastavalt ketta suurusele.
• See on spetsiaalselt loodud tehnika suure andmehulga käsitlemiseks.
• See on andmebaaside ja failisüsteemide jaoks kasulik algoritm.
• Hea valik suurte andmeplokkide lugemiseks ja kirjutamiseks.

B-puu ajalugu

• Andmed salvestatakse kettale plokkidena. Kui need andmed tuuakse põhimällu (või muutmällu), nimetatakse neid andmestruktuuriks.
• Suurte andmemahtude korral nõuab ühe kirje otsimine kettalt kogu ketta lugemist; see suurendab aega ja põhimälu tarbimist kettale juurdepääsu suure sageduse ja andmete suuruse tõttu.
• Selle probleemi lahendamiseks luuakse indekstabelid, mis salvestavad kirjete viited vastavalt plokkidele, milles need asuvad. See vähendab drastiliselt aja- ja mälutarbimist.
• Kuna meil on tohutult andmeid, saame luua mitmetasandilisi indeksitabeleid.
• Mitmetasandilise indeksi saab kujundada B-puu abil kee jaoksping andmed on sorteeritud isetasakaalustuval viisil.

Otsing Operamine

Otsinguoperatsioon on B-puu lihtsaim operatsioon. Rakendatakse järgmist algoritmi:

• Olgu otsitav võti (väärtus) „k“.
• Alustage otsimist juurest ja liikuge rekursiivselt alla.
• Kui k on väiksem kui juurväärtus, otsitakse vasakpoolsest alampuust; kui k on suurem kui juurväärtus, otsitakse paremast alampuust.
• Kui sõlmel on leitud k, tagastage sõlm lihtsalt.
• Kui k-d sõlmes ei leidu, liikuge suurema võtmega alla lapse juurde.
• Kui puust k ei leia, tagastame NULL.

Sisesta Operamine

Kuna B-puu on isetasakaalustuv puu, ei saa võtit suvalisse sõlme sundida sisestama. Kehtib järgmine algoritm:

• Käivitage otsinguoperatsioon ja leidke sobiv sisestuskoht.
• Sisestage uus võti õigesse kohta, kuid kui sõlmel on juba maksimaalne arv võtmeid:
• Sõlm koos äsja sisestatud võtmega eraldatakse keskmisest elemendist.
• Keskmisest elemendist saab ülejäänud kahe alamsõlme vanem.
• Sõlmed peavad võtmed ümber paigutama kasvavas järjekorras.

Ülaltoodud näites:

• Otsi võtme jaoks sobivat positsiooni sõlmes.
• Sisesta võti sihtsõlme ja kontrolli reegleid.
• Kas pärast sisestamist on sõlmel rohkem või võrdne minimaalse võtmete arvuga, mis on 1? Sel juhul jah, on. Kontrollige järgmist reeglit.
• Kas sõlmel on pärast sisestamist rohkem võtmeid kui maksimaalne lubatud arv, mis on 3? Antud juhul ei, sel juhul ei ole. See tähendab, et B-puu ei riku ühtegi reeglit ja sisestamine on lõppenud.

Ülaltoodud näites:

• Sõlm on saavutanud maksimaalse võtmete arvu.
• Sõlm jaguneb ja keskmisest võtmest saab kahe ülejäänud sõlme juursõlm.
• Paarisarvu klahvide korral valitakse keskmine sõlm vasakpoolse või parempoolse nihke abil.

Ülaltoodud näites:

• Sõlmel on vähem kui maksimaalne arv võtmeid.
• Number 1 lisatakse arvu 3 kõrvale, aga kasvava järjekorra reegel on rikutud.
• Selle parandamiseks sorteeritakse võtmed.

Samamoodi saab sõlme hõlpsalt lisada numbreid 13 ja 2, kuna need vastavad sõlmede reeglile „võtmeid on vähem kui maksimaalne arv“.

Ülaltoodud näites:

• Sõlmel on võtmed, mis on võrdsed maksimaalsete võtmetega.
• Võti sisestatakse sihtsõlme, kuid see rikub maksimaalse võtmete arvu reeglit.
• Sihtsõlm on poolitatud ja vasakpoolse nihkega keskmine võti on nüüd uute alamsõlmede vanem.
• Uued sõlmed on järjestatud kasvavas järjekorras.

Samamoodi saab ülaltoodud reeglite ja juhtumite põhjal ülejäänud väärtused hõlpsasti B-puusse sisestada.

kustutama Operamine

Kustutamistoimingul on rohkem reegleid kui lisamis- ja otsingutoimingul. Kehtib järgmine algoritm:

• Käivitage otsinguoperatsioon ja leidke sõlmedest sihtvõti.
• Sihtvõtme asukoha põhjal rakendatakse kolme tingimust, nagu on selgitatud järgmistes osades.

Kui sihtvõti on lehesõlmes

• Target on lehesõlmes, rohkem kui min võtmeid. Selle kustutamine ei riku B-puu omadust.
• Target asub lehesõlmes ja sellel on min võtmesõlmi. Selle kustutamine rikub B-puu omadust.
• Sihtsõlm saab laenata võtme vahetult vasakult või vahetult paremalt sõlmelt (õde-vend).
• Õde-vend ütleb jah kui sellel on rohkem kui minimaalne võtmete arv.
• Võti laenatakse vanemsõlmelt, maksimaalne väärtus kantakse vanemsõlmele, vanemsõlme maksimaalne väärtus kantakse sihtsõlmele ja sihtväärtus eemaldatakse.
• Target on lehesõlmes, kuid ühelgi õde-vennal pole rohkem võtmeid kui minimaalne arv: otsige võtit, ühendage õde-vendade ja minimaalse arvu vanemsõlmedega, võtmete koguarv on nüüd suurem kui minimaalne arv ja sihtvõti asendatakse vanemsõlme minimaalse arvuga.

Kui sihtvõti on sisemises sõlmes

• Valige kas järjekorras eelkäija või järjekorras järeltulija.
• Järjekorras eelkäija puhul valitakse selle vasakpoolsest alampuust maksimaalne võti.
• Järjekorras oleva järglase puhul valitakse selle parempoolsest alampuust minimaalne võti.
• Ainult siis, kui sihtvõtme järjekorras oleval eelkäijal on rohkem kui min-võtmeid, saab see sihtvõtme järjekorras oleva eelkäija maksimaalse võtmega asendada.
• Kui sihtvõtme järjekorras oleva eelkäija võtmete arv ei ole suurem kui min, otsige järjekorras oleva järeltulija minimaalset võtit.
• Kui sihtvõtme järjekorras eelkäijal ja järglasel on mõlemal vähem kui min võti, ühendage eelkäija ja järglane.

Kui sihtvõti on juursõlmes

• Asenda eelkäija alampuu järjekorras oleva maksimaalse elemendiga.
• Kui pärast kustutamist on sihtmärgil vähem kui miinimumvõtmeid, laenab sihtsõlm oma õelt-vennalt õe-venna ülemsõlme kaudu maksimaalse väärtuse.
• Siht võtab vanema maksimaalse väärtuse, kuid õe-venna maksimaalse väärtuse sõlmedega.

Vaatame nüüd näite abil kustutamistoimingut.

Ülaltoodud diagramm näitab B-puu kustutusoperatsiooni erinevaid juhtumeid. See B-puu on 5. järku, mis tähendab, et sõlme minimaalne tütarsõlmede arv on 3 ja maksimaalne tütarsõlmede arv on 5. Sõlme minimaalne ja maksimaalne võtmete arv on vastavalt 2 ja 4.

Ülaltoodud näites:

• Sihtsõlmel on kustutatav sihtvõti.
• Sihtsõlmel on võtmeid rohkem kui minimaalne võtmete arv.
• Kustuta võti lihtsalt ära.

Ülaltoodud näites:

• Sihtsõlmel on võtmed, mis on võrdsed minimaalsete võtmetega, seega ei saa me seda otse kustutada, kuna see rikub tingimusi.

Nüüd selgitab järgmine diagramm, kuidas seda võtit kustutada:

• Sihtsõlm laenab võtme vahetult oma õelt-vennalt, antud juhul järjekorras olevalt eelkäijalt (vasakpoolne vend-vend), kuna sellel pole järjekorras olevat järeltulijat (parempoolne vend-vend).
• Järjekorras eelkäija maksimaalne väärtus kantakse ülemale ja vanem kannab maksimaalse väärtuse sihtsõlmele (vt allolevat diagrammi).

Järgmine näide illustreerib, kuidas kustutada võtit, mis vajab väärtust selle järjestuse järglasest.

• Sihtsõlm laenab võtme vahetult temalt õelt-vennalt, antud juhul järjekorras olevalt järglaselt (parempoolne järglane), kuna selle järjekorras oleva eelkäija (vasakpoolne järglane) võtmed on võrdsed minimaalsete võtmetega.
• Järjekorras järglase minimaalne väärtus kantakse üle vanemale ja ülem edastab maksimaalse väärtuse sihtsõlmele.

Allolevas näites pole sihtsõlmel ühtegi õde-venda, kes saaks oma võtme sihtsõlmele anda. Seetõttu on vaja ühendamist. Vaadake sellise võtme kustutamise protseduuri:

• Ühenda sihtsõlm mis tahes selle vahetu õe-vennaga koos vanemvõtmega.
• Valitakse kahe ühineva sõlme vahel asuv vanemsõlme võti.
• Kustuta ühendatud sõlmest sihtvõti.

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

Väljund: Suurim element kustutatakse B-puust.

KKK