B + DRVO: Primjer operacija pretraživanja, umetanja i brisanja

Sadržaj:

Anonim

Što je B + stablo?

B + stabla prvenstveno se koristi za implementaciju dinamičkog indeksiranje na više razina. U usporedbi s B-Treeom, B + Tree pohranjuje pokazivače podataka samo na lisnim čvorovima Tree-a, što postupak pretraživanja čini preciznijim i bržim.

U ovom vodiču za B + Tree naučit ćete:

  • Što je B + stablo?
  • Pravila za stablo B +
  • Zašto koristiti B + Tree
  • B + Tree nasuprot B Tree
  • Operacija pretraživanja
  • Umetni rad
  • Izbriši operaciju

Pravila za stablo B +

Evo osnovnih pravila za B + Tree.

  • Listovi se koriste za spremanje zapisa podataka.
  • Pohranjeno je u unutarnjim čvorovima Stabla.
  • Ako je ciljana vrijednost ključa manja od unutarnjeg čvora, slijedi se točka s njegove lijeve strane.
  • Ako je vrijednost ciljanog ključa veća ili jednaka unutarnjem čvoru, slijedi se točka desno s njegove desne strane.
  • Korijen ima najmanje dvoje djece.

Zašto koristiti B + Tree

Evo razloga za upotrebu B + stabla:

  • Ključevi se prvenstveno koriste za pomoć u pretraživanju usmjeravanjem na odgovarajući list.
  • B + Tree koristi "faktor popunjavanja" za upravljanje povećanjem i smanjenjem stabla.
  • U stablima B +, brojni se ključevi lako mogu postaviti na stranicu memorije jer nemaju podatke povezane s unutarnjim čvorovima. Stoga će brzo pristupiti podacima o stablu koji se nalaze na čvoru lista.
  • Sveobuhvatno cjelovito skeniranje svih elemenata stablo je koje treba samo jedan linearni prolaz jer su svi lisni čvorovi B + stabla međusobno povezani.

B + Tree nasuprot B Tree

Ovdje su glavne razlike između B + Tree i B Tree

B + stablo B Drvo
Tipke za pretraživanje mogu se ponoviti. Tipke za pretraživanje ne mogu biti suvišne.
Podaci se spremaju samo na čvorovima lista. I čvorovi lista i unutarnji čvorovi mogu pohranjivati ​​podatke
Podaci pohranjeni na čvoru lista čine pretragu preciznijom i bržom. Traženje je sporo zbog podataka pohranjenih na Leafu i unutarnjim čvorovima.
Brisanje nije teško jer se element uklanja samo s čvorišta lista. Brisanje elemenata složen je i dugotrajan postupak.
Povezani čvorovi lista čine pretragu učinkovitom i brzom. Ne možete povezati čvorove listova.

Operacija pretraživanja

U B + Treeu pretraživanje je jedan od najlakših postupaka za izvršavanje i iz njega se dobivaju brzi i točni rezultati.

Primjenjiv je sljedeći algoritam pretraživanja:

  • Da biste pronašli traženi zapis, morate izvršiti binarno pretraživanje dostupnih zapisa u Stablu.
  • U slučaju da se točno podudara s tipkom za pretraživanje, odgovarajući zapis vraća se korisniku.
  • U slučaju da pretraga u nadređenom, trenutnom ili lisnom čvoru nije pronađena točnog ključa, tada se korisniku prikazuje "poruka nije pronađena".
  • Postupak pretraživanja može se ponovno pokrenuti za bolje i preciznije rezultate.

Algoritam operacije pretraživanja

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

Izlaz :

Korisniku se prikazuje odgovarajući zapis postavljen prema točnom ključu; u suprotnom, korisnik se prikazuje neuspjeli pokušaj.

Umetni rad

Sljedeći algoritam primjenjiv je za operaciju umetanja:

  • 50 posto elemenata u čvorovima premješta se na novi list radi skladištenja.
  • Roditelj novog Leafa točno je povezan s minimalnom vrijednošću ključa i novim mjestom u Stablu.
  • Podijelite roditeljski čvor na više mjesta u slučaju da se u potpunosti iskoristi.
  • Sada je za bolje rezultate središnji ključ povezan s čvorom najviše razine tog lista.
  • Sve dok čvor najviše razine ne bude pronađen, nastavite ponavljati postupak objašnjen u gornjim koracima.

