B + TREE: Paieškos, įterpimo ir ištrynimo operacijų pavyzdys

Turinys:

Anonim

Kas yra B + medis?

„ B + Tree “ pirmiausia naudojamas dinaminiam indeksavimui įgyvendinti keliais lygmenimis. Palyginti su „B- Tree“, „B + Tree“ saugo duomenų rodykles tik medžio lapų mazguose, todėl paieška tampa tikslesnė ir greitesnė.

Šioje „B + Tree“ pamokoje sužinosite:

  • Kas yra B + medis?
  • B + medžio taisyklės
  • Kodėl verta naudoti „B + Tree“
  • B + medis prieš B medį
  • Paieškos operacija
  • Įterpti operaciją
  • Ištrinti operaciją

B + medžio taisyklės

Čia pateikiamos pagrindinės B + medžio taisyklės.

  • Lapai naudojami duomenų įrašams saugoti.
  • Jis kaupėsi vidiniuose medžio mazguose.
  • Jei tikslinio rakto reikšmė yra mažesnė nei vidinio mazgo, laikomasi taško, esančio kairėje pusėje.
  • Jei tikslinio rakto reikšmė yra didesnė arba lygi vidiniam mazgui, tada laikomasi taško, esančio tik jo dešinėje pusėje.
  • Šaknyje yra mažiausiai du vaikai.

Kodėl verta naudoti „B + Tree“

Čia yra B + medžio naudojimo priežastys:

  • Raktas pirmiausia naudojamas paieškai padėti nukreipiant į tinkamą lapą.
  • „B + Tree“ naudoja „užpildymo koeficientą“, kad valdytų medžio padidėjimą ir sumažėjimą.
  • B + medžiuose daugybę raktų galima lengvai įdėti į atminties puslapį, nes jie neturi duomenų, susietų su vidaus mazgais. Todėl jis greitai pasieks medžio duomenis, esančius lapo mazge.
  • Išsamus visų elementų išsamus nuskaitymas yra medis, kuriam reikia tik vieno tiesinio praėjimo, nes visi B + medžio lapų mazgai yra susieti vienas su kitu.

B + medis prieš B medį

Čia yra pagrindiniai skirtumai tarp B + medžio ir B medžio

B + medis B medis
Paieškos klavišus galima pakartoti. Paieškos raktai negali būti nereikalingi.
Duomenys išsaugomi tik lapų mazguose. Tiek lapų, tiek vidiniai mazgai gali saugoti duomenis
Duomenys, saugomi lapų mazge, daro paiešką tikslesnę ir greitesnę. Paieška yra lėta dėl „Leaf“ ir vidiniuose mazguose saugomų duomenų.
Ištrinti nėra sunku, nes elementas pašalinamas tik iš lapo mazgo. Elementų ištrynimas yra sudėtingas ir daug laiko reikalaujantis procesas.
Susieti lapų mazgai daro paiešką efektyvią ir greitą. Negalite susieti lapų mazgų.

Paieškos operacija

„B + Tree“ sistemoje paieška yra viena iš paprasčiausių procedūrų, leidžiančių atlikti greitus ir tikslius jos rezultatus.

Taikomas šis paieškos algoritmas:

  • Norėdami rasti reikiamą įrašą, turite atlikti dvejetainę paiešką medyje esančiuose įrašuose.
  • Tiksliai sutapus su paieškos raktu, atitinkamas įrašas grąžinamas vartotojui.
  • Jei tikslaus rakto nėra ieškant pagrindiniame, dabartiniame ar lapų mazge, vartotojui rodomas pranešimas „nerastas“.
  • Norėdami gauti geresnius ir tikslesnius rezultatus, paieškos procesą galima pakartoti iš naujo.

Paieškos operacijos algoritmas

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."

Išvestis :

Vartotojui rodomas suderintas įrašas, nustatytas pagal tikslų raktą; kitaip vartotojui parodomas nepavykęs bandymas.

Įterpti operaciją

Įterpimo operacijai taikomas šis algoritmas:

  • 50 procentų mazgų elementų yra perkeliami į naują lapą saugojimui.
  • Naujo „Leaf“ tėvas yra tiksliai susietas su minimalia rakto verte ir nauja vieta medyje.
  • Padalinkite pagrindinį mazgą į daugiau vietų, jei jis bus visiškai panaudotas.
  • Dabar, norint pasiekti geresnių rezultatų, centrinis raktas yra susietas su to lapo aukščiausio lygio mazgu.
  • Kol nerandamas aukščiausio lygio mazgas, kartokite procesą, paaiškintą aukščiau nurodytuose veiksmuose.

