B+ FA: Keresés, beszúrás és törlés OperaPélda

Mi az a B+ fa?

A B+ fa elsősorban a dinamikus indexelés többszintű megvalósítására szolgál. A B-fához képest a B+ fa csak a fa levélcsomópontjain tárolja az adatmutatókat, ami pontosabbá és gyorsabbá teszi a keresést.

A B+ Tree szabályai

Íme a B+ Tree alapvető szabályai.

• A levelek adatrekordok tárolására szolgálnak.
• A Fa belső csomópontjaiban tárolva.
• Ha egy célkulcs értéke kisebb, mint a belső csomópont, akkor a közvetlenül a bal oldalán lévő pontot követi a rendszer.
• Ha egy célkulcs értéke nagyobb vagy egyenlő, mint a belső csomópont, akkor a közvetlenül a jobb oldalán lévő pontot követi a rendszer.
• A gyökérnek minimum két gyermeke van.

Miért használja a B+ Tree-t?

Íme, a B+ Tree használatának okai:

• A kulcsokat elsősorban a keresés elősegítésére használják a megfelelő levélre irányítva.
• A B+ Tree egy „kitöltési tényezőt” használ a fa növekedésének és csökkenésének kezelésére.
• A B+ fákban számos kulcs könnyen elhelyezhető a memórialapon, mivel nem rendelkeznek a belső csomópontokhoz tartozó adatokkal. Ezért gyorsan hozzáfér a levél csomópontján található faadatokhoz.
• Az összes elem átfogó, teljes vizsgálata egy olyan fa, amelynek csak egy lineáris lépésre van szüksége, mivel a B+ fa összes levélcsomópontja össze van kapcsolva egymással.

B+ fa kontra B fa

Itt vannak a fő különbségek a B+ fa és a B fa között

B+ fa	B Fa
A keresőbillentyűk ismételhetők.	A keresőbillentyűk nem lehetnek redundánsak.
Az adatok csak a levél csomópontjain kerülnek mentésre.	Mind a levél csomópontjai, mind a belső csomópontok tárolhatnak adatokat
A levél csomópontján tárolt adatok pontosabbá és gyorsabbá teszik a keresést.	A keresés lassú a Leaf-en és a belső csomópontokon tárolt adatok miatt.
A törlés nem nehéz, mivel egy elemet csak a levél csomópontjáról távolítanak el.	Az elemek törlése bonyolult és időigényes folyamat.
Az összekapcsolt levél csomópontok hatékonyabbá és gyorssá teszik a keresést.	A levél csomópontjai nem kapcsolhatók össze.

Keresés OperaCIÓ

A B+ Tree-ban a keresés az egyik legkönnyebben végrehajtható eljárás, és gyors és pontos eredményeket kaphat belőle.

A következő keresési algoritmus használható:

• A szükséges rekord megtalálásához végre kell hajtania a bináris keresés a Fában elérhető rekordokon.
• A keresési kulcs pontos egyezése esetén a megfelelő rekord visszakerül a felhasználóhoz.
• Abban az esetben, ha a keresés során a pontos kulcsot nem találja meg a szülő, aktuális vagy levél csomópontban, akkor a „nem található” üzenet jelenik meg a felhasználó számára.
• A keresési folyamat újra futtatható a jobb és pontosabb eredmények érdekében.

Keresés Operaciós algoritmus

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

teljesítmény:

A pontos kulccsal összeegyeztetett rekord megjelenik a felhasználó számára; ellenkező esetben a sikertelen kísérlet megjelenik a felhasználó számára.

betétlap OperaCIÓ

A következő algoritmus alkalmazható a beillesztési műveletre:

• A csomópontokban lévő elemek 50 százaléka új levélre kerül tárolás céljából.
• Az új levél szülője pontosan kapcsolódik a minimális kulcsértékhez és egy új helyhez a fában.
• Ossza fel a szülőcsomópontot több helyre arra az esetre, ha teljes mértékben kihasználná.
• A jobb eredmények érdekében a középső billentyűt az adott levél legfelső szintű csomópontjához rendeljük.
• Amíg a legfelső szintű csomópont nem található, folytassa a fenti lépésekben leírt folyamat iterációját.

betétlap Operaciós algoritmus

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.  

teljesítmény:

Az algoritmus meghatározza az elemet, és sikeresen beilleszti a kívánt levélcsomópontba.

A fenti B+ fa minta példáját az alábbi lépések magyarázzák:

• Először is 3 csomópontunk van, és az első 3 elemet, amelyek 1, 4 és 6, hozzáadjuk a csomópontok megfelelő helyeire.
• Az adatsor következő értéke a 12, amelyet a fa részévé kell tenni.
• Ennek eléréséhez osszuk fel a csomópontot, adjunk hozzá 6-ot mutatóelemként.
• Most létrejön egy fa jobb oldali hierarchiája, és a fennmaradó adatértékeket ennek megfelelően módosítja, szem előtt tartva az egyenlő vagy nagyobb értékekre vonatkozó szabályokat a jobb oldali kulcsérték csomópontokhoz képest.

töröl OperaCIÓ

A törlési eljárás összetettsége a B+ fában meghaladja a beszúrási és keresési funkciókat.

A következő algoritmus alkalmazható egy elem B+ fából való törlésekor:

• Először is meg kell találnunk egy levélbejegyzést a fában, amely a kulcsot és a mutatót tartja. , törölje a levél bejegyzést a fából, ha a levél pontosan megfelel a rekordtörlés feltételeinek.
• Abban az esetben, ha a levélcsomópont csak a félig megtelt faktort teljesíti, akkor a művelet befejeződött; egyébként a Leaf csomópont minimális bejegyzésekkel rendelkezik, és nem törölhető.
• A többi összekapcsolt csomópont a jobb és a bal oldalon kiürítheti a bejegyzéseket, majd áthelyezheti őket a Leafre. Ha ezek a feltételek nem teljesülnek, akkor kombinálniuk kell a fahierarchiában a levélcsomópontot és a hozzá kapcsolódó csomópontot.
• A levélcsomópont és a jobb vagy bal oldali szomszédokkal való egyesítésekor a levélcsomópontban vagy a legfelső szintű csomópontra mutató csatolt szomszédban lévő értékek bejegyzései törlődnek.

A fenti példa azt az eljárást szemlélteti, hogyan távolítható el egy elem egy adott sorrendű B+ fából.

• Először is, a törölni kívánt elem pontos helye azonosításra kerül a fában.
• Itt a törölni kívánt elem csak levélszinten azonosítható pontosan, indexelhelyezésnél nem. Így az elem törölhető a törlési szabályok befolyásolása nélkül, ami a minimális kulcs értéke.

• A fenti példában 31-et kell törölnünk a fából.
• Meg kell keresnünk a 31 példányait az Indexben és a Leafben.
• Láthatjuk, hogy a 31 Index és Leaf node szinten is elérhető. Ezért mindkét példányból töröljük.
• De ki kell töltenünk a 42-re mutató indexet. Most megnézzük a megfelelő 25 év alatti gyermeket, és vegyük a minimális értéket, és helyezzük el indexként. Tehát, mivel a 42 az egyetlen jelen lévő érték, ez lesz az index.

töröl Operaciós algoritmus

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

teljesítmény:

A „K” kulcs törlődik, és a kulcsokat a testvérektől kölcsönzik az n és a szülőcsomópontok értékeinek módosításához, ha szükséges.

Összegzésként

• A B+ Tree egy önkiegyensúlyozó adatszerkezet pontos és gyorsabb adatkeresési, beszúrási és törlési eljárások végrehajtásához
• Könnyen visszakereshetünk teljes adatokat vagy részadatokat, mert a csatolt fastruktúrán való átjárás hatékonysá teszi.
• A B+ fastruktúra növekszik és csökken a tárolt rekordok számának növekedésével/csökkenésével.
• Az adatok tárolása a levél csomópontjain, majd a belső csomópontok ezt követő elágazása nyilvánvalóan lerövidíti a fa magasságát, ami csökkenti a lemez bemeneti és kimeneti műveleteit, ami végső soron sokkal kevesebb helyet foglal el a tárolóeszközökön.