B PUU andmestruktuuris: toimingu näide, otsing, sisestamine, kustutamine

Mis on B puu?

B Tree on isetasakaalustuv andmestruktuur, mis põhineb konkreetsel reeglistikul andmete otsimiseks, sisestamiseks ja kustutamiseks kiiremini ja mälusäästlikumalt. Selle saavutamiseks järgitakse B-puu loomiseks järgmisi reegleid.

B-puu on eriline puu liik andmestruktuuris. 1972. aastal võttis selle meetodi esmakordselt kasutusele McCreight ja Bayer nimetas selle kõrguse tasakaalustatud m-way otsingupuuks. See aitab teil säilitada andmeid, mis on järjestatud ja võimaldasid mitmesuguseid toiminguid, nagu sisestamine, otsimine ja kustutamine, vähem aega.

Selles B-Tree õpetuses saate teada:

• Mis on B puu?
• Miks kasutada B-Tree
• B puu ajalugu
• Otsinguoperatsioon
• Sisesta toiming
• Kustuta toiming

B-puu reeglid

Siin on olulised reeglid B_Tree loomiseks

• Kõik lehed luuakse samal tasemel.
• B-puu määrab astmete arv, mida nimetatakse ka "järjekorraks" (mille määrab väline osaleja, nagu programmeerija), millele viidatakse kui

  m

  edasi. Väärtus

  m

  sõltub selle ketta ploki suurusest, millel andmed peamiselt asuvad.
• Sõlme vasakul alampuul on väiksemad väärtused kui alampuu paremal küljel. See tähendab, et ka sõlmed on järjestatud kasvavas järjestuses vasakult paremale.
• Lapsesõlmede, juursõlme ja selle alamsõlmede maksimaalne arv võib olla arvutatud järgmise valemi abil:

  m - 1

  Näiteks:

  m = 4max keys: 4 - 1 = 3

• Kõik sõlmed, välja arvatud juur, peavad sisaldama minimaalseid võtmeid

  [m/2]-1

  Näiteks:

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

• Maksimaalne sõlmes olevate lapse sõlmede arv on võrdne tema astmega, mis on

  m

• Minimaalne laste arv, mis sõlmel võib olla, on pool järjestusest, mis on m / 2 (võetakse ülemmäär).
• Kõik sõlme võtmed on järjestatud järjestuses.

Miks kasutada B-Tree

Siin on B-puu kasutamise põhjused

• Vähendab kettal tehtud lugemiste arvu
• B Puid saab hõlpsasti optimeerida, et kohandada selle suurust (see tähendab alamsõlmede arvu) vastavalt ketta suurusele
• See on spetsiaalselt välja töötatud tehnika mahuka andmehulga töötlemiseks.
• See on kasulik andmebaaside ja failisüsteemide algoritm.
• Hea valik suurte andmeplokkide lugemise ja kirjutamise osas

B puu ajalugu

• Andmeid 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 kettale juurdepääsu sageduse ja andmete suuruse tõttu aja ja põhimälu tarbimist.
• Selle ületamiseks luuakse registritabelid, mis salvestavad kirjete kirjeviite vastavalt nende plokkidele, milles nad asuvad. See vähendab drastiliselt aega ja mälu.
• Kuna meil on tohutuid andmeid, saame luua mitmetasandilisi indeksitabeleid.
• Mitmetasandilise indeksi saab koostada, kasutades B Tree, et hoida andmeid järjestatud isetasakaalustatult.

Otsinguoperatsioon

Otsinguoperatsioon on B Tree kõige lihtsam toiming.

Rakendatakse järgmist algoritmi:

• Laske võtit (väärtust) otsida "k" abil.
• Alustage otsimist juurest ja liikuge rekursiivselt alla.
• Kui k on väiksem kui juurväärtus, otsige vasakpoolset alampuud, kui k on suurem kui juurväärtus, otsige paremat alampuud.
• Kui sõlmel on leitud k, tagastage see lihtsalt.
• Kui k-d sõlmes ei leidu, liikuge suurema võtmega alla lapse juurde.
• Kui k-d puust ei leita, tagastame NULL.

