Hvad er et B + træ?
Et B + -træ bruges primært til implementering af dynamisk indeksering på flere niveauer. Sammenlignet med B-Tree gemmer B + Tree kun datapunkterne ved træets bladknudepunkter, hvilket gør søgningen mere nøjagtig og hurtigere.
I denne B + Tree-tutorial lærer du:
- Hvad er et B + træ?
- Regler for B + Tree
- Hvorfor bruge B + Tree
- B + træ vs. B træ
- Søgning
- Indsæt operation
- Slet handling
Regler for B + Tree
Her er vigtige regler for B + Tree.
- Blade bruges til at gemme dataposter.
- Det er gemt i træets interne noder.
- Hvis en målnøgleværdi er mindre end den interne knude, følges punktet lige til venstre side.
- Hvis en målnøgleværdi er større end eller lig med den interne knude, følges punktet lige til højre side.
- Roden har mindst to børn.
Hvorfor bruge B + Tree
Her er grunde til at bruge B + Tree:
- Nøgler bruges primært til at hjælpe søgningen ved at dirigere til det rette blad.
- B + Tree bruger en "udfyldningsfaktor" til at styre stigningen og faldet i et træ.
- I B + træer kan adskillige taster let placeres på hukommelsessiden, fordi de ikke har de data, der er knyttet til de indvendige noder. Derfor vil det hurtigt få adgang til trædata, der er på bladknuden.
- En omfattende fuld scanning af alle elementerne er et træ, der kun har brug for en lineær pasning, fordi alle bladknudepunkterne i et B + -træ er forbundet med hinanden.
B + træ vs. B træ
Her er de vigtigste forskelle mellem B + Tree vs. B Tree
| B + træ | B træ |
| Søgetaster kan gentages. | Søgetaster kan ikke være overflødige. |
| Data gemmes kun på bladknudepunkterne. | Både bladnoder og interne noder kan gemme data |
| Data gemt på bladnoden gør søgningen mere præcis og hurtigere. | Søgningen er langsom på grund af data gemt på Leaf og interne noder. |
| Sletning er ikke vanskelig, da et element kun fjernes fra en bladknude. | Sletning af elementer er en kompliceret og tidskrævende proces. |
| Tilknyttede bladknuder gør søgningen effektiv og hurtig. | Du kan ikke linke bladknuder. |
Søgning
I B + Tree er en søgning en af de nemmeste procedurer til at udføre og få hurtige og nøjagtige resultater af det.
Følgende søgealgoritme er anvendelig:
- For at finde den krævede post skal du udføre den binære søgning på de tilgængelige poster i træet.
- I tilfælde af et nøjagtigt match med søgetasten returneres den tilsvarende post til brugeren.
- Hvis den nøjagtige nøgle ikke findes ved søgningen i den overordnede, aktuelle eller bladnode, vises en "ikke fundet meddelelse" for brugeren.
- Søgningsprocessen kan køres igen for at få bedre og mere nøjagtige resultater.
Søg Operation Algoritme
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."
Output :
Den matchede post, der er indstillet til den nøjagtige nøgle, vises for brugeren; Ellers vises et mislykket forsøg for brugeren.
Indsæt operation
Følgende algoritme gælder for indsættelsesoperationen:
- 50 procent af elementerne i noderne flyttes til et nyt blad til opbevaring.
- Overordnet til det nye blad er nøjagtigt forbundet med minimumnøgleværdien og en ny placering i træet.
- Opdel overordnet knudepunkt i flere placeringer, hvis det bliver fuldt udnyttet.
- For bedre resultater er midttasten nu forbundet med topnoden på det blad.
- Indtil topnoden ikke findes, skal du fortsætte med at gentage processen, der er forklaret i ovenstående trin.
Indsæt operationsalgoritme
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.
Output :
Algoritmen bestemmer elementet og indsætter det med succes i den krævede bladknude.
Ovenstående B + Tree-eksempeleksempel forklares i nedenstående trin:
- For det første har vi 3 noder, og de første 3 elementer, der er 1, 4 og 6, tilføjes på passende placeringer i noderne.
- Den næste værdi i serien af data er 12, der skal gøres til en del af træet.
- For at opnå dette skal du dele noden, tilføje 6 som et pointerelement.
- Nu oprettes et højrehierarki af et træ, og de resterende dataværdier justeres i overensstemmelse hermed ved at huske på de gældende regler, der er lig med eller større end værdier i forhold til nøgleværdierne til højre.
Slet handling
Sletningsprocedurens kompleksitet i B + -træet overgår den for indsætnings- og søgefunktionalitet.
Følgende algoritme kan anvendes, når du sletter et element fra B + -træet:
- For det første skal vi finde en bladindgang i træet, der holder nøglen og markøren. , slet bladindgangen fra træet, hvis bladet opfylder de nøjagtige betingelser for sletning af poster.
- Hvis bladnoden kun opfylder den tilfredsstillende faktor for at være halvt fuld, er operationen afsluttet; Ellers har bladknudepunktet mindsteposter og kan ikke slettes.
- De andre sammenkædede noder til højre og venstre kan forlade alle poster og derefter flytte dem til bladet. Hvis disse kriterier ikke er opfyldt, skal de kombinere bladknuden og dens sammenkædede knude i træhierarkiet.
- Ved sammenfletning af bladnode med dens naboer til højre eller venstre slettes indtastninger af værdier i bladnoden eller den sammenkædede nabo, der peger på topnoden.
Eksemplet ovenfor illustrerer proceduren for at fjerne et element fra B + -træet i en bestemt rækkefølge.
- For det første identificeres de nøjagtige placeringer af det element, der skal slettes, i træet.
- Her kan elementet, der skal slettes, kun identificeres nøjagtigt på bladniveau og ikke ved indeksplaceringen. Derfor kan elementet slettes uden at påvirke reglerne for sletning, som er værdien af nøglen.
- I ovenstående eksempel skal vi slette 31 fra træet.
- Vi skal finde forekomsterne af 31 i Index og Leaf.
- Vi kan se, at 31 er tilgængelig på både indeks- og bladnodeniveau. Derfor sletter vi det fra begge forekomster.
- Men vi er nødt til at udfylde indekset, der peger på 42. Vi ser nu på det rigtige barn under 25 år og tager minimumsværdien og placerer den som et indeks. Så, da 42 er den eneste nuværende værdi, bliver det indekset.
Slet operation algoritme
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
Output :
Nøglen "K" slettes, og nøglerne lånes fra søskende til justering af værdier i n og dens overordnede noder, hvis det er nødvendigt.
Resumé:
- B + Tree er en selvbalancerende datastruktur til at udføre nøjagtig og hurtigere søgning, indsættelse og sletning af procedurer på data
- Vi kan nemt hente komplette eller delvise data, fordi det er effektivt at gennemgå den sammenkædede træstruktur.
- B + træstrukturen vokser og krymper med et stigning / fald i antallet af lagrede poster.
- Lagring af data på bladknudepunkterne og efterfølgende forgrening af interne knudepunkter forkorter tydeligvis træhøjden, hvilket reducerer diskinput- og outputoperationerne og i sidste ende forbruger meget mindre plads på lagerenhederne.