Įterpti operacijos 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.

Išvestis :

Algoritmas nustatys elementą ir sėkmingai jį įterps į reikiamą lapų mazgą.

Aukščiau pateiktas „B + Tree“ pavyzdžio pavyzdys paaiškinamas toliau pateiktais veiksmais:

  • Pirma, mes turime 3 mazgus, o pirmieji 3 elementai, kurie yra 1, 4 ir 6, pridedami prie atitinkamų mazgų vietų.
  • Kita duomenų serijos reikšmė yra 12, kurią reikia įtraukti į medį.
  • Norėdami tai pasiekti, padalykite mazgą, pridėkite 6 kaip rodyklės elementą.
  • Dabar sukuriama medžio dešinioji hierarchija ir atitinkamai koreguojamos likusios duomenų vertės, turint omenyje taikytinas taisykles, lygias arba didesnes už reikšmes, palyginti su raktų vertės mazgais dešinėje.

Ištrinti operaciją

Ištrynimo procedūros sudėtingumas B + medyje viršija įterpimo ir paieškos funkcionalumą.

Šis algoritmas yra naudojamas ištrinant elementą iš B + medžio:

  • Pirma, medyje turime surasti lapo įrašą, kuriame laikomas raktas ir rodyklė. , ištrinkite lapo įrašą iš medžio, jei lapas atitinka tikslius įrašo ištrynimo reikalavimus.
  • Jei lapo mazgas atitinka patenkinamą koeficientą, kad jis yra pusiau užpildytas, operacija baigta; priešingu atveju „Leaf“ mazge yra minimalių įrašų ir jo negalima ištrinti.
  • Kiti susieti mazgai dešinėje ir kairėje gali atlaisvinti visus įrašus, tada perkelti juos į lapą. Jei šie kriterijai nėra įvykdyti, jie turėtų sujungti lapų mazgą ir su juo susietą mazgą medžių hierarchijoje.
  • Sujungus lapo mazgą su jo kaimynais dešinėje arba kairėje, lapų mazgo ar susieto kaimyno verčių įrašai, nukreipiantys į aukščiausio lygio mazgą, ištrinami.

Aukščiau pateiktame pavyzdyje pavaizduota procedūra, kaip pašalinti elementą iš B + medžio pagal tam tikrą tvarką.

  • Pirma, tikslios ištrintino elemento vietos nurodomos medyje.
  • Čia elementą, kurį reikia ištrinti, galima tiksliai nustatyti tik lapų lygyje, o ne rodyklės vietoje. Taigi elementą galima ištrinti nepažeidžiant ištrynimo taisyklių, kurios yra minimalaus rakto vertė.

  • Ankstesniame pavyzdyje mes turime išbraukti 31 iš medžio.
  • „Index“ ir „Leaf“ turime surasti 31 atvejus.
  • Matome, kad 31 yra prieinamas tiek indekso, tiek lapų mazgų lygiu. Taigi mes jį ištriname iš abiejų atvejų.
  • Bet mes turime užpildyti indeksą, nurodydami 42. Dabar mes pažiūrėsime į tinkamą vaiką iki 25 metų ir paimsime mažiausią vertę ir nurodysime kaip indeksą. Taigi, 42 yra vienintelė esama vertė, ji taps indeksu.

Ištrinti operacijos 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

Išvestis :

Raktas „K“ ištrinamas, o raktai skolinami iš brolių ir seserų, norint pakoreguoti n ir jo tėvų mazgų reikšmes, jei reikia.

Santrauka:

  • „B + Tree“ yra savaime subalansuota duomenų struktūra, skirta atlikti tikslią ir greitesnę duomenų paiešką, įterpimą ir ištrynimą
  • Mes galime lengvai gauti išsamius duomenis arba dalinius duomenis, nes pereinant susietą medžio struktūrą tai tampa efektyvu.
  • B + medžio struktūra auga ir mažėja didėjant / mažėjant saugomų įrašų skaičiui.
  • Duomenų kaupimas lapų mazguose ir tolesnis vidinių mazgų išsišakojimas akivaizdžiai sutrumpina medžio aukštį, o tai sumažina disko įvesties ir išvesties operacijas, o galiausiai sunaudoja daug mažiau vietos atminties įrenginiuose.