Sisesta toiming

Kuna B Tree on isetasakaalustuv puu, ei saa te võtit sundida sisestama suvalisse sõlme.

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 jaguneb keskmisest elemendist.
• Keskmisest elemendist saab kahe teise lapse sõlme vanem.
• Sõlmed peavad võtmed kasvavas järjekorras ümber korraldama.

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

Ülaltoodud näites:

• Otsige võtmest sobivat positsiooni sõlmes
• Sisestage võti sihtsõlmesse ja kontrollige reegleid
• Kas pärast sisestamist on sõlmel rohkem kui võrdne minimaalse võtmete arvuga, mis on 1? Sel juhul jah, küll. Kontrollige järgmist reeglit.
• Kas pärast sisestamist on sõlmel rohkem kui maksimaalne võtmete arv, mis on 3? Sel juhul ei, ei ole. See tähendab, et B-puu ei riku ühtegi reeglit ja sisestamine on lõpule viidud.

Ülaltoodud näites:

• Sõlm on jõudnud võtmete maksimaalse arvuni
• Sõlm jaguneb ja keskmisest võtmest saab ülejäänud kahe sõlme juursõlm.
• Paarisarvuliste klahvide korral valitakse keskmine sõlm vasak- või parempoolse eelhäälega.

Ülaltoodud näites:

• Sõlmel on vähem kui võtmeid
• 1 lisatakse 3 juurde, kuid kasvava järjekorra reeglit on rikutud
• Selle parandamiseks sorteeritakse võtmed

Samamoodi saab sõlme hõlpsalt sisestada 13 ja 2, kuna need täidavad sõlmede jaoks vähem kui võtmete reeglit.

Ülaltoodud näites:

• Sõlmel on võtmeid, mis võrduvad võtmetega max.
• Võti sisestatakse sihtsõlme, kuid see rikub võtmete max reeglit.
• Sihtsõlm on jagatud ja vasakpoolse eelarvamusega keskmine võti on nüüd uute alamsõlmede vanem.
• Uued sõlmed on paigutatud kasvavas järjekorras.

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

Kustuta toiming

Kustutustoimingul on rohkem reegleid kui sisestamis- ja otsinguoperatsioonidel.

Kehtib järgmine algoritm:

• Käivitage otsinguoperatsioon ja leidke sõlmedest sihtvõtm
• Rakendati kolme tingimust vastavalt sihtvõtme asukohale, nagu on selgitatud järgmistes jaotistes

Kui sihtvõtm asub lehesõlmes

• Siht asub lehesõlmes, rohkem kui min võtmeid.
  • Selle kustutamine ei riku B Tree vara
• Siht asub lehesõlmes, sellel on min võtmesõlmed
  • Selle kustutamine rikub B Tree omadust
  • Sihtsõlm saab võtit laenata kohe vasakust või parempoolsest sõlmest (õde-vend)
  • Õde-vend ütleb jah, kui tal on rohkem kui minimaalselt võtmeid
  • Võti laenatakse vanemsõlmelt, maksimaalne väärtus kantakse üle vanemale, vanemsõlme maksimaalne väärtus kantakse sihtsõlmele ja eemaldatakse sihtväärtus
• Sihtmärk on lehesõlmes, kuid ühelgi õel-vennal pole võtmete arvu üle min
  • Otsige võtit
  • Liitmine õdede-vendade ja vanemate sõlmede miinimumiga
  • Võtmete koguarv on nüüd üle min
  • Sihtvõti asendatakse vanemasõlme minimaalsega

Kui sihtvõtm asub sisemises sõlmes

