Mi az a B + fa?
A B + fa elsősorban a dinamikus indexelés többszintű megvalósításához használható. A B- Tree-hez képest a B + Tree csak a fa levélcsomópontjain tárolja az adatmutatókat, ezáltal a keresés pontosabb és gyorsabb.
Ebben a B + Tree oktatóanyagban megtudhatja:
- Mi az a B + fa?
- A B + fa szabályai
- Miért érdemes használni a B + Tree-t?
- B + fa vs. B fa
- Keresés művelet
- Helyezze be a műveletet
- Művelet törlése
A B + fa szabályai
Itt vannak a B + Tree alapvető szabályai.
- A leveleket az adatrekordok tárolására használják.
- A fa belső csomópontjaiban tárolódott.
- Ha a célkulcs értéke kisebb, mint a belső csomópont, akkor a bal oldalán lévő pont követhető.
- Ha a célkulcs értéke nagyobb vagy egyenlő a belső csomóponttal, akkor a jobb oldalán lévő pont követhető.
- A gyökérnek minimum két gyermeke van.
Miért érdemes használni a B + Tree-t?
Itt vannak okok a B + Tree használatára:
- A kulcsot elsősorban a keresés megkönnyítésére használják a megfelelő Leaf-be való irányítással.
- A B + Tree "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ória oldalán, mert nem rendelkeznek a belső csomópontokkal társított adatokkal. Ezért gyorsan hozzáférni fog a fa csomópont adataihoz.
- Az összes elem átfogó, teljes átvizsgálása egy fa, amelynek csak egy lineáris áthaladásra van szüksége, mivel a B + fa összes levélcsomópontja összekapcsolódik egymással.
B + fa vs. 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ő gombok megismételhetők. | A keresési kulcsok nem lehetnek feleslegesek. |
| Az adatokat csak a levélcsomópontok mentik. | A levélcsomópontok és a belső csomópontok egyaránt tárolhatnak adatokat |
| A levélcsomóponton tárolt adatok pontosabbá és gyorsabbá teszik a keresést. | A keresés a Leaf-en és a belső csomópontokon tárolt adatok miatt lassú. |
| A törlés nem nehéz, mivel egy elemet csak egy levélcsomópontból távolítanak el. | Az elemek törlése bonyolult és időigényes folyamat. |
| Az összekapcsolt levélcsomópontok hatékonyabbá és gyorsabbá teszik a keresést. | Nem kapcsolhatja össze a levélcsomópontokat. |
Keresés művelet
A B + Tree alkalmazásban a keresés az egyik legegyszerűbb eljárás, és gyors és pontos eredményeket érhet el belőle.
A következő keresési algoritmus alkalmazható:
- A szükséges rekord megtalálásához el kell végeznie a bináris keresést a Fa elérhető rekordjain.
- Pontos egyezés esetén a keresési kulccsal a megfelelő rekordot visszaküldi a felhasználónak.
- Abban az esetben, ha a pontos kulcsot nem a szülő, az aktuális vagy a levél csomópontban végzett keresés találja meg, akkor a "nem található üzenet" jelenik meg a felhasználó számára.
- A jobb és pontosabb eredmények érdekében a keresési folyamat újra lefuttatható.
Keresési műveleti algoritmus
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."
Kimenet :
A pontos kulcshoz beállított egyeztetett rekord megjelenik a felhasználó számára; ellenkező esetben egy sikertelen kísérlet jelenik meg a felhasználó számára.
Helyezze be a műveletet
A következő algoritmus alkalmazható a beszúrási művelethez:
- A csomópontokban lévő elemek 50 százaléka új levélbe kerül tárolásra.
- Az új Leaf szülője pontosan össze van kapcsolva a minimális kulcsértékkel és a fa új helyével.
- Ossza fel a szülőcsomópontot több helyre, hátha teljes mértékben kihasználja.
- A jobb eredmény elérése érdekében a középső kulcs hozzá van rendelve a Leaf legfelső szintű csomópontjához.
- Amíg a legfelső szintű csomópont nem található, folytassa a fenti lépésekben ismertetett folyamat ismétlését.
Helyezze be a műveleti algoritmust
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.
Kimenet :
Az algoritmus meghatározza az elemet, és sikeresen beilleszti a szükséges levélcsomópontba.
A fenti B + fa mintapéldát az alábbi lépések magyarázzák:
- Először 3 csomópontunk van, és az első 3 elem, amelyek 1, 4 és 6, hozzáadódnak a csomópontok megfelelő helyeihez.
- Az adatsor következő értéke 12, amelyet a fa részévé kell tenni.
- Ennek eléréséhez ossza fel a csomópontot, és adjon hozzá 6-at mutatóelemként.
- Most egy fa jobb oldali hierarchiája jön létre, és a fennmaradó adatértékeket ennek megfelelően állítják be, szem előtt tartva az alkalmazandó szabályokat, amelyek egyenlőek vagy nagyobbak, mint az értékek, a jobb oldali kulcsérték-csomópontokkal szemben.
Művelet törlése
A B + Tree törlési eljárásának bonyolultsága meghaladja a beszúrás és a keresés funkcióit.
A következő algoritmus alkalmazható egy elem törlésekor a B + fáról:
- Először meg kell keresnünk egy levél bejegyzést a fában, amely a kulcsot és a mutatót tartja. , törölje a levél bejegyzést a fáró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 megtelt kielégítő tényezőnek felel meg, akkor a művelet befejeződik; ellenkező esetben a Leaf csomópont minimális bejegyzéssel rendelkezik, és nem törölhető.
- A többi összekapcsolt csomópont a jobb és a bal oldalon felszabadíthatja a bejegyzéseket, majd áthelyezheti őket a Levélbe. Ha ezek a feltételek nem teljesülnek, akkor egyesíteniük kell a levélcsomópontot és a hozzá kapcsolt csomópontot a fahierarchiában.
- A levélcsomópont egyesítésével a jobb vagy bal oldali szomszédaival a levélcsomópont vagy a kapcsolt szomszéd értékeinek a legfelső szintű csomópontra mutató bejegyzéseit törli.
A fenti példa azt szemlélteti, hogyan lehet egy elemet eltávolítani a B + Tree-ből egy adott sorrendben.
- Először a törlendő elem pontos helyét határozza meg a fa.
- Itt a törlendő elem csak a levelek szintjén azonosítható pontosan, az index elhelyezésénél nem. Ezért az elem törölhető anélkül, hogy befolyásolná a törlés szabályait, ami a minimális kulcs értéke.
- A fenti példában 31-et törölnünk kell a fáról.
- Meg kell keresnünk a 31 példányt az Indexben és a Leafben.
- Láthatjuk, hogy a 31 mind Index, mind Leaf csomópont szinten elérhető. Ezért mindkét példányból töröljük.
- De ki kell töltenünk az indexet a 42-re mutatva. Most megvizsgáljuk a megfelelő 25 év alatti gyermeket, és a minimális értéket vesszük indexként. Tehát, mivel 42 az egyetlen jelen lévő érték, ez lesz az index.
Műveleti algoritmus törlése
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
Kimenet :
A "K" kulcs törlődik, és a kulcsokat testvérektől kölcsönözzük, hogy szükség esetén n és annak szülőcsomópontjainak értékeit módosítsuk.
Összegzés:
- A B + Tree egy önkiegyensúlyozó adatstruktúra, amely pontos és gyorsabb keresési, beillesztési és törlési eljárásokat hajt végre az adatokon
- Könnyen visszakereshetjük a teljes vagy a részleges adatokat, mert a csatolt faszerkezeten keresztül haladva hatékony.
- A B + fa szerkezete növekszik és zsugorodik a tárolt rekordok számának növekedésével / csökkenésével.
- Az adatok tárolása a levélcsomópontokon és 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 beviteli és kimeneti műveleteit, és végül sokkal kevesebb helyet foglal el a tárolóeszközökön.