B+ STABLO: Pretraživanje, umetanje i brisanje Operations Primjer

Što je B+ stablo?

A B+ Drvo prvenstveno se koristi za implementaciju dinamičkog indeksiranja na više razina. U usporedbi s B-stablom, B+ stablo pohranjuje pokazivače podataka samo na čvorove listova stabla, što proces pretraživanja čini preciznijim i bržim.

Pravila za B+ stablo

Evo osnovnih pravila za B+ Tree.

• Listovi se koriste za pohranjivanje zapisa podataka.
• Pohranjuje se u unutarnjim čvorovima Stabla.
• Ako je vrijednost ciljnog ključa manja od unutarnjeg čvora, tada se slijedi točka na njegovoj lijevoj strani.
• Ako je vrijednost ciljnog ključa veća ili jednaka unutarnjem čvoru, slijedi se točka s njegove desne strane.
• Root ima minimalno dvoje djece.

Zašto koristiti B+ Tree

Evo razloga za korištenje B+ stabla:

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

B+ stablo protiv B stabla

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

B+ Drvo	B Drvo
Tipke za pretraživanje mogu se ponavljati.	Tipke za pretraživanje ne mogu biti suvišne.
Podaci se spremaju samo na listovima čvorova.	I lisni čvorovi i unutarnji čvorovi mogu pohranjivati ​​podatke
Podaci pohranjeni na lisnom čvoru čine pretraživanje preciznijim i bržim.	Pretraživanje je sporo zbog podataka pohranjenih na listu i internim čvorovima.
Brisanje nije teško jer se element uklanja samo iz lisnog čvora.	Brisanje elemenata je kompliciran i dugotrajan proces.
Povezani lisni čvorovi čine pretragu učinkovitom i brzom.	Ne možete povezati lisne čvorove.

Traži OperaANJE

U B+ Tree-u, pretraživanje je jedan od najlakših postupaka za izvođenje i dobivanje brzih i točnih rezultata.

Primjenjiv je sljedeći algoritam pretraživanja:

• Da biste pronašli traženi zapis, morate izvršiti binarno pretraživanje na dostupnim zapisima u stablu.
• U slučaju točnog podudaranja s ključem za pretraživanje, korisniku se vraća odgovarajući zapis.
• U slučaju da točan ključ nije lociran pretraživanjem u roditeljskom, trenutnom ili lisnom čvoru, tada se korisniku prikazuje "poruka nije pronađena".
• Proces pretraživanja može se ponovno pokrenuti za bolje i točnije rezultate.

Traži Operacijski algoritam

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

Izlaz:

Podudarni skup zapisa prema točnom ključu prikazuje se korisniku; u suprotnom, korisniku se prikazuje neuspjeli pokušaj.

umetak OperaANJE

Za operaciju umetanja primjenjiv je sljedeći algoritam:

• 50 posto elemenata u čvorovima premješta se na novi list za pohranu.
• Roditelj novog lista točno je povezan s minimalnom vrijednošću ključa i novom lokacijom u stablu.
• Podijelite nadređeni čvor na više lokacija u slučaju da se u potpunosti iskoristi.
• Sada, za bolje rezultate, središnji ključ je povezan s čvorom najviše razine tog lista.
• Sve dok se čvor najviše razine ne pronađe, nastavite ponavljati proces objašnjen u gornjim koracima.

umetak Operacijski algoritam

1.	Even 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.  

Izlaz:

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

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

• Prvo, imamo 3 čvora, a prva 3 elementa, koji su 1, 4 i 6, dodani su na odgovarajućim mjestima 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 stvara desna hijerarhija stabla, a preostale vrijednosti podataka prilagođavaju se u skladu s tim imajući na umu primjenjiva pravila jednake ili veće od vrijednosti u odnosu na čvorove ključ-vrijednost s desne strane.

Izbrisati OperaANJE

Složenost postupka brisanja u B+ stablu nadilazi onu funkcionalnost umetanja i pretraživanja.

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

• Prvo, moramo locirati unos lista u stablu koji drži ključ i pokazivač. , izbrišite unos lista iz stabla ako list ispunjava točne uvjete za brisanje zapisa.
• U slučaju da lisni čvor zadovoljava samo zadovoljavajući faktor da je napola pun, tada je operacija dovršena; u suprotnom, listni čvor ima minimum unosa i ne može se izbrisati.
• Ostali povezani čvorovi s desne i lijeve strane mogu osloboditi sve unose i zatim ih premjestiti na list. Ako ovi kriteriji nisu ispunjeni, tada bi trebali kombinirati čvor lista i njegov povezani čvor u hijerarhiji stabla.
• Nakon spajanja lisnog čvora s njegovim susjedima s desne ili lijeve strane, unosi vrijednosti u lisnom čvoru ili povezanom susjedu koji pokazuju na čvor najviše razine se brišu.

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

• Prvo, točne lokacije elementa koji se brišu identificiraju se u stablu.
• Ovdje se element koji treba izbrisati može točno identificirati samo na razini lista, a ne na položaju indeksa. Dakle, element se može izbrisati bez utjecaja na pravila brisanja, što je vrijednost minimalnog ključa.

• U gornjem primjeru, moramo izbrisati 31 iz Stabla.
• Moramo locirati instance od 31 u indeksu i listu.
• Vidimo da je 31 dostupan i na razini čvora Index i Leaf. Stoga ga brišemo iz obje instance.
• Ali, moramo ispuniti indeks koji pokazuje na 42. Sada ćemo pogledati pravo dijete ispod 25 godina i uzeti minimalnu vrijednost i staviti je kao indeks. Dakle, budući da je 42 jedina prisutna vrijednost, to će postati indeks.

Izbrisati Operacijski algoritam

1) Start at the root and go up to 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

Izlaz:

Ključ "K" se briše, a ključevi se posuđuju od srodnih za podešavanje vrijednosti u n i njegovim nadređenim čvorovima ako je potrebno.

rezime

• B+ Drvo je samobalansirajuće struktura podataka za izvršavanje točnih i bržih postupaka pretraživanja, umetanja i brisanja podataka
• Lako možemo dohvatiti potpune podatke ili djelomične podatke jer prolazak kroz povezanu strukturu stabla to čini učinkovitim.
• Struktura B+ stabla raste i smanjuje se s povećanjem/smanjenjem broja pohranjenih zapisa.
• Pohranjivanje podataka na listove čvorova i naknadno grananje internih čvorova očito skraćuje visinu stabla, što smanjuje ulazne i izlazne operacije diska, što u konačnici troši puno manje prostora na uređajima za pohranu.