B DREVO v strukturi podatkov: Primer operacije iskanje, vstavljanje, brisanje

Kazalo:

Anonim

Kaj je drevo B?

B Tree je samo-uravnotežujoča se podatkovna struktura, ki temelji na določenem naboru pravil za hitrejše iskanje in vstavljanje in brisanje podatkov ter pomnilniško učinkovitejši način. Da bi to dosegli, se za ustvarjanje drevesa B upoštevajo naslednja pravila.

B-Tree je posebna vrsta drevesa v podatkovni strukturi. Leta 1972 je to metodo prvič predstavil McCreight, Bayer pa jo je poimenoval Height Balanced m-way Search Tree. Pomaga vam, da v krajšem času ohrani podatke, razvrščene in dovoljene različne operacije, kot so vstavljanje, iskanje in brisanje.

V tej vadnici B-Tree boste izvedeli:

  • Kaj je drevo B?
  • Zakaj uporabljati B-Tree
  • Zgodovina drevesa B
  • Iskalna operacija
  • Vstavite postopek
  • Izbriši operacijo

Pravila za B-Tree

Tu so pomembna pravila za ustvarjanje B_Tree

  • Vsi listi bodo ustvarjeni na isti ravni.
  • B-Tree je določeno s številom stopinj, ki se imenuje tudi "vrstni red" (določi ga zunanji akter, kot je programer), ki se imenuje 
    m
    naprej. Vrednost 
    m
    je odvisno od velikosti bloka na disku, na katerem so podatki v glavnem.
  • Levo poddrevo vozlišča bo imelo manj vrednosti kot desna stran poddrevesa. To pomeni, da so vozlišča razvrščena tudi v naraščajočem vrstnem redu od leve proti desni.
  • Največje število podrejenih vozlišč, koreninsko vozlišče in njegova podrejena vozlišča, ki jih lahko vsebuje, se izračuna po tej formuli: 
    m - 1
    Na primer: 
    m = 4max keys: 4 - 1 = 3

  • Vsako vozlišče, razen korenskega, mora vsebovati najmanj ključev 
    [m/2]-1
    Na primer: 
    m = 4min keys: 4/2-1 = 1
  • Največje število podrejenih vozlišč, ki jih lahko ima vozlišče, je enako njegovi stopnji, kar je 
    m
  • Najmanjše število podrejenih vozlišč je polovica vrstnega reda, kar je m / 2 (upošteva se zgornja meja).
  • Vsi ključi v vozlišču so razvrščeni v naraščajočem vrstnem redu.

Zakaj uporabljati B-Tree

Tukaj so razlogi za uporabo B-Tree

  • Zmanjša število branja na disku
  • B Drevesa lahko enostavno optimizirate, da prilagodite njegovo velikost (to je število podrejenih vozlišč) glede na velikost diska
  • To je posebej zasnovana tehnika za obdelavo obsežne količine podatkov.
  • Je koristen algoritem za podatkovne baze in datotečne sisteme.
  • Dobra izbira za branje in pisanje velikih blokov podatkov

Zgodovina drevesa B

  • Podatki se na disku shranijo v blokih, ti podatki, ko jih prenesemo v glavni pomnilnik (ali RAM), se imenujejo podatkovna struktura.
  • V primeru ogromnih podatkov je za iskanje enega zapisa na disku treba prebrati celoten disk; to poveča čas in porabo glavnega pomnilnika zaradi visoke frekvence dostopa do diska in velikosti podatkov.
  • Da bi to premagali, se ustvarijo indeksne tabele, ki shranijo referenco zapisov na podlagi blokov, v katerih se nahajajo. To drastično zmanjša čas in porabo pomnilnika.
  • Ker imamo ogromno podatkov, lahko ustvarimo indeksne tabele na več ravneh.
  • Večstopenjski indeks je mogoče oblikovati z uporabo B Tree za vodenje podatkov, razvrščenih na način samo-uravnoteženja.

Iskalna operacija

Iskalna operacija je najpreprostejša operacija na B Tree.

Uporablja se naslednji algoritem:

  • Naj ključ (vrednost) išče "k".
  • Začnite iskati od korena in se rekurzivno pomaknite navzdol.
  • Če je k manjša od korenske vrednosti, poiščite levo poddrevo, če je k večja od korenske vrednosti, poiščite desno poddrevo.
  • Če ima vozlišče najdeni k, ga preprosto vrnite.
  • Če k v vozlišču ni, pojdite do otroka z večjim ključem.
  • Če k v drevesu ni mogoče najti, vrnemo NULL.

