B STROM ve struktuře dat: Hledat, Vložit, Smazat OperaPříklad

Co je to strom B?

B strom je samovyvažující datová struktura založená na specifické sadě pravidel pro vyhledávání, vkládání a mazání dat rychlejším a paměťově efektivním způsobem. Abyste toho dosáhli, dodržujte následující pravidla pro vytvoření B stromu.

B-Strom je speciální druh stromu v datové struktuře. V roce 1972 tuto metodu poprvé představil McCreight a Bayer ji pojmenoval Height Balanced m-way Search Tree. Pomáhá vám zachovat roztříděná data a umožnit různé operace, jako je vkládání, vyhledávání a mazání v kratším čase.

Pravidla pro B-strom

Zde jsou důležitá pravidla pro vytváření B_Tree

  • Všechny listy budou vytvořeny na stejné úrovni.
  • B-Strom je určen počtem stupňů, který se také nazývá „řád“ (určený externím aktérem, jako je programátor), označovaný jako
    m

    dále. Hodnota

    m

    závisí na velikosti bloku na disku, na kterém jsou data primárně umístěna.

  • Levý podstrom uzlu bude mít menší hodnoty než pravá strana podstromu. To znamená, že uzly jsou také seřazeny ve vzestupném pořadí zleva doprava.
  • Maximální počet podřízených uzlů, kořenového uzlu i jeho podřízených uzlů, které může obsahovat, se vypočítá podle tohoto vzorce:
    m – 1

    Například:

    m = 4
    max keys: 4 – 1 = 3
    

Pravidla pro B-strom

  • Každý uzel, kromě root, musí obsahovat minimální počet klíčů
    [m/2]-1

    Například:

    m = 4
    min keys: 4/2-1 = 1
    
  • Maximální počet podřízených uzlů, které může uzel mít, se rovná jeho stupni, což je
    m
  • Minimální potomky, které může uzel mít, je polovina řádu, což je m/2 (bere se hodnota stropu).
  • Všechny klíče v uzlu jsou seřazeny ve vzestupném pořadí.

Proč používat B-Strom

Zde jsou důvody použití B-Stromu

  • Snižuje počet čtení provedených na disku
  • B stromy lze snadno optimalizovat tak, aby upravily svou velikost (to je počet podřízených uzlů) podle velikosti disku
  • Je to speciálně navržená technika pro manipulaci s objemným množstvím dat.
  • Je to užitečný algoritmus pro databáze a souborové systémy.
  • Dobrá volba, pokud jde o čtení a zápis velkých bloků dat

Historie B stromu

  • Data jsou na disku ukládána v blocích, tato data se po přenesení do hlavní paměti (neboli RAM) nazývají datová struktura.
  • V případě velkých dat vyžaduje prohledávání jednoho záznamu na disku čtení celého disku; to zvyšuje spotřebu času a hlavní paměti kvůli vysoké frekvenci přístupu k disku a velikosti dat.
  • K překonání tohoto problému jsou vytvořeny indexové tabulky, které ukládají referenční záznamy záznamů na základě bloků, ve kterých se nacházejí. To drasticky snižuje spotřebu času a paměti.
  • Protože máme obrovská data, můžeme vytvářet víceúrovňové indexové tabulky.
  • Víceúrovňový index lze navrhnout pomocí stromu B pro uchování dat tříděných způsobem samovyvažování.

Hledat Operavání

Vyhledávací operace je nejjednodušší operace na B stromu.

Je použit následující algoritmus:

  • Nechte klíč (hodnotu), který má být vyhledán, pomocí „k“.
  • Začněte hledat od kořene a rekurzivně přejděte dolů.
  • Pokud je k menší než kořenová hodnota, prohledejte levý podstrom, pokud je k větší než kořenová hodnota, prohledejte pravý podstrom.
  • Pokud má uzel nalezené k, jednoduše vraťte uzel.
  • Pokud k není v uzlu nalezeno, přejděte dolů k potomkovi pomocí většího klíče.
  • Pokud k není ve stromu nalezeno, vrátíme NULL.

Vložit Operavání

Vzhledem k tomu, že strom B je samovyrovnávací strom, nemůžete vynutit vložení klíče do jakéhokoli uzlu.

Platí následující algoritmus:

  • Spusťte operaci vyhledávání a najděte vhodné místo vložení.
  • Vložte nový klíč na správné místo, ale pokud má uzel již maximální počet klíčů:
  • Uzel se spolu s nově vloženým klíčem oddělí od prostředního prvku.
  • Prostřední prvek se stane rodičem pro další dva podřízené uzly.
  • Uzly musí znovu uspořádat klíče ve vzestupném pořadí.
TIP Následující není pravda o algoritmu vkládání:

Protože je uzel plný, rozdělí se a poté se vloží nová hodnota

Vložit Operavání

Ve výše uvedeném příkladu:

  • Vyhledejte klíč na příslušné pozici v uzlu
  • Vložte klíč do cílového uzlu a zkontrolujte pravidla
  • Má uzel po vložení více než rovno minimálnímu počtu klíčů, což je 1? V tomto případě ano, platí. Zkontrolujte další pravidlo.
  • Má uzel po vložení více než maximální počet klíčů, což jsou 3? V tomto případě ne, neplatí. To znamená, že strom B neporušuje žádná pravidla a vkládání je dokončeno.

Vložit Operavání

Ve výše uvedeném příkladu:

  • Uzel dosáhl maximálního počtu klíčů
  • Uzel se rozdělí a prostřední klíč se stane kořenovým uzlem zbývajících dvou uzlů.
  • V případě sudého počtu klíčů bude prostřední uzel vybrán levým nebo pravým předpětím.

Vložit Operavání

Ve výše uvedeném příkladu:

  • Uzel má méně než maximální počet klíčů
  • 1 se vkládá vedle 3, ale je porušeno pravidlo vzestupného pořadí
  • Aby se to napravilo, jsou klíče seřazeny

Podobně lze do uzlu snadno vložit 13 a 2, protože splňují pravidlo klíčů menší než maximální pro uzly.

Vložit Operavání

Ve výše uvedeném příkladu:

  • Uzel má klíče rovné maximálnímu počtu klíčů.
  • Klíč je vložen do cílového uzlu, ale porušuje pravidlo maximálních klíčů.
  • Cílový uzel je rozdělen a prostřední klíč podle předpětí vlevo je nyní rodičem nových podřízených uzlů.
  • Nové uzly jsou uspořádány vzestupně.

Podobně, na základě výše uvedených pravidel a případů, lze zbytek hodnot snadno vložit do B stromu.

Vložit Operavání

Vymazat Operavání

Operace odstranění má více pravidel než operace vkládání a vyhledávání.

Platí následující algoritmus:

  • Spusťte operaci vyhledávání a najděte cílový klíč v uzlech
  • Uplatňují se tři podmínky na základě umístění cílového klíče, jak je vysvětleno v následujících částech

Pokud je cílový klíč v listovém uzlu

  • Target je v listovém uzlu, více než min klíčů.
  • Smazáním to neporuší vlastnost B stromu
  • Target je v listovém uzlu, má min klíčových uzlů
  • Smazáním tohoto porušíte vlastnost B stromu
  • Target uzel si může půjčit klíč od okamžitého levého uzlu nebo okamžitého pravého uzlu (sourozenec)
  • Řekne sourozenec ano pokud má více než minimální počet klíčů
  • Klíč bude vypůjčen z nadřazeného uzlu, maximální hodnota bude převedena na nadřazený uzel, maximální hodnota nadřazeného uzlu bude přenesena do cílového uzlu a odebrána cílová hodnota
  • Target je v listovém uzlu, ale žádní sourozenci nemají více než min počet klíčů
  • Vyhledejte klíč
  • Sloučení se sourozenci a minimem nadřazených uzlů
  • Celkový počet klíčů bude nyní více než min
  • Cílový klíč bude nahrazen minimem nadřazeného uzlu

Pokud je cílový klíč v interním uzlu

  • Buď si vyberte, předchůdce v pořadí nebo následník v pořadí
  • V případě předchůdce v pořadí bude vybrán maximální klíč z jeho levého podstromu
  • V případě následníka v pořadí bude vybrán minimální klíč z jeho pravého podstromu
  • Pokud má předchůdce cílového klíče v pořadí více klíčů než min, může pouze nahradit cílový klíč maximem předchůdce v pořadí.
  • Pokud předchůdce cílového klíče v pořadí nemá více než min klíčů, vyhledejte minimální klíč následníka v pořadí.
  • Pokud mají předchůdce i následník cílového klíče v pořadí méně než min klíčů, sloučte předchůdce a následníka.

Pokud je cílový klíč v kořenovém uzlu

  • Nahraďte maximálním prvkem podstromu předchůdce v pořadí
  • Pokud má cíl po smazání méně než min klíčů, pak si cílový uzel vypůjčí maximální hodnotu od svého sourozence prostřednictvím rodiče sourozence.
  • Maximální hodnota rodiče bude převzata cílem, ale s uzly maximální hodnoty sourozence.

Nyní pochopme operaci odstranění na příkladu.

Vymazat  Operavání

Výše uvedený diagram zobrazuje různé případy operace odstranění v B-stromu. Tento B-strom je řádu 5, což znamená, že minimální počet podřízených uzlů, které může mít každý uzel, jsou 3, a maximální počet podřízených uzlů, které může každý uzel mít, je 5. Zatímco minimální a maximální počet klíčů kterýkoli uzel mohou mít jsou 2 a 4, resp.

Vymazat  Operavání

Ve výše uvedeném příkladu:

  • Cílový uzel má cílový klíč k odstranění
  • Cílový uzel má klíčů více než minimální počet klíčů
  • Jednoduše smažte klíč

Vymazat  Operavání

Ve výše uvedeném příkladu:

  • Cílový uzel má klíče rovné minimálnímu počtu klíčů, takže jej nelze přímo odstranit, protože by to porušilo podmínky

Nyní následující diagram vysvětluje, jak tento klíč odstranit:

Vymazat  Operavání

  • Cílový uzel si vypůjčí klíč od bezprostředního sourozence, v tomto případě předchůdce v pořadí (levý sourozenec), protože nemá žádného následníka v pořadí (pravý sourozenec).
  • Maximální hodnota předchůdce pořadí bude přenesena na nadřazený uzel a nadřazený prvek přenese maximální hodnotu do cílového uzlu (viz diagram níže)

Následující příklad ukazuje, jak odstranit klíč, který potřebuje hodnotu, ze svého následníka v pořadí.

Vymazat  Operavání

  • Cílový uzel si vypůjčí klíč od bezprostředního sourozence, v tomto případě následníka v pořadí (pravý sourozenec), protože jeho předchůdce v pořadí (levý sourozenec) má klíče rovné minimálnímu počtu klíčů.
  • Minimální hodnota následníka v pořadí se přenese na nadřazený a nadřazený přenese maximální hodnotu na cílový uzel.

V níže uvedeném příkladu cílový uzel nemá žádného sourozence, který by mohl poskytnout svůj klíč cílovému uzlu. Proto je nutné sloučení.

Podívejte se na postup odstranění takového klíče:

Vymazat  Operavání

  • Sloučit cílový uzel s libovolným z jeho bezprostředních sourozenců spolu s nadřazeným klíčem
  • Je vybrán klíč z nadřazeného uzlu, který se nachází mezi dvěma slučovanými uzly
  • Odstraňte cílový klíč ze sloučeného uzlu

Vymazat OperaPseudokód

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
    }
}

Výstup:

Největší prvek je odstraněn z B-stromu.

Shrnutí

  • B Tree je samovyvažující datová struktura pro lepší vyhledávání, vkládání a mazání dat z disku.
  • B Strom je regulován stanoveným stupněm
  • B Klíče a uzly stromu jsou uspořádány vzestupně.
  • Vyhledávací operace stromu B je nejjednodušší, která vždy začíná od kořene a začíná kontrolovat, zda je cílový klíč větší nebo menší než hodnota uzlu.
  • Operace vkládání stromu B je poměrně podrobná, která nejprve najde vhodnou pozici vložení pro cílový klíč, vloží jej, vyhodnotí platnost stromu B v různých případech a poté podle toho restrukturalizuje uzly stromu B.
  • Operace odstranění stromu B nejprve vyhledá cílový klíč, který má být odstraněn, odstraní jej, vyhodnotí platnost na základě několika případů, jako je minimální a maximální klíč cílového uzlu, sourozenci a rodič.