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

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
  

• 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

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.

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.

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.

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.

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.

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.

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íč

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:

• 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í.

• 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:

• 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č.