Vstavite postopek

Ker je drevo B drevo samo-uravnoteženo, ključa ne morete na silo vstaviti v katero koli vozlišče.

Uporablja se naslednji algoritem:

  • Zaženite iskalno operacijo in poiščite primerno mesto vstavljanja.
  • Vstavite nov ključ na pravo mesto, če pa ima vozlišče že največje število ključev:
  • Vozlišče se bo skupaj z na novo vstavljenim ključem ločilo od srednjega elementa.
  • Srednji element bo postal nadrejeni za druga dva podrejena vozlišča.
  • Vozlišča morajo prerazporediti ključe v naraščajočem vrstnem redu.

NASVET

Za algoritem za vstavljanje ne drži:

Ker je vozlišče polno, se bo torej razdelilo in nato bo vstavljena nova vrednost

V zgornjem primeru:

  • V vozlišču poiščite ključ v ustreznem položaju
  • Ključ vstavite v ciljno vozlišče in preverite, ali obstajajo pravila
  • Ali ima vozlišče po vstavitvi več kot enako najmanjšemu številu ključev, ki je 1? V tem primeru je tako. Preverite naslednje pravilo.
  • Ali ima vozlišče po vstavitvi več kot največje število ključev, to je 3? V tem primeru ne. To pomeni, da drevo B ne krši nobenih pravil in je vstavljanje končano.

V zgornjem primeru:

  • Vozlišče je doseglo največje število ključev
  • Vozlišče se bo razdelilo, srednji ključ pa bo postal korensko vozlišče preostalih dveh vozlišč.
  • V primeru parnega števila tipk bo srednje vozlišče izbrano z levo ali desno pristranskostjo.

V zgornjem primeru:

  • Vozlišče ima manj kot največ tipk
  • 1 je vstavljen poleg 3, vendar je kršeno pravilo naraščajočega vrstnega reda
  • Da bi to popravili, so tipke razvrščene

Podobno lahko v vozlišče enostavno vstavite 13 in 2, saj izpolnjujeta pravilo ključev za vozlišča manj kot največ.

V zgornjem primeru:

  • Vozlišče ima ključe, enake največjim ključem.
  • Ključ je vstavljen v ciljno vozlišče, vendar krši pravilo največ tipk.
  • Ciljno vozlišče je razdeljeno in srednji ključ po levi pristranskosti je zdaj nadrejen za nove podrejene vozlišča.
  • Nova vozlišča so razporejena v naraščajočem vrstnem redu.

Podobno lahko na podlagi zgornjih pravil in primerov ostale vrednosti enostavno vstavite v drevo B.

Izbriši operacijo

Operacija brisanja ima več pravil kot vstavitev in iskanje.

Uporablja se naslednji algoritem:

  • Zaženite iskalno operacijo in v vozliščih poiščite ciljni ključ
  • Na podlagi lokacije ciljnega ključa so bili uporabljeni trije pogoji, kot je razloženo v naslednjih razdelkih

Če je ciljni ključ v vozlišču listov

  • Cilj je v vozlišču listov, več kot min ključev.
    • Če to izbrišete, ne bo kršena lastnost drevesa B.
  • Cilj je v vozlišču listov, ima najmanj ključnih vozlišč
    • Če izbrišete to, bo kršena lastnost drevesa B.
    • Ciljno vozlišče si lahko izposodi ključ od neposrednega levega vozlišča ali neposrednega desnega vozlišča (brata ali sestre)
    • Brat ali sestra bo odgovoril z da, če ima več kot minimalno število ključev
    • Ključ bo izposojen od nadrejenega vozlišča, največja vrednost bo prenesena nadrejenemu, največja vrednost nadrejenega vozlišča bo prenesena v ciljno vozlišče in odstraniti ciljno vrednost
  • Cilj je v vozlišču listov, vendar noben brat ali sestra nima več kot najmanjše število ključev
    • Poiščite ključ
    • Združite se z brati in sestrami in najmanj nadrejenimi vozlišči
    • Skupno število ključev bo zdaj več kot min
    • Ciljni ključ bo nadomeščen z najmanj nadrejenim vozliščem

