B+ TREE: otsimine, sisestamine ja kustutamine Operamine
Sarah Chen
⚡ Nutikas kokkuvõte
B+ puu on mitmetasandiline dünaamiline indeks, mis salvestab andmeviideid ainult lingitud lehesõlmedesse, muutes otsingud täpseks ja kiireks. See hõlmab B+ puu reegleid, selle erinevust B-puust ning otsingu-, lisamis- ja kustutamistoiminguid.
Mis on B+ puu?
A B+ puu kasutatakse peamiselt dünaamilise indekseerimise rakendamiseks mitmel tasandil. Võrreldes B-puuga salvestab B+ puu andmeviited ainult puu lehesõlmedesse, mis muudab otsinguprotsessi täpsemaks ja kiiremaks.
B+ puu reeglid
Siin on B+ puu olulised reeglid.
- Lehti kasutatakse andmekirjete salvestamiseks.
- Kirjed salvestatakse puu sisemistesse sõlmedesse.
- Kui sihtvõtme väärtus on väiksem kui sisemise sõlme väärtus, järgitakse sellest vasakul asuvat pointerit.
- Kui sihtvõtme väärtus on suurem või võrdne sisemise sõlme väärtusega, järgitakse sellest paremal asuvat pointerit.
- Juurel on minimaalselt kaks last.
Miks kasutada B+ puud
B+ puu kasutamise põhjused on järgmised:
- Võtmeid kasutatakse peamiselt otsingu hõlbustamiseks, suunates õigele lehele.
- B+ puu kasutab puu suurenemise ja vähenemise haldamiseks „täitetegurit“.
- B+ puude puhul saab arvukalt võtmeid hõlpsasti mälulehele paigutada, kuna neil puuduvad sisemiste sõlmedega seotud andmed. Seetõttu pääseb see kiiresti juurde lehesõlmes olevatele puuandmetele.
- Kõigi elementide täielik skaneerimine nõuab vaid ühte lineaarset läbimist, kuna B+ puu kõik lehesõlmed on omavahel seotud.
B+ puu vs. puu B
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 lehtede sõlmedesse. | Andmeid saavad salvestada nii lehe- kui ka sisesõlmed. |
| Lehesõlmele salvestatud andmed muudavad otsingu täpsemaks ja kiiremaks. | Otsimine on aeglane lehtedel ja sisemistel sõlmedel talletatud andmete tõttu. |
| Kustutamine ei ole keeruline, kuna element eemaldatakse ainult lehesõlmest. | Elementide kustutamine on keeruline ja aeganõudev protsess. |
| Lingitud lehtede sõlmed muudavad otsingu tõhusaks ja kiireks. | Lehtede sõlmi ei saa linkida. |
Otsing Operamine
B+ puus on otsing üks lihtsamini teostatavaid protseduure ning see annab kiireid ja täpseid tulemusi.
Kasutatav on järgmine otsingualgoritm:
- Vajaliku kirje leidmiseks peate käivitama käsu binaarotsing puus saadaolevatel kirjetel.
- Otsinguvõtmega täpse vaste korral tagastatakse vastav kirje kasutajale.
- Kui täpset võtit ei leidu otsinguga vanem-, voolu- või lehesõlmes, kuvatakse kasutajale teade "ei leitud".
- Paremate ja täpsemate tulemuste saamiseks saab otsinguprotsessi uuesti käivitada.
Otsing OperaAlgoritm
1. Call the binary search method on the records in the B+ Tree. 2. If the search parameters match the exact key The accurate result is returned and displayed to the user Else, if the node being searched is the current and the exact key is not found by the algorithm Display the statement "Recordset cannot be found."
Väljund: Täpse võtmega vastendatud kirje kuvatakse kasutajale; vastasel juhul näidatakse kasutajale ebaõnnestunud katset.
Sisesta Operamine
Sisestamistoimingu jaoks kehtib järgmine algoritm:
- 50 protsenti sõlmedes olevatest elementidest viiakse ladustamiseks uuele lehele.
- Uue lehe vanem lingitakse täpselt minimaalse võtmeväärtuse ja uue asukohaga puus.
- Jagage emasõlm mitmeks asukohaks juhuks, kui see täielikult ära kasutatakse.
- Nüüd, paremate tulemuste saavutamiseks, on keskmine võti seotud selle lehe kõrgeima taseme sõlmega.
- Kuni tipptaseme sõlme ei leita, jätkake ülaltoodud sammudes kirjeldatud protsessi kordamist.
Sisesta OperaAlgoritm
1. If inserting at least 1 entry into the leaf container does not make it full, then add the record. 2. 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 tree. b. 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 vajalikku lehesõlme.
Ülaltoodud B+ puu näidisnäidet selgitatakse järgmiste sammudega.
- Esiteks on meil 3 sõlme ja esimesed 3 elementi, mis on 1, 4 ja 6, lisatakse sõlmede sobivatesse kohtadesse.
- Andmeseeria järgmine väärtus on 12, mis tuleb lisada puu osaks.
- Selle saavutamiseks jagage sõlm ja lisage pointerelemendina 6.
- Nüüd luuakse puu parempoolne hierarhia ja ülejäänud andmeväärtusi kohandatakse vastavalt käsuga kee.ping pidage meeles paremal asuvate võtme-väärtuse sõlmede suhtes kehtivaid võrdsete või suuremate väärtuste reegleid.
kustutama Operamine
Kustutusprotseduuri keerukus B+ puus ületab sisestamise ja otsingu funktsioonide keerukuse.
B+ puust elemendi kustutamisel on rakendatav järgmine algoritm:
- Esiteks peame leidma puust lehekirje, mis sisaldab võtit ja pointerit, ning seejärel kustutama lehekirje puust, kui leht vastab täpselt kirje kustutamise tingimustele.
- Kui lehesõlm vastab rahuldavale tegurile, mille kohaselt on see vaid pooltäis, siis toiming on lõpule viidud; vastasel juhul on lehesõlmel minimaalne kirjete arv ja seda ei saa kustutada.
- Teised paremal ja vasakul asuvad lingitud sõlmed saavad tühjendada mis tahes kirjeid ja seejärel lehele teisaldada. Kui need kriteeriumid ei ole täidetud, peaksid nad lehesõlme ja sellega lingitud sõlme puuhierarhias ühendama.
- Lehesõlme ühendamisel paremal või vasakul asuvate naabritega kustutatakse lehesõlme või lingitud naabri väärtuste kirjed, mis osutavad tipptaseme sõlmele.
Ülaltoodud näide illustreerib protseduuri elemendi eemaldamiseks kindla järjekorra B+ puust.
- Esiteks tuvastatakse puus kustutatava elemendi täpsed asukohad.
- Siin saab kustutatavat elementi täpselt tuvastada ainult lehe tasandil, mitte indeksi paigutuse järgi. Seega saab elemendi kustutada ilma kustutamisreegleid mõjutamata, milleks on minimaalse võtme väärtus.
- Ülaltoodud näites peame puust kustutama 31.
- Peame leidma 31 eksemplarid indeksist ja lehest.
- Näeme, et 31 on saadaval nii indeksi- kui ka lehesõlme tasemel. Seega kustutame selle mõlemast eksemplarist.
- Aga me peame täitma indeksi, mis osutab 42-le. Nüüd vaatleme paremat last alla 25-aastasest ja võtame minimaalse väärtuse ning paigutame selle indeksiks. Seega, kuna 42 on ainus olemasolev väärtus, saab sellest indeks.
kustutama OperaAlgoritm
1) Start at the root and go up to the leaf node containing the key K. 2) Find the node n on the path from the root to the leaf node containing K. A. If n is root, remove K a. if root has more than one key, done b. if root has only K i) if any of its child nodes can lend a node Borrow key from the child and adjust child links ii) Otherwise merge the children nodes. It will be a new root c. If n is an internal node, remove K i) 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 node Adjust child links Else Merge n with its sibling Adjust child links d. If n is a leaf node, remove K i) If n has at least ceil(M/2) elements, done! In case the smallest key is deleted, push up the next key ii) If n has less than ceil(m/2) elements If the sibling can lend a key Borrow key from a sibling and adjust keys in n and its parent node Else Merge n and its sibling Adjust keys in the parent node
Väljund: Võti „K” kustutatakse ja vajadusel n-i ja selle vanemsõlmede väärtuste kohandamiseks laenatakse võtmed õdedelt-vendadelt.