• Kas valida kas järjekorras eelkäija või järjekorras järeltulija
• Korraliku eelkäija korral valitakse selle vasakust alampuust maksimaalne võti
• Järjekorras järeltulija korral valitakse selle parempoolsest alampuust minimaalne võti
• Kui sihtvõtme järjekorras eelkäijal on rohkem kui min võtmeid, saab see asendada sihtvõtme järjekorras oleva eelkäija maksimumiga
• Kui sihtvõtme järjekorras eelkäijal pole rohkem kui min võtmeid, otsige järjekorras järeltulija minimaalset võtit.
• Kui sihtvõtme järjekorras eelkäijal ja järeltulijal on mõlemal vähem kui min võtmeid, siis ühendage eelkäija ja järeltulija.

Kui sihtvõtm asub juursõlmes

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

Nüüd mõistame kustutamise toimingut ühe näitega.

Ülaltoodud diagramm näitab erinevaid kustutamise juhtumeid B-puus. See B-puu on järjekorras 5, mis tähendab, et ükskõik millises sõlmes võib olla minimaalselt 3 alamsõlme ja kõigi sõlmede maksimaalne arv on 5. Mõlema sõlme võtmete minimaalne ja maksimaalne arv võivad olla vastavalt 2 ja 4.

Ülaltoodud näites:

• Sihtsõlmel on kustutamiseks sihtmärk
• Sihtsõlmel on võtmeid rohkem kui minimaalseid võtmeid
• Kustutage lihtsalt võti

Ülaltoodud näites:

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

Järgmine skeem selgitab, kuidas seda võtit kustutada:

• Sihtsõlm laenab võtme otseselt vennalt, antud juhul korralikult eelkäijalt (vasak õde-vend), kuna tal pole ühtegi järeltulijat (paremat õde-venda)
• Tellitava eelkäija maksimaalne väärtus kantakse vanemale ja vanem kannab maksimaalse väärtuse sihtsõlmele (vt allolevat diagrammi)

Järgmine näide illustreerib, kuidas kustutada võtit, mis vajab väärtust järjekorras järeltulijast.

• Sihtsõlm laenab võtme otseselt vennalt, antud juhul järjekorras järeltulijalt (parem õde-vend), kuna selle järjekorras oleval eelkäijal (vasakul vennal) on võtmed, mis on võrdsed miinimumvõtmetega.
• Järjekorras oleva pärija minimaalne väärtus kantakse vanemale ja vanem kannab maksimaalse väärtuse sihtsõlmele.

Allpool toodud näites pole sihtsõlmel ühtegi õde-venda, kes saaks oma võtme sihtsõlmele anda. Seetõttu on vajalik ühendamine.

Vaadake sellise võtme kustutamise protseduuri:

• Ühendage sihtsõlm kõigi oma otseste õdede-vendadega koos vanemvõti
  • Vanemasõlmest valitakse võti, mille õed-vennad asuvad kahe ühineva sõlme vahel
• Kustutage ühendatud võti sihtmärk

Kustutage operatsioon Pseudokood

private int removeBiggestElement(){if (root has no child)remove and return the last elementelse {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 isetasakaalustuv andmestruktuur andmete paremaks otsimiseks, sisestamiseks ja kettalt kustutamiseks.
• B Puud reguleerib määratud aste
• 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õtm on sõlme väärtusest suurem või väiksem.
• B Tree sisestusoperatsioon on üsna üksikasjalik, mis leiab kõigepealt sihtvõtmele sobiva sisestusasendi, sisestab selle, hindab B Tree kehtivust erinevate juhtumite põhjal ja seejärel B Tree sõlmed vastavalt sellele ümber.
• B Tree kustutustoiming otsib kõigepealt kustutatavat võtmevõtit, kustutab selle, hindab kehtivust mitme juhtumi põhjal, näiteks sihtmärgi sõlme, õdede-vendade ja vanema minimaalsed ja maksimaalsed võtmed.