B Strom v datové struktuře: Hledat, Vkládat, Smazat

Co je to strom B?

B strom je samovyvažovací 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. Aby se toho dosáhlo, je třeba při vytváření B-stromu dodržovat následující pravidla.

B-strom je speciální druh stromu v datové struktuře. Tuto metodu poprvé představili McCreight a Bayer v roce 1972 a pojmenovali ji Height Balanced M-way Search Tree (Výškově vyvážený m-cestný vyhledávací strom). Pomáhá zachovat seřazená data a umožňuje provádět 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 vytvoření B-stromu:

• Všechny listy budou vytvořeny na stejné úrovni.
• B-strom je určen číslem stupně, kterému se také říká „řád“ (určený externím aktérem, například programátorem), označovaným 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 klíčů, které může kořenový uzel a jeho podřízené uzly obsahovat, se vypočítá podle tohoto vzorce: m − 1, Například:

  m = 4
  max keys: 4 − 1 = 3

• Každý uzel, kromě kořene, 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 pro použití B-stromu:

• Snižuje počet čtení provedených na disku.
• B-stromy lze snadno optimalizovat tak, aby se jejich velikost (tj. počet podřízených uzlů) upravila 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 uložena v blocích. Tato data, když jsou přenesena do hlavní paměti (nebo RAM), se nazývají datová struktura.
• V případě obrovských dat vyžaduje hledání jednoho záznamu na disku čtení celého disku; to zvyšuje čas a spotřebu hlavní paměti kvůli vysoké frekvenci přístupů k disku a velikosti dat.
• Aby se tento problém překonal, vytvářejí se indexové tabulky, které ukládají reference záznamů na základě bloků, ve kterých se nacházejí. To drasticky snižuje čas a spotřebu 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í B-stromu pro uchováníping data seřazená samovyvažovacím způsobem.

Hledat Operavání

Vyhledávací operace je nejjednodušší operací na B-stromu. Používá se následující algoritmus:

• Nechť klíč (hodnota), která se má hledat, je „k“.
• Začněte hledat od kořene a rekurzivně přejděte dolů.
• Pokud je k menší než kořenová hodnota, prohledá se levý podstrom; pokud je k větší než kořenová hodnota, prohledá se 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í

Protože B-strom je samovyvažovací strom, nelze vynutit vložení klíče do libovolného 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í.

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ětší nebo roven minimálnímu počtu klíčů, který je 1? V tomto případě ano. Zkontrolujte následující pravidlo.
• Má uzel po vložení více klíčů než maximální počet, který je 3? V tomto případě ne, nemá. To znamená, že B-strom neporušuje žádná pravidla a vložení 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 pomocí levého nebo pravého zkreslení.

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

• Uzel má méně než maximum klíčů.
• Vedle čísla 3 je vložena 1, ale pravidlo vzestupného pořadí je porušeno.
• Aby se to napravilo, klíče jsou seřazeny.

Podobně lze do uzlu snadno vložit čísla 13 a 2, protože splňují pravidlo „méně než maximum klíčů“ 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ího počtu 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 mazání má více pravidel než operace vkládání a vyhledávání. Platí následující algoritmus:

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

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

• Target je v koncovém uzlu více než min klíčů. Smazáním této vlastnosti B stromu nebude narušena jeho vlastnost.
• Target je v koncovém uzlu a má min klíčových uzlů. Jeho smazání poruší vlastnost B-stromu.
• Cílový uzel si může vypůjčit klíč od bezprostředně levého uzlu nebo bezprostředně pravého uzlu (sourozence).
• Ř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řenesena do nadřazeného uzlu, maximální hodnota nadřazeného uzlu bude přenesena do cílového uzlu a cílová hodnota bude odebrána.
• Target je v koncovém uzlu, ale žádný ze sourozenců nemá více klíčů než minimální počet: hledání klíče, sloučení se sourozenci a minimálním počtem nadřazených uzlů, celkový počet klíčů bude nyní větší než min a cílový klíč bude nahrazen minimálním počtem klíčů z nadřazeného uzlu.

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

• Vyberte buď předchůdce v pořadí, nebo následníka 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ž minimální počet, může cílový klíč nahradit maximálním počtem předchůdce v pořadí.
• Pokud předchůdce cílového klíče v pořadí nemá více než min klíčů, hledejte 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 daném pořadí.
• Pokud má cíl po odstranění méně než min klíčů, pak si cílový uzel vypůjčí maximální hodnotu od svého sourozence prostřednictvím rodičovského uzlu sourozence.
• Cíl vezme maximální hodnotu rodiče, 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 jakýkoli uzel, je 3 a maximální počet podřízených uzlů, které může mít jakýkoli uzel, je 5. Minimální a maximální počet klíčů, které může jakýkoli uzel mít, je 2 a 4.

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

• Cílový uzel má cílový klíč k odstranění.
• Cílový uzel má více klíčů 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 nemůžeme přímo smazat, 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ě od 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 v pořadí bude přenesena do nadřazeného uzlu a nadřazený uzel 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ě od nástupce 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 cílovému uzlu poskytnout svůj klíč. Proto je nutné sloučení. Viz postup pro 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 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
    }
}

Výstup: Největší prvek je odstraněn z B-stromu.

Nejčastější dotazy