Če je ciljni ključ v notranjem vozlišču

  • Izberite bodisi predhodnika po vrstnem redu ali naslednika po vrstnem redu
  • V primeru predhodnika po vrstnem redu bo izbran največji ključ iz njegovega levega poddrevesa
  • V primeru naslednika po vrstnem redu bo izbran najmanjši ključ iz njegovega desnega poddrevesa
  • Če ima predhodnik v vrstnem redu ciljnega ključa več kot ključev min, lahko le ciljni ključ nadomesti z maksimumom predhodnika v vrstnem redu
  • Če predhodnik ciljnega ključa po vrstnem redu nima več kot min ključev, poiščite najmanjši ključ naslednika po vrstnem redu.
  • Če imata predhodnik in naslednik ciljnega ključa manj kot min ključev, združite predhodnika in naslednika.

Če je ciljni ključ v korenskem vozlišču

  • Nadomestite z največjim elementom podrevesa predhodnika po vrstnem redu
  • Če ima po izbrisu cilj manj kot najmanj ključev, si bo ciljno vozlišče sposodilo največjo vrednost od svojega brata ali sestre preko nadrejenega.
  • Največjo vrednost nadrejenega bo vzel cilj, vendar z vozlišči največje vrednosti brata ali sestre.

Zdaj pa razumimo operacijo brisanja s primerom.

Zgornji diagram prikazuje različne primere brisanja v drevesu B. To drevo B je vrstnega reda 5, kar pomeni, da je najmanjše število podrejenih vozlišč, ki jih lahko ima katero koli vozlišče, 3, največje število podrejenih vozlišč, ki jih ima katero koli vozlišče, pa je 5. Medtem ko je najmanjše in največje število ključev katerega koli vozlišča lahko imajo 2 oziroma 4.

V zgornjem primeru:

  • Ciljno vozlišče ima ciljni ključ za brisanje
  • Ciljno vozlišče ima ključe več kot minimalne ključe
  • Preprosto izbrišite ključ

V zgornjem primeru:

  • Ciljno vozlišče ima ključe, ki so enaki minimalnim ključem, zato ga ne morete neposredno izbrisati, ker bo kršil pogoje

V naslednjem diagramu je razloženo, kako izbrisati ta ključ:

  • Ciljno vozlišče si bo izposodilo ključ od takojšnjega brata, v tem primeru predhodnika po vrstnem redu (levi brat ali sestra), ker nima naslednika po vrstnem redu (desni brat ali sestra)
  • Najvišja vrednost predhodnika inorder bo prenesena na nadrejenega, nadrejena pa bo prenesla največjo vrednost na ciljno vozlišče (glej spodnji diagram)

Naslednji primer prikazuje, kako iz naslednika po vrstnem redu izbrišete ključ, ki potrebuje vrednost.

  • Ciljno vozlišče si bo izposodilo ključ od takojšnjega brata, v tem primeru naslednika po vrstnem redu (desni brat ali sestra), ker ima njegov predhodnik po vrstnem redu (levi brat ali sestra) ključe, enake minimalnim ključem.
  • Najmanjša vrednost naslednika po vrstnem redu bo prenesena na nadrejenega, nadrejeni pa na ciljno vozlišče.

V spodnjem primeru ciljno vozlišče nima nobenega brata ali sestre, ki bi lahko dal svoj ključ ciljnemu vozlišču. Zato je združitev potrebna.

Glejte postopek brisanja takega ključa:

  • Ciljno vozlišče združite s katerim koli od njegovih neposrednih bratov in sester skupaj s starševskim ključem
    • Izbran je ključ iz nadrejenega vozlišča, ki se nahaja med dvema vozliščema, ki se združujeta
  • Iz združenega vozlišča izbrišite ciljni ključ

Izbrišite operativno psevdo kodo

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

Izhod :

Največji element je izbrisan iz drevesa B.

Povzetek:

  • B Tree je samobalansirana podatkovna struktura za boljše iskanje, vstavljanje in brisanje podatkov z diska.
  • B Drevo je urejeno z določeno stopnjo
  • B Drevesne tipke in vozlišča so razporejena v naraščajočem vrstnem redu.
  • Postopek iskanja drevesa B je najpreprostejši, ki se vedno začne od korena in začne preverjati, ali je ciljni ključ večji ali manjši od vrednosti vozlišča.
  • Postopek vstavljanja drevesa B je precej podroben, ki najprej poišče primeren položaj vstavitve za ciljni ključ, ga vstavi, oceni veljavnost drevesa B glede na različne primere in nato vozlišča drevesa B ustrezno prestrukturira.
  • Operacija brisanja drevesa B najprej poišče ciljni ključ, ki ga je treba izbrisati, ga izbriše in oceni veljavnost na podlagi več primerov, kot so minimalni in največji ključi ciljnega vozlišča, bratov in sester ter nadrejenega.