B+ DRVO: Pretraživanje, umetanje i brisanje Operama

Š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 listovima stabla, što proces pretraživanja čini preciznijim i bržim.

Pravila za B+ stablo

Evo osnovnih pravila za B+ stablo.

• Listovi se koriste za pohranjivanje zapisa podataka.
• Zapisi se pohranjuju u unutarnjim čvorovima Stabla.
• Ako je vrijednost ciljnog ključa manja od vrijednosti internog čvora, prati se pokazivač odmah s njegove lijeve strane.
• Ako je vrijednost ciljnog ključa veća ili jednaka internom čvoru, tada se prati pokazivač odmah desno od njega.
• Root ima minimalno dvoje djece.

Zašto koristiti B+ Tree

Evo razloga za korištenje B+ stabla:

• Ključevi se prvenstveno koriste za pomoć u pretraživanju usmjeravanjem na odgovarajući list.
• B+ stablo koristi "faktor ispune" za upravljanje povećanjem i smanjenjem u stablu.
• 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.
• Za sveobuhvatno skeniranje svih elemenata potreban je samo jedan linearni prolaz jer su svi listovi B+ stabla međusobno povezani.

B+ stablo protiv B stabla

Evo glavnih razlika između B+ stabla i B stabla.

Traži OperaANJE

U B+ stablu, pretraživanje je jedan od najlakših postupaka za izvršenje i daje brze i točne rezultate.

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 je točno 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 je, za bolje rezultate, središnji ključ 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. 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.

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ća mjesta u čvorovima.
• Sljedeća vrijednost u nizu podataka je 12, koju je potrebno učiniti dijelom Stabla.
• Da biste to postigli, podijelite čvor i dodajte 6 kao element pokazivača.
• Sada se stvara desna hijerarhija stabla, a preostale vrijednosti podataka se shodno tome prilagođavaju pomoću keeping imajte na umu primjenjiva pravila o jednakosti ili većoj 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 pronaći unos lista u Stablu koji sadrži ključ i pokazivač, a zatim izbrisati unos lista iz Stabla ako list ispunjava točne uvjete brisanja zapisa.
• U slučaju da listni čvor zadovoljava samo zadovoljavajući faktor da je napola ispunjen, operacija je dovršena; u suprotnom, listni čvor ima minimalan broj unosa i ne može se izbrisati.
• Ostali povezani čvorovi s desne i lijeve strane mogu osloboditi bilo koje unose i zatim ih premjestiti na list. Ako ovi kriteriji nisu ispunjeni, tada bi trebali kombinirati listni čvor i njegov povezani čvor u hijerarhiji stabla.
• Prilikom spajanja listnog čvora sa susjedima s desne ili lijeve strane, brišu se unosi vrijednosti u listnom čvoru ili povezanom susjedu koji upućuju na čvor najviše razine.

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 razini indeksa. Stoga se element može izbrisati bez utjecaja na pravila brisanja, koja su vrijednost minimalnog ključa.

• U gornjem primjeru, moramo izbrisati 31 iz Stabla.
• Moramo pronaći instance broja 31 u indeksu i listu.
• Možemo vidjeti da je 31 dostupan i na razini indeksnog i na razini listnog čvora. Stoga ga brišemo iz obje instance.
• Ali moramo popuniti indeks koji pokazuje na 42. Sada ćemo pogledati odgovarajuće dijete mlađe od 25 godina i uzeti minimalnu vrijednost te je postaviti kao indeks. Dakle, budući da je 42 jedina prisutna vrijednost, ona će postati indeks.

Izbrisati Operacijski algoritam

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

Izlaz: Ključ „K“ se briše, a ključevi se posuđuju od braće i sestara za podešavanje vrijednosti u n i njegovim roditeljskim čvorovima ako je potrebno.

Pitanja i odgovori