B PUUD andmestruktuuris: otsimine, lisamine, kustutamine Operanäidis

B-puu reeglid

Siin on olulised reeglid B_Tree loomiseks

• Kõik lehed luuakse samal tasemel.
• B-puu määrab astme arv, mida nimetatakse ka "järjekorraks" (mille määrab väline osaleja, näiteks programmeerija), 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.
• Alamsõlmede, juursõlme ja selle alamsõlmede maksimaalne arv arvutatakse järgmise valemiga:

  m – 1

  Näiteks:

  m = 4
  max keys: 4 – 1 = 3
  

• Iga sõlm, välja arvatud juur, peab sisaldama minimaalseid 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

Siin on B-Tree kasutamise põhjused

• Vähendab kettale tehtud lugemiste arvu
• B Puid saab hõlpsasti optimeerida, et kohandada nende suurust (see tähendab alamsõ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, põhimällu (või RAM-i) viimisel nimetatakse neid andmeid andmestruktuuriks.
• Suurte andmete korral nõuab kettalt ühe kirje otsimine kogu ketta lugemist; see suurendab aja ja põhimälu tarbimist tänu suurele kettale juurdepääsu sagedusele ja andmemahule.
• Sellest ülesaamiseks luuakse indeksitabelid, mis salvestavad kirjete viite kirjete plokkide alusel, milles need asuvad. See vähendab oluliselt aja- ja mälukulu.
• Kuna meil on tohutult andmeid, saame luua mitmetasandilisi indeksitabeleid.
• Mitmetasandilist indeksit saab kujundada, kasutades B-puud, et hoida andmeid isetasakaalustaval viisil sorteeritud.

Otsing Operamine

Otsinguoperatsioon on B-puu lihtsaim toiming.

Rakendatakse järgmist algoritmi:

• Olgu otsitav võti (väärtus) tähega "k".
• Alustage otsimist juurest ja liikuge rekursiivselt alla.
• Kui k on juurväärtusest väiksem, otsige vasakpoolset alampuud, kui k on juurväärtusest suurem, otsige paremat alampuud.
• 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 Tree on isetasakaalustuv puu, ei saa te sundida võtit suvalisse sõlme 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.

Nõuanne

Järgmine ei vasta sisestusalgoritmi kohta tõele: Kuna sõlm on täis, siis see jaguneb ja seejärel lisatakse uus väärtus

Ülaltoodud näites:

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

Ülaltoodud näites:

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

Ülaltoodud näites:

• Sõlmel on vähem kui max võtmeid
• 1 lisatakse 3 kõrvale, kuid kasvavas järjekorras reeglit rikutakse
• Selle parandamiseks sorteeritakse võtmed

Samamoodi saab 13 ja 2 hõlpsasti sõlme sisestada, kuna need täidavad sõlmede maksimaalsest võtmete reeglist vähem.

Ülaltoodud näites:

• Sõlmel on võtmed, mis on võrdsed maksimaalsete võtmetega.
• Võti sisestatakse sihtsõlme, kuid see rikub maksimaalsete võtmete 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 otsingutoimingutel.

Kehtib järgmine algoritm:

• Käivitage otsinguoperatsioon ja leidke sõlmedest sihtvõti
• Sihtvõtme asukoha põhjal rakendati kolm tingimust, nagu on selgitatud järgmistes jaotistes

Kui sihtvõti on lehesõlmes

• Target on lehesõlmes, rohkem kui min klahvid.
• Selle kustutamine ei riku B Tree omadusi
• Target on lehesõlmes, sellel on min võtmesõlmed
• Selle kustutamine rikub B Tree omadusi
• Target sõlm saab laenata võtit otsesest vasakust sõlmest või otsesest paremast sõlmest (vend)
• Õde-vend ütleb jah kui sellel on rohkem kui minimaalne arv võtmeid
• Võti laenatakse ülemsõlmelt, maksimaalne väärtus kantakse üle emasõlmele, ülemsõlme maksimaalne väärtus kantakse üle sihtsõlmele ja sihtväärtus eemaldatakse
• Target on lehesõlmes, kuid ühelgi õdedel-vendadel pole rohkem kui min võtmete arv
• Otsige võtit
• Ühendage õdede-vendadega ja minimaalselt vanemsõlmedega
• Võtmeid on nüüd rohkem kui min
• Sihtvõti asendatakse põhisõlme miinimumiga

Kui sihtvõti on sisemises sõlmes

• Kas valida, järjekorras eelkäija või järjekorras järglane
• Järjekorras eelkäija puhul valitakse selle vasakpoolsest alampuust maksimaalne võti
• Järjekorras järglase korral valitakse selle parempoolsest alampuust minimaalne võti
• Kui sihtvõtme järjekorra eelkäijal on rohkem kui min võtmeid, saab see sihtvõtme asendada järjestuse eelkäija max väärtusega
• Kui sihtvõtme järjekorra eelkäijal ei ole rohkem kui min võtmeid, otsige järjestuse järglase miinimumvõ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

• Asendage järjekorras eelkäija alampuu maksimaalse elemendiga
• Kui pärast kustutamist on sihtmärgil vähem kui min võtmeid, laenab sihtsõlm maksimaalse väärtuse oma õe-vennalt õe-venna vanema kaudu.
• Vanema maksimaalse väärtuse võtab sihtmärk, kuid koos õe-venna maksimaalse väärtuse sõlmedega.

Vaatame nüüd näite abil kustutamistoimingut.

Ülaltoodud diagramm näitab erinevaid kustutamistoimingu juhtumeid B-puus. See B-puu on suurusjärgus 5, mis tähendab, et alamsõlmede minimaalne arv, mis igal sõlmel võib olla, on 3 ja alamsõlmede maksimaalne arv, mis igal sõlmel võib olla, on 5. Mis tahes sõlme minimaalne ja maksimaalne võtmete arv võivad olla vastavalt 2 ja 4.

Ülaltoodud näites:

• Sihtsõlmel on kustutamiseks sihtvõti
• Sihtsõlmel on võtmeid rohkem kui minimaalselt
• Lihtsalt kustutage võti

Ülaltoodud näites:

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

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

• Sihtsõlm laenab võtme vahetult õelt-vennalt, antud juhul järjekorra eelkäijalt (vasakpoolne õde), kuna sellel ei ole järjestuses järglast (parem õde)
• Järjekorra eelkäija maksimaalne väärtus kantakse üle vanemale ja vanem edastab 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 õelt-vennalt, antud juhul järjestuse järglaselt (parem õde), kuna selle järjestuse eelkäija (vasak õde) 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 ei ole sihtsõlmel ühtegi venda, kes saaks sihtsõlmele oma võtme anda. Seetõttu on liitmine vajalik.

Vaadake sellise võtme kustutamise protseduuri:

• Ühendage sihtsõlm mis tahes selle vahetu õdede-vendadega koos vanemvõtmega
• Valitakse põhisõlme võti, mis on kahe ühendava sõlme vahel
• Kustutage liidetud sõlmest sihtvõti

kustutama Operapseudokood

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.

kokkuvõte

• B Tree on isetasakaaluv andmestruktuur andmete paremaks otsimiseks, sisestamiseks ja kettalt kustutamiseks.
• B Puu on reguleeritud määratud astmega
• B Puu võtmed ja sõlmed on järjestatud kasvavas järjekorras.
• B Tree otsinguoperatsioon on kõige lihtsam, mis algab alati juurest ja hakkab kontrollima, kas sihtvõti on sõlme väärtusest suurem või väiksem.
• B-puu sisestamise operatsioon on üsna detailne, mis esmalt leiab sihtvõtme jaoks sobiva sisestuspositsiooni, lisab selle, hindab B-puu kehtivust erinevatel juhtudel ja seejärel struktureerib B-puu sõlmed vastavalt ümber.
• B Tree kustutamisoperatsioon otsib esmalt kustutatavat sihtvõtit, kustutab selle ja hindab kehtivust mitmel juhul, näiteks sihtsõlme, õdede-vendade ja vanema võtmete miinimum- ja maksimumvõtmed.