B FA az adatstruktúrában: Keresés, beszúrás, törlés Operaciós példa

A B-Tree szabályai

Itt vannak a B_Tree létrehozásának fontos szabályai

• Minden levél ugyanazon a szinten lesz létrehozva.
• A B-fát számos fokozat határozza meg, amelyet „rendnek” is neveznek (egy külső szereplő, például egy programozó határozza meg), ún.

  m

  tovább. Az értéke

  m

  a blokk méretétől függ azon a lemezen, amelyen elsősorban az adatok találhatók.

• A csomópont bal oldali részfájának értéke kisebb, mint a részfa jobb oldalának. Ez azt jelenti, hogy a csomópontok is növekvő sorrendben vannak rendezve balról jobbra.
• A gyermekcsomópontok, a gyökércsomópontok és a gyermekcsomópontok maximális számát a következő képlettel számítjuk ki:

  m – 1

  Például:

  m = 4
  max keys: 4 – 1 = 3
  

• A root kivételével minden csomópontnak minimális kulcsot kell tartalmaznia

  [m/2]-1

  Például:

  m = 4
  min keys: 4/2-1 = 1
  

• Egy csomópont gyermekcsomópontjainak maximális száma megegyezik a fokával, ami az

  m

• Egy csomópont minimális gyermekei a sorrend fele, ami m/2 (a plafonértéket veszik).
• A csomópont összes kulcsa növekvő sorrendben van rendezve.

Miért használja a B-tree-t?

Íme, a B-Tree használatának okai

• Csökkenti a lemezen végzett olvasások számát
• B A fák könnyen optimalizálhatók, hogy méretüket (vagyis a gyermek csomópontok számát) a lemez méretéhez igazítsák
• Ez egy speciálisan nagy mennyiségű adat kezelésére tervezett technika.
• Ez egy hasznos algoritmus adatbázisokhoz és fájlrendszerekhez.
• Jó választás, ha nagy adattömbök olvasására és írására van szükség

A B fa története

• Az adatok a lemezen blokkokban tárolódnak, ezeket az adatokat a főmemóriába (vagy RAM-ba) adatstruktúrának nevezzük.
• Hatalmas adatmennyiség esetén egy rekord keresése a lemezen a teljes lemez olvasását igényli; ez növeli az idő- és főmemória-felhasználást a magas lemezelérési gyakoriság és adatméret miatt.
• Ennek kiküszöbölésére indextáblákat hoznak létre, amelyek elmentik a rekordok rekordhivatkozását azon blokkok alapján, amelyekben vannak. Ez drasztikusan csökkenti az idő- és memóriafelhasználást.
• Mivel hatalmas adatokkal rendelkezünk, többszintű indextáblákat is készíthetünk.
• Többszintű index tervezhető a B fa használatával, hogy az adatok önkiegyensúlyozó módon legyenek rendezve.

Keresés OperaCIÓ

A keresési művelet a legegyszerűbb művelet a B fán.

A következő algoritmust alkalmazzuk:

• Hagyja, hogy a keresendő kulcs (az érték) „k” legyen.
• Kezdje el a keresést a gyökértől, és rekurzívan haladjon lefelé.
• Ha k kisebb, mint a gyökérérték, keressen a bal oldali részfában, ha k nagyobb, mint a gyökérérték, keressen a jobb oldali részfában.
• Ha a csomópont rendelkezik a talált k értékkel, egyszerűen adja vissza a csomópontot.
• Ha a k nem található a csomópontban, lépjen le a gyermekhez egy nagyobb kulccsal.
• Ha k nem található a fában, akkor NULL-t adunk vissza.

betétlap OperaCIÓ

Mivel a B Tree egy önkiegyensúlyozó fa, nem kényszerítheti be a kulcsot bármelyik csomópontba.

A következő algoritmus érvényes:

• Futtassa a keresési műveletet, és keresse meg a megfelelő beszúrási helyet.
• Illessze be az új kulcsot a megfelelő helyre, de ha a csomópontnak már van maximális számú kulcsa:
• A csomópont az újonnan beillesztett kulccsal együtt kiválik a középső elemből.
• A középső elem lesz a másik két gyermek csomópont szülője.
• A csomópontoknak újra kell rendezniük a kulcsokat növekvő sorrendben.

TIPP	A következő nem igaz a beillesztési algoritmusra: Mivel a csomópont megtelt, ezért feldarabolódik, majd új érték kerül beillesztésre

A fenti példában:

• Keresse meg a kulcs megfelelő pozícióját a csomópontban
• Illessze be a kulcsot a célcsomópontba, és ellenőrizze a szabályokat
• A beillesztés után a csomópontnak több kulcsa van, mint egy minimális számú kulcs, ami 1? Ebben az esetben igen, így van. Ellenőrizze a következő szabályt.
• A beillesztés után a csomópontnak több kulcsa van a maximális számnál, ami 3? Ebben az esetben nem, nem. Ez azt jelenti, hogy a B fa nem sért meg semmilyen szabályt, és a beillesztés befejeződött.

A fenti példában:

• A csomópont elérte a kulcsok maximális számát
• A csomópont felosztódik, és a középső kulcs lesz a többi két csomópont gyökércsomópontja.
• Páros számú kulcs esetén a középső csomópont bal vagy jobb oldali előfeszítéssel lesz kiválasztva.

A fenti példában:

• A csomópontnak kevesebb, mint max kulcsa van
• Az 1-es a 3 mellé kerül, de megsérti a növekvő sorrend szabályát
• Ennek javítása érdekében a kulcsok rendezve vannak

Hasonlóképpen, a 13 és a 2 könnyen beilleszthető a csomópontba, mivel a csomópontokra vonatkozó max. kulcsnál kevesebb szabályt teljesítenek.

A fenti példában:

• A csomópont kulcsai megegyeznek a maximális kulcsokkal.
• A kulcs be van illesztve a célcsomópontba, de megsérti a max kulcsok szabályát.
• A célcsomópont fel van osztva, és a bal oldali torzítású középső kulcs mostantól az új gyermek csomópontok szülője.
• Az új csomópontok növekvő sorrendben vannak elrendezve.

Hasonlóképpen, a fenti szabályok és esetek alapján a többi érték könnyen beilleszthető a B fába.

Törölni OperaCIÓ

A törlési műveletnek több szabálya van, mint a beszúrási és keresési műveleteknek.

A következő algoritmus érvényes:

• Futtassa a keresési műveletet, és keresse meg a célkulcsot a csomópontokban
• Három feltétel érvényes a célkulcs helye alapján, a következő szakaszokban ismertetettek szerint

Ha a célkulcs a levélcsomópontban van

• Target a levél csomópontban van, több mint min kulcs.
• Ennek törlése nem sérti a B Tree tulajdonát
• Target levél csomópontban van, minimum kulcscsomópontjai vannak
• Ennek törlése sérti a B Tree tulajdonát
• Target A csomópont kölcsönözheti a kulcsot a közvetlen bal vagy a közvetlen jobb oldali csomóponttól (testvér)
• A testvér azt fogja mondani Igen ha a minimálisnál több kulcsot tartalmaz
• A kulcs a szülőcsomóponttól lesz kölcsönözve, a maximális érték átkerül egy szülőbe, a szülőcsomópont maximális értéke átkerül a célcsomópontba, és eltávolítja a célértéket
• Target a levél csomópontjában van, de egyetlen testvérnek sem van minnél több kulcsa
• Kulcs keresése
• Egyesítse a testvérekkel és a minimális szülőcsomópontokkal
• Az összes kulcs most több mint min
• A célkulcsot a rendszer egy szülőcsomópont minimumára cseréli

Ha a célkulcs egy belső csomópontban van

• Vagy válasszon, sorrendben elődje vagy sorrendi utódja
• A sorrendbeli előd esetén a bal oldali részfából a maximális kulcs kerül kiválasztásra
• Soron belüli utód esetén annak jobb oldali részfájából a minimális kulcs kerül kiválasztásra
• Ha a célkulcs sorrendi elődjének több mint a min kulcsa van, csak akkor tudja a célkulcsot a sorrendben elődjének max értékére cserélni.
• Ha a célkulcs sorrendi elődjének nem több mint min kulcsa van, keresse meg a sorrendi utód minimális kulcsát.
• Ha a célkulcs sorrendi elődjének és utódjának egyaránt kevesebb, mint min kulcsa van, akkor egyesítse az elődöt és az utódot.

Ha a célkulcs gyökércsomópontban van

• Cserélje le a sorrendben lévő előd részfa maximális elemére
• Ha a törlés után a célnak kevesebb mint min kulcsa van, akkor a célcsomópont maximális értéket kölcsönöz a testvérétől a testvér szülőjén keresztül.
• A szülő max értékét egy cél veszi fel, de a testvér max értékének csomópontjaival.

Most értsük meg a törlési műveletet egy példával.

A fenti diagram a törlési műveletek különböző eseteit mutatja be egy B-fában. Ez a B-fa 5-ös rendű, ami azt jelenti, hogy minden csomópont gyermekcsomópontjainak minimális száma 3, és a csomópontok gyermekcsomópontjainak maximális száma 5. Míg a kulcsok minimális és maximális száma minden csomópontban lehet 2, illetve 4.

A fenti példában:

• A célcsomópont rendelkezik a törölni kívánt célkulccsal
• A célcsomópontnak több kulcsa van, mint a minimális kulcs
• Egyszerűen törölje a kulcsot

A fenti példában:

• A célcsomópont kulcsai megegyeznek a minimális kulcsokkal, ezért nem törölhető közvetlenül, mert megsérti a feltételeket

Most a következő diagram leírja, hogyan törölheti ezt a kulcsot:

• A célcsomópont kölcsönkér egy kulcsot a közvetlen testvértől, ebben az esetben a sorrendbeli elődtől (bal oldali testvértől), mert nincs sorrendbeli utódja (jobb testvér)
• Az inorder előd maximális értéke átkerül a szülőre, a szülő pedig a maximális értéket a célcsomópontra (lásd az alábbi diagramot)

A következő példa bemutatja, hogyan lehet törölni egy kulcsot, amelynek értékre van szüksége a sorrendi utódából.

• A célcsomópont kölcsönkér egy kulcsot a közvetlen testvértől, ebben az esetben a sorrendi utódtól (jobb testvér), mivel a sorrendben lévő elődjének (bal oldali testvérének) kulcsai megegyeznek a minimális kulcsokkal.
• A sorban álló utód minimális értéke átkerül a szülőre, a szülő pedig a maximális értéket a célcsomópontra.

Az alábbi példában a célcsomópontnak nincs olyan testvére, amely megadhatná a kulcsát a célcsomópontnak. Ezért összevonásra van szükség.

Tekintse meg az ilyen kulcsok törlésének menetét:

• Egyesítse a célcsomópontot bármelyik közvetlen testvérével a szülőkulccsal együtt
• A szülőcsomópont kulcsa van kiválasztva, amely a két egyesülő csomópont között testvérek
• Törölje a célkulcsot az egyesített csomópontból

Törölni Operation Pseudo Code

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

teljesítmény:

A legnagyobb elem törlődik a B-fából.

Összegzésként

• A B Tree egy önkiegyensúlyozó adatstruktúra az adatok jobb kereséséhez, beillesztéséhez és törléséhez a lemezről.
• B A fát a megadott fokozat szabályozza
• B A fa kulcsai és csomópontjai növekvő sorrendben vannak elrendezve.
• A B Tree keresési művelete a legegyszerűbb, amely mindig a gyökértől indul, és elkezdi ellenőrizni, hogy a célkulcs nagyobb vagy kisebb-e a csomópont értékénél.
• A B Tree beszúrási művelete meglehetősen részletes, amely először megtalálja a megfelelő beillesztési pozíciót a célkulcshoz, beszúrja, kiértékeli a B fa érvényességét a különböző esetekhez képest, majd ennek megfelelően átstrukturálja a B fa csomópontjait.
• A B Tree törlési művelete először megkeresi a törölni kívánt célkulcsot, törli, és több eset alapján értékeli az érvényességet, mint például a célcsomópont, a testvérek és a szülő minimális és maximális kulcsa.