Umetni algoritam 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.

Izlaz :

Algoritam će odrediti element i uspješno ga umetnuti u traženi čvor lista.

Gornji primjer uzorka stabla B + objašnjen je u donjim koracima:

  • Prvo, imamo 3 čvora, a prva 3 elementa, koji su 1, 4 i 6, dodaju se na odgovarajuća mjesta u čvorovima.
  • Sljedeća vrijednost u nizu podataka je 12 koju treba učiniti dijelom stabla.
  • Da biste to postigli, podijelite čvor, dodajte 6 kao element pokazivača.
  • Sada se kreira desna hijerarhija stabla, a preostale vrijednosti podataka prilagođavaju se u skladu s tim imajući na umu primjenjiva pravila jednaka ili veća od vrijednosti prema čvorovima ključ / vrijednost s desne strane.

Izbriši operaciju

Složenost postupka brisanja u stablu B + premašuje složenost funkcije umetanja i pretraživanja.

Sljedeći je algoritam primjenjiv tijekom brisanja elementa iz B + stabla:

  • Prvo, moramo pronaći unos lista na drvetu koji drži ključ i pokazivač. , obrišite unos lista s stabla ako list ispunjava točne uvjete brisanja zapisa.
  • U slučaju da listni čvor zadovoljava samo zadovoljavajući faktor da je napola pun, tada je operacija dovršena; u suprotnom, čvor Leaf ima najmanje unosa i ne može se izbrisati.
  • Ostali povezani čvorovi s desne i lijeve strane mogu osloboditi sve unose, a zatim ih premjestiti na Leaf. Ako ti kriteriji nisu ispunjeni, tada bi trebali kombinirati lisni čvor i njegov povezani čvor u hijerarhiji stabla.
  • Spajanjem lisnog čvora sa susjedima zdesna ili s lijeve strane, unosi vrijednosti u čvoru lista ili povezanog susjeda koji upućuju na čvor najviše razine brišu se.

Gornji primjer ilustrira postupak uklanjanja elementa s B + stabla određenog reda.

  • Prvo, tačna mjesta elementa koji se briše identificirana su na stablu.
  • Ovdje se element koji se briše može točno identificirati samo na razini lista, a ne i na položaju indeksa. Dakle, element se može izbrisati bez utjecaja na pravila brisanja, što je vrijednost ključa golog minimuma.

  • U gornjem primjeru moramo s Stabla izbrisati 31.
  • Moramo locirati slučajeve 31 u Indexu i Leafu.
  • Vidimo da je 31 dostupan i na razini indeksa i na razini čvora Leaf. Stoga ga brišemo iz oba slučaja.
  • Ali, moramo popuniti indeks koji pokazuje na 42. Sada ćemo pogledati pravo dijete mlađe od 25 godina i uzeti ćemo minimalnu vrijednost i smjestiti ga kao indeks. Dakle, 42 je jedina prisutna vrijednost, ona će postati indeks.

Izbrišite algoritam 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

Izlaz :

Ključ "K" se briše, a ključevi se posuđuju od braće i sestara radi prilagođavanja vrijednosti u n i njegovih nadređenih čvorova ako je potrebno.

Sažetak:

  • B + Tree je samobalansirajuća struktura podataka za izvršavanje točnog i bržeg pretraživanja, umetanja i brisanja postupaka na podacima
  • Kompletne podatke ili djelomične podatke možemo lako dobiti, jer prolazak kroz povezanu strukturu stabla čini ga učinkovitim.
  • Struktura stabla B + raste i smanjuje se s povećanjem / smanjenjem broja pohranjenih zapisa.
  • Pohrana podataka na čvorovima lista i naknadno grananje unutarnjih čvorova očito skraćuje visinu stabla, što smanjuje operacije unosa i izlaza diska, što u konačnici troši mnogo manje prostora na uređajima za pohranu.