B+ TREE: Keresés, beszúrás és törlés OperaTIONS

Mi az a B+ fa?

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

A B+ Tree szabályai

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

• A levelek adatrekordok tárolására szolgálnak.
• A rekordok a fa belső csomópontjaiban tárolódnak.
• Ha egy célkulcs értéke kisebb, mint a belső csomópont értéke, akkor a tőle balra lévő mutatót követi a rendszer.
• Ha egy célkulcs értéke nagyobb vagy egyenlő, mint a belső csomópont értéke, akkor a tőle jobbra lévő mutatót követi a rendszer.
• A gyökérnek minimum két gyermeke van.

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

Íme néhány ok a B+ fa használatára:

• A kulcsokat elsősorban a keresés segítésére használják a megfelelő levélre való irányítással.
• Egy B+ fa 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.
• Egy átfogó, teljes átvizsgálás, amely az összes elemet letapogatja, mindössze egyetlen lineáris menetet igényel, mivel egy B+ fa összes levélcsomópontja össze van kapcsolva egymással.

B+ fa kontra B fa

Íme a B+ fa és a B fa közötti fő különbségek.

Keresés OperaCIÓ

Egy B+ fában a keresés az egyik legegyszerűbben végrehajtható eljárás, amely gyors és pontos eredményeket ad.

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

output: 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 összekapcsolódik a minimális kulcsértékkel és egy új hellyel a fában.
• Ossza fel a szülőcsomópontot több helyre arra az esetre, ha teljes mértékben kihasználná.
• Most, a jobb eredmények érdekében, a középső kulcsot az adott levél legfelső szintű csomópontjához társítjuk.
• 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. 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.

output: 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, van 3 csomópontunk, és az első 3 elemet, amelyek az 1, 4 és 6, a csomópontok megfelelő helyeire adjuk hozzá.
• Az adatsorozat következő értéke a 12, amelyet a fa részévé kell tenni.
• Ennek eléréséhez oszd el a csomópontot, és adj hozzá 6-ot mutatóelemként.
• Most egy fa jobb hierarchiája jön létre, és a fennmaradó adatértékeket ennek megfelelően módosítja a kee.ping tartsa szem előtt az alkalmazandó egyenlő vagy nagyobb, mint értékekre vonatkozó szabályokat a jobb oldali kulcs-érték csomópontokkal szemben.

Törölni 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 a fában egy olyan levélbejegyzést, amely a kulcsot és a mutatót tartalmazza, majd törölnünk kell a levélbejegyzést a fából, ha a levél megfelel a rekord törlésének pontos feltételeinek.
• Abban az esetben, ha a levélcsomópont csak a félig teltség kielégítő faktorát éri el, akkor a művelet befejeződik; ellenkező esetben a levélcsomópont minimális bejegyzésekkel rendelkezik, és nem törölhető.
• A jobb és bal oldali többi összekapcsolt csomópont kiüríthet bármilyen bejegyzést, majd áthelyezheti azokat a levélcsomópontra. Ha ezek a kritériumok nem teljesülnek, akkor a levélcsomópontot és a hozzá kapcsolódó csomópontot kombinálniuk kell a fa hierarchiában.
• Egy levélcsomópont jobb vagy bal oldali szomszédaival való egyesítésekor a legfelső szintű csomópontra mutató levélcsomópontban vagy a kapcsolódó szomszédban lévő értékbejegyzések törlődnek.

A fenti példa egy adott sorrendű B+ fából egy elem eltávolításának eljárását szemlélteti.

• 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örlendő elem csak levélszinten azonosítható pontosan, az indexpozíció alapján nem. Ezért az elem törölhető a törlési szabályok, azaz a minimális kulcs értéke befolyásolása nélkül.

• A fenti példában 31-et kell törölnünk a fából.
• Meg kell találnunk a 31 előfordulásait az Indexben és a Leafben.
• Láthatjuk, hogy a 31 mind az index, mind a levél csomópont szintjén 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 jobb oldali, 25 év alatti gyermeket, és a minimális értéket vesszük, és indexként helyezzük el. Tehát, mivel a 42 az egyetlen jelenlévő érték, az lesz az index.

Törölni Operaciós algoritmus

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

output: A „K” kulcsot törlik, és a testvércsomópontoktól kölcsönöznek kulcsokat az n és a szülőcsomópontok értékeinek szükség esetén történő módosításához.

GYIK