Kas ir B + koks?
B + Tree ir galvenokārt izmanto, lai īstenotu dinamisku indeksēšanas vairākos līmeņos. Salīdzinot ar B- Tree, B + Tree datu norādes glabā tikai koka lapu mezglos, kas padara meklēšanu precīzāku un ātrāku.
Šajā B + Tree apmācībā jūs uzzināsiet:
- Kas ir B + koks?
- Noteikumi B + kokam
- Kāpēc izmantot B + Tree
- B + koks pret B koku
- Meklēšanas darbība
- Ievietot darbību
- Dzēst darbību
Noteikumi B + kokam
Šeit ir svarīgi noteikumi B + Tree.
- Lapas tiek izmantotas datu ierakstu glabāšanai.
- Tas glabājās koka iekšējos mezglos.
- Ja mērķa atslēgas vērtība ir mazāka nekā iekšējais mezgls, tad seko punktam, kas atrodas tieši tā kreisajā pusē.
- Ja mērķa atslēgas vērtība ir lielāka vai vienāda ar iekšējo mezglu, seko punktam, kas atrodas tieši tā labajā pusē.
- Saknei ir vismaz divi bērni.
Kāpēc izmantot B + Tree
Šeit ir B + koka izmantošanas iemesli:
- Atslēgu galvenokārt izmanto, lai palīdzētu meklēšanai, novirzot uz pareizo lapu.
- B + Tree izmanto "aizpildījuma koeficientu", lai pārvaldītu koka pieaugumu un samazinājumu.
- B + kokos daudzus taustiņus var viegli ievietot atmiņas lapā, jo tiem nav datu, kas saistīti ar iekšējiem mezgliem. Tāpēc tas ātri piekļūs koku datiem, kas atrodas lapu mezglā.
- Visu elementu visaptveroša pilnīga skenēšana ir koks, kuram nepieciešama tikai viena lineāra pāreja, jo visi B + koka lapu mezgli ir savstarpēji saistīti.
B + koks pret B koku
Šeit ir galvenās atšķirības starp B + koku un B koku
| B + koks | B koks |
| Meklēšanas taustiņus var atkārtot. | Meklēšanas taustiņi nevar būt lieki. |
| Dati tiek saglabāti tikai lapu mezglos. | Gan lapu mezgli, gan iekšējie mezgli var saglabāt datus |
| Lapas mezglā saglabātie dati padara meklēšanu precīzāku un ātrāku. | Meklēšana ir lēna, pateicoties datiem, kas saglabāti Leaf un iekšējos mezglos. |
| Dzēšana nav grūta, jo elements tiek noņemts tikai no lapas mezgla. | Elementu dzēšana ir sarežģīts un laikietilpīgs process. |
| Saistītie lapu mezgli padara meklēšanu efektīvu un ātru. | Lapu mezglus nevar saistīt. |
Meklēšanas darbība
Programmā B + Tree meklēšana ir viena no vienkāršākajām procedūrām, lai to izpildītu un no tās iegūtu ātrus un precīzus rezultātus.
Piemērojams šāds meklēšanas algoritms:
- Lai atrastu nepieciešamo ierakstu, jums jāveic binārā meklēšana kokā pieejamajos ierakstos.
- Precīzas meklēšanas atslēgas atbilstības gadījumā atbilstošais ieraksts tiek atgriezts lietotājam.
- Gadījumā, ja precīza atslēga neatrodas pēc meklēšanas vecāku, pašreizējā vai lapu mezglā, lietotājam tiek parādīts ziņojums "nav atrasts".
- Lai iegūtu labākus un precīzākus rezultātus, meklēšanas procesu var atkārtot.
Meklēšanas operācijas algoritms
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."
Izeja :
Lietotājam tiek parādīts saskaņotais ieraksts, kas iestatīts pret precīzu atslēgu; pretējā gadījumā lietotājam tiek parādīts neveiksmīgs mēģinājums.
Ievietot darbību
Ievietošanas darbībai ir piemērots šāds algoritms:
- 50 procenti elementu mezglos tiek pārvietoti uz jaunu lapu uzglabāšanai.
- Jaunās lapas vecāks ir precīzi saistīts ar minimālo atslēgas vērtību un jaunu vietu kokā.
- Sadaliet vecāku mezglu vairākās vietās, ja tas tiks pilnībā izmantots.
- Tagad, lai iegūtu labākus rezultātus, centrālā atslēga ir saistīta ar šīs lapas augšējā līmeņa mezglu.
- Kamēr augšējā līmeņa mezgls nav atrasts, turpiniet atkārtot procesu, kas paskaidrots iepriekš minētajās darbībās.
Ievietojiet darbības algoritmu
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.
Izeja :
Algoritms noteiks elementu un veiksmīgi ievietos to vajadzīgajā lapu mezglā.
Iepriekš minētais B + koka parauga piemērs ir paskaidrots šādās darbībās:
- Pirmkārt, mums ir 3 mezgli, un pirmie 3 elementi, kas ir 1, 4 un 6, tiek pievienoti attiecīgajās mezglu vietās.
- Nākamā datu sērijas vērtība ir 12, kas jāpadara daļa no koka.
- Lai to panāktu, sadaliet mezglu, pievienojiet 6 kā rādītāja elementu.
- Tagad tiek izveidota koka labā hierarhija, un pārējās datu vērtības tiek attiecīgi pielāgotas, paturot prātā piemērojamos noteikumus, kas ir vienādi vai lielāki par vērtībām, salīdzinot ar galvenajiem vērtību mezgliem labajā pusē.
Dzēst darbību
B + Tree dzēšanas procedūras sarežģītība pārsniedz ievietošanas un meklēšanas funkcionalitāti.
Dzēšot elementu no B + koka, ir piemērots šāds algoritms:
- Pirmkārt, kokā ir jāatrod lapas ieraksts, kas tur taustiņu un rādītāju. , dzēsiet lapas koku no koka, ja lapa atbilst precīziem ieraksta dzēšanas nosacījumiem.
- Gadījumā, ja lapu mezgls atbilst apmierinošajam koeficientam tikai līdz pusei piepildījumam, darbība ir pabeigta; pretējā gadījumā mezglā Leaf ir minimālais ierakstu skaits, un to nevar izdzēst.
- Pārējie saistītie mezgli labajā un kreisajā pusē var atbrīvot visus ierakstus, pēc tam tos pārvietot uz lapu. Ja šie kritēriji nav izpildīti, tiem koku hierarhijā jāapvieno lapu mezgls un ar to saistītais mezgls.
- Apvienojot lapu mezglu ar kaimiņiem labajā vai kreisajā pusē, tiek dzēsti vērtību ieraksti lapu mezglā vai saistītajā kaimiņā, kas norāda uz augšējā līmeņa mezglu.
Iepriekš minētajā piemērā ir parādīta procedūra elementa noņemšanai no B + koka ar noteiktu secību.
- Pirmkārt, kokā tiek norādītas precīzas dzēšamā elementa atrašanās vietas.
- Šeit dzēšamo elementu var precīzi noteikt tikai lapu līmenī, nevis indeksa izvietojumā. Tādējādi elementu var izdzēst, neietekmējot dzēšanas kārtulas, kas ir minimālās atslēgas vērtība.
- Iepriekš minētajā piemērā mums ir jāizdzēš 31 no koka.
- Mums vietnēs Index un Leaf ir jāatrod 31 gadījums.
- Mēs varam redzēt, ka 31 ir pieejams gan Index, gan Leaf mezglu līmenī. Tādējādi mēs to izdzēšam no abiem gadījumiem.
- Bet mums ir jāaizpilda indekss, kas norāda uz 42. Tagad mēs aplūkosim pareizo bērnu līdz 25 gadu vecumam un ņemsim minimālo vērtību un ievietosim to kā indeksu. Tātad, tā kā vienīgā vērtība ir 42, tā kļūs par indeksu.
Dzēst darbības algoritmu
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
Izeja :
Atslēga "K" tiek izdzēsta, un atslēgas tiek aizņemtas no brāļiem un māsām, lai vajadzības gadījumā pielāgotu vērtības n un tā vecāku mezglos.
Kopsavilkums:
- B + Tree ir pašbalansējoša datu struktūra, lai veiktu precīzu un ātrāku datu meklēšanu, ievietošanu un dzēšanu
- Mēs varam viegli izgūt pilnīgus datus vai daļējus datus, jo, izmantojot saistīto koku struktūru, tas ir efektīvs.
- B + koka struktūra aug un samazinās, palielinoties / samazinoties uzglabāto ierakstu skaitam.
- Datu glabāšana lapu mezglos un turpmāka iekšējo mezglu sazarošana acīmredzami saīsina koka augstumu, kas samazina diska ievades un izvades darbības, galu galā patērējot daudz mazāk vietas atmiņas ierīcēs.