Kaj je drevo B +?
B + drevo se predvsem uporabljajo za izvajanje dinamične indeksiranje na več ravneh. V primerjavi z B-Tree drevo B + shrani kazalce podatkov samo na listna vozlišča drevesa, zaradi česar je iskanje bolj natančno in hitrejše.
V tej vadnici B + Tree boste izvedeli:
- Kaj je drevo B +?
- Pravila za drevo B +
- Zakaj uporabljati B + Tree
- B + Tree v primerjavi z B Tree
- Iskalna operacija
- Vstavite postopek
- Izbriši operacijo
Pravila za drevo B +
Tu so bistvena pravila za drevo B +.
- Listi se uporabljajo za shranjevanje podatkovnih zapisov.
- Shranjeno je v notranjih vozliščih drevesa.
- Če je vrednost ciljnega ključa manjša od notranjega vozlišča, se sledi točki na levi strani.
- Če je vrednost ciljnega ključa večja ali enaka notranjemu vozlišču, sledi točka le na njegovi desni strani.
- Koren ima najmanj dva otroka.
Zakaj uporabljati B + Tree
Tu so razlogi za uporabo drevesa B +:
- Ključi se v glavnem uporabljajo za pomoč pri iskanju z usmerjanjem na ustrezen list.
- B + Tree uporablja "faktor zapolnitve" za upravljanje povečanja in zmanjšanja drevesa.
- V drevesih B + lahko številne tipke enostavno položite na pomnilniško stran, ker nimajo podatkov, povezanih z notranjimi vozlišči. Zato bo hitro dostopal do drevesnih podatkov, ki so na vozlišču listov.
- Celovit popoln pregled vseh elementov je drevo, ki potrebuje le en linearni prehod, ker so vsa listnata vozlišča drevesa B + povezana med seboj.
B + Tree v primerjavi z B Tree
Tu so glavne razlike med B + Tree in B Tree
| B + drevo | B Drevo |
| Iskalne tipke lahko ponovite. | Iskalne tipke ne morejo biti odvečne. |
| Podatki se shranijo samo na vozliščih listov. | Tako vozlišča listov kot notranja vozlišča lahko shranjujejo podatke |
| Podatki, shranjeni na vozlišču listov, naredijo iskanje natančnejše in hitrejše. | Iskanje je počasno zaradi podatkov, shranjenih na Leaf in notranjih vozliščih. |
| Brisanje ni težko, saj se element odstrani samo iz vozlišča listov. | Brisanje elementov je zapleten in dolgotrajen postopek. |
| Povezana vozlišča listov omogočajo učinkovito in hitro iskanje. | Ne morete povezati vozlišč listov. |
Iskalna operacija
V B + Tree je iskanje eden najlažjih postopkov za izvedbo in iz njega dobite hitre in natančne rezultate.
Uporablja se naslednji algoritem iskanja:
- Če želite najti zahtevani zapis, morate izvesti binarno iskanje na razpoložljivih zapisih v drevesu.
- V primeru natančnega ujemanja z iskalno tipko se ustrezen zapis vrne uporabniku.
- Če natančnega ključa iskanje ne najde v nadrejenem, trenutnem ali listnem vozlišču, se uporabniku prikaže sporočilo »not found«.
- Za boljše in natančnejše rezultate lahko postopek iskanja znova zaženete.
Algoritem iskalne operacije
1. Call the binary search method on the records in the B+ Tree.2. If the search parameters match the exact keyThe accurate result is returned and displayed to the userElse, if the node being searched is the current and the exact key is not found by the algorithmDisplay the statement "Recordset cannot be found."
Izhod :
Uporabniku se prikaže ustrezen zapis, nastavljen glede na natančen ključ; v nasprotnem primeru se uporabniku prikaže neuspešen poskus.
Vstavite postopek
Za operacijo vstavljanja se uporablja naslednji algoritem:
- 50 odstotkov elementov v vozliščih se premakne na nov list za shranjevanje.
- Starš novega lista je natančno povezan z najmanjšo vrednostjo ključa in novim mestom v drevesu.
- Razdelite nadrejeno vozlišče na več lokacij, če se popolnoma izkoristi.
- Zdaj je za boljše rezultate sredinski ključ povezan z vozliščem najvišje ravni tega lista.
- Dokler vozlišča najvišje ravni ne najdemo, nadaljujte s ponavljanjem postopka, pojasnjenega v zgornjih korakih.
Vstavi algoritem operacije
1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record2. Else, divide the node into more locations to fit more records.a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the treeb. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.c. Divide the top-level node if it gets full of keys and addresses.i. Similarly, insert a key in the center of the top-level node in the hierarchy of the Tree.d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore.3) Build a new top-level root node of 1 Key and 2 indicators.
Izhod :
Algoritem bo določil element in ga uspešno vstavil v zahtevano listno vozlišče.
Zgornji primer vzorca B + Tree je razložen v spodnjih korakih:
- Najprej imamo 3 vozlišča in prvi 3 elementi, ki so 1, 4 in 6, so dodani na ustreznih mestih v vozliščih.
- Naslednja vrednost v nizu podatkov je 12, ki mora biti del drevesa.
- Če želite to doseči, razdelite vozlišče in dodajte 6 kot element kazalca.
- Zdaj se ustvari desna hierarhija drevesa, preostale vrednosti podatkov pa se ustrezno prilagodijo, pri čemer se upoštevajo veljavna pravila, enaka ali večja od vrednosti vozlišč ključ-vrednost na desni.
Izbriši operacijo
Zapletenost postopka brisanja v drevesu B + presega kompleksnost vstavljanja in iskanja.
Pri brisanju elementa iz drevesa B + je uporaben naslednji algoritem:
- Najprej moramo v drevesu poiskati vnos listov, ki drži ključ in kazalec. , izbriši vnos listov z drevesa, če list izpolnjuje natančne pogoje za brisanje zapisa.
- Če listno vozlišče zadosti zadovoljivemu faktorju, da je napol polno, je operacija končana; v nasprotnem primeru ima vozlišče Leaf najmanj vnosov in ga ni mogoče izbrisati.
- Druga povezana vozlišča na desni in levi lahko izpraznijo vse vnose in jih nato premaknejo na Leaf. Če ta merila niso izpolnjena, morajo združiti listno vozlišče in njegovo povezano vozlišče v drevesni hierarhiji.
- Po združitvi listnega vozlišča s sosednjimi na desni ali levi se vnosi vrednosti v vozlišču lista ali povezane sosede, ki kaže na vozlišče najvišje ravni, izbrišejo.
Zgornji primer prikazuje postopek odstranjevanja elementa iz drevesa B + določenega vrstnega reda.
- Najprej so natančna mesta elementa, ki ga je treba izbrisati, določena v drevesu.
- Tu je element, ki ga je treba izbrisati, mogoče natančno identificirati le na ravni listov in ne pri umestitvi indeksa. Zato lahko element izbrišete, ne da bi to vplivalo na pravila brisanja, kar je vrednost ključa najmanjšega minimuma.
- V zgornjem primeru moramo iz drevesa izbrisati 31.
- Poiskati moramo primere 31 v Index in Leaf.
- Vidimo, da je 31 na voljo tako na ravni vozlišča Index kot Leaf. Zato ga izbrišemo iz obeh primerkov.
- Vendar moramo izpolniti indeks, ki kaže na 42. Zdaj bomo pogledali pravega otroka, mlajšega od 25 let, vzeli najnižjo vrednost in jo postavili kot indeks. Torej, 42 kot edina prisotna vrednost bo postalo indeks.
Izbriši algoritem operacije
1) Start at the root and go up to leaf node containing the key K2) Find the node n on the path from the root to the leaf node containing KA. If n is root, remove Ka. if root has more than one key, doneb. if root has only Ki) if any of its child nodes can lend a nodeBorrow key from the child and adjust child linksii) Otherwise merge the children nodes. It will be a new rootc. If n is an internal node, remove Ki) If n has at least ceil(m/2) keys, done!ii) If n has less than ceil(m/2) keys,If a sibling can lend a key,Borrow key from the sibling and adjust keys in n and the parent nodeAdjust child linksElseMerge n with its siblingAdjust child linksd. If n is a leaf node, remove Ki) If n has at least ceil(M/2) elements, done!In case the smallest key is deleted, push up the next keyii) If n has less than ceil(m/2) elementsIf the sibling can lend a keyBorrow key from a sibling and adjust keys in n and its parent nodeElseMerge n and its siblingAdjust keys in the parent node
Izhod :
Ključ "K" je izbrisan, ključi pa so izposojeni od bratov in sester, da po potrebi prilagodijo vrednosti v n in njegovih nadrejenih vozliščih.
Povzetek:
- B + Tree je samobalansirana podatkovna struktura za natančno in hitrejše iskanje, vstavljanje in brisanje postopkov v podatkih
- Z lahkoto lahko pridobimo popolne podatke ali delne podatke, saj je s pomočjo povezane drevesne strukture to učinkovito.
- Drevesna struktura B + raste in se zmanjšuje s povečanjem / zmanjšanjem števila shranjenih zapisov.
- Shranjevanje podatkov na listnih vozliščih in poznejša razvejanost notranjih vozlišč očitno skrajšata drevesno višino, kar zmanjša vhodne in izhodne operacije diska, kar na koncu porabi veliko manj prostora na pomnilniških napravah.