Mis on B + puu?
B + Tree peamiselt kasutatud rakendamise dünaamiline indekseerimise mitmel tasandil. Võrreldes B-Tree'ga salvestab B + Tree andmekursorid ainult puu lehesõlmedesse, mis muudab otsingu täpsemaks ja kiiremaks.
Selles B + Tree õpetuses saate teada:
- Mis on B + puu?
- Reeglid B + puu jaoks
- Miks kasutada B + puud
- B + puu vs B puu
- Otsinguoperatsioon
- Sisesta toiming
- Kustuta toiming
Reeglid B + puu jaoks
Siin on B + puu jaoks olulised reeglid.
- Lehti kasutatakse andmete kirjete salvestamiseks.
- See salvestati puu sisemistesse sõlmedesse.
- Kui sihtvõtme väärtus on väiksem kui sisemine sõlm, siis järgitakse lihtsalt selle vasakul küljel asuvat punkti.
- Kui sihtvõtme väärtus on sisesõlmest suurem või sellega võrdne, järgitakse selle paremal küljel asuvat punkti.
- Juurel on minimaalselt kaks last.
Miks kasutada B + puud
Siin on B + puu kasutamise põhjused:
- Võtit kasutatakse peamiselt otsingu hõlbustamiseks, suunates õigele lehele.
- B + Tree kasutab puu suurenemise ja vähenemise haldamiseks "täitetegurit".
- B + puudes saab arvukalt võtmeid hõlpsasti mälu lehele panna, kuna neil pole sisesõlmedega seotud andmeid. Seetõttu pääseb see kiiresti lehesõlmes olevate puuandmete juurde.
- Kõigi elementide põhjalik täielik skaneerimine on puu, mis vajab ainult ühte lineaarset läbimist, kuna B + puu kõik lehesõlmed on omavahel seotud.
B + puu vs B puu
Siin on peamised erinevused B + puu ja B puu vahel
| B + puu | B puu |
| Otsinguklahve saab korrata. | Otsinguklahvid ei saa olla üleliigsed. |
| Andmed salvestatakse ainult lehesõlmedele. | Andmeid saavad salvestada nii lehesõlmed kui ka sisemised sõlmed |
| Lehesõlme salvestatud andmed muudavad otsingu täpsemaks ja kiiremaks. | Otsimine on Leafi ja sisemiste sõlmede salvestatud andmete tõttu aeglane. |
| Kustutamine pole keeruline, kuna element eemaldatakse ainult lehesõlmest. | Elementide kustutamine on keeruline ja aeganõudev protsess. |
| Seotud lehesõlmed muudavad otsingu tõhusaks ja kiireks. | Lehesõlmi ei saa linkida. |
Otsinguoperatsioon
Rakenduses B + Tree on otsing üks lihtsamaid toiminguid ja kiireid ja täpseid tulemusi.
Kohaldatav on järgmine otsingu algoritm:
- Nõutava kirje leidmiseks peate läbi viima kahendotsingu Puus saadaolevatel kirjetel.
- Otsinguklahviga täpse vaste korral tagastatakse vastav kirje kasutajale.
- Kui täpne võti ei asu otsingu kaudu vanem-, praeguses või lehesõlmes, kuvatakse kasutajale teade "ei leitud".
- Paremate ja täpsemate tulemuste saamiseks saab otsinguprotsessi uuesti käivitada.
Otsinguoperatsiooni algoritm
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."
Väljund :
Kasutajale kuvatakse sobitatud rekord, mis on seatud täpse võtmega; vastasel juhul kuvatakse kasutajale nurjunud katse.
Sisesta toiming
Lisamistoimingu jaoks on kasutatav järgmine algoritm:
- 50 protsenti sõlmede elementidest viiakse ladustamiseks uuele lehele.
- Uue lehe vanem on täpselt seotud minimaalse võtmeväärtuse ja uue asukohaga puul.
- Jagage vanemasõlm rohkematesse kohtadesse, juhul kui see täielikult ära kasutatakse.
- Nüüd on parema tulemuse saavutamiseks seotud keskne võti selle lehe tipptasemel sõlmega.
- Kuni tipptasemel sõlme ei leita, jätkake ülaltoodud sammudes kirjeldatud protsessi kordamist.
Sisesta operatsiooni algoritm
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.
Väljund :
Algoritm määrab elemendi ja sisestab selle edukalt vajalikule lehesõlmele.
Ülaltoodud B + puu näite näidet selgitatakse allpool toodud sammudes:
- Esiteks on meil 3 sõlme ja esimesed 3 elementi, milleks on 1, 4 ja 6, lisatakse sõlmede asjakohastele kohtadele.
- Järgmine väärtus andmeseerias on 12, mis tuleb muuta puu osaks.
- Selle saavutamiseks jagage sõlm, lisage kursori elemendiks 6.
- Nüüd luuakse puu parempoolne hierarhia ja ülejäänud andmeväärtusi kohandatakse vastavalt, pidades silmas kehtivaid reegleid, mis on väärtustega võrdsed või suuremad, võrreldes parempoolsete võtmeväärtuste sõlmedega.
Kustuta toiming
Kustutusprotseduuri keerukus B + puus ületab sisestamis- ja otsingufunktsioonide keerukuse.
B + puust elemendi kustutamisel saab kasutada järgmist algoritmi:
- Esiteks peame leidma puust lehekande, mis hoiab võtit ja kursorit. , kustutage lehe kirje puust, kui leht täidab kirje kustutamise täpseid tingimusi.
- Juhul kui lehesõlm vastab rahuldavale poolväärtusega tegurile, on toiming lõpule viidud; vastasel juhul on Leaf-sõlmel minimaalselt kirjeid ja seda ei saa kustutada.
- Teised lingitud sõlmed paremal ja vasakul võivad kõik kirjed vabastada ja seejärel lehte teisaldada. Kui need kriteeriumid ei ole täidetud, peaksid nad puuhierarhias ühendama lehesõlme ja sellega seotud sõlme.
- Lehesõlme liitmisel paremal või vasakul asuvate naabritega kustutatakse lehesõlme või lingitud naabri tipptasemel sõlmele osutavate väärtuste kirjed.
Ülaltoodud näide illustreerib protseduuri elemendi eemaldamiseks kindla järjekorra B + puust.
- Esiteks määratakse puul kustutatava elemendi täpsed asukohad.
- Siin saab kustutatava elemendi täpselt tuvastada ainult lehe tasemel, mitte indeksi paigutamisel. Seega saab elemendi kustutada, ilma et see mõjutaks kustutamise reegleid, mis on minimaalse minimaalse võtme väärtus.
- Ülaltoodud näites peame puudest kustutama 31.
- Peame leidma indeksite ja lehtede 31 eksemplari.
- Näeme, et 31 on saadaval nii Indeksi kui ka Lehe sõlmede tasemel. Seega kustutame selle mõlemast eksemplarist.
- Kuid peame täitma indeksi, osutades 42-le. Nüüd vaatame õiget alla 25-aastast last ja võtame miinimumväärtuse ning paigutame selle indeksiks. Niisiis, kui 42 on ainus olemasolev väärtus, saab sellest indeks.
Kustuta operatsiooni algoritm
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
Väljund :
Võti "K" kustutatakse ja võtmed laenatakse õdedelt-vendadelt, et vajadusel n-s ja selle vanemasõlmedes väärtusi kohandada.
Kokkuvõte:
- B + Tree on isetasakaalustuv andmestruktuur andmete täpseks ja kiiremaks otsimiseks, sisestamiseks ja kustutamiseks
- Saame hõlpsasti hankida täielikud andmed või osalised andmed, kuna lingitud puustruktuuri läbimine muudab selle tõhusaks.
- B + puu struktuur kasvab ja kahaneb koos salvestatud kirjete arvu suurenemise / vähenemisega.
- Andmete salvestamine lehesõlmedele ja järgnev sisemiste sõlmede hargnemine lühendab ilmselt puu kõrgust, mis vähendab ketta sisend- ja väljundoperatsioone ning lõpuks kulutab mäluseadmetel palju vähem ruumi.