B STROM v datové struktuře: Hledání, vkládání, mazání Příklad operace

Obsah:

Anonim

Co je to strom B?

B Tree je samovyvažující datová struktura založená na konkrétní sadě pravidel pro vyhledávání, vkládání a mazání dat rychlejším a paměťově efektivním způsobem. K dosažení tohoto cíle se při vytváření stromu B dodržují následující pravidla.

B-strom je speciální druh stromu v datové struktuře. V roce 1972 tuto metodu poprvé představil McCreight a společnost Bayer ji pojmenovala Výškově vyvážený m-way Search Tree. Pomůže vám zachovat data seřazená a povolené různé operace, jako je vkládání, vyhledávání a mazání, za kratší dobu.

V tomto výukovém programu B-Tree se naučíte:

  • Co je to strom B?
  • Proč používat B-Tree
  • Historie stromu B.
  • Vyhledávací operace
  • Operace vložení
  • Smazat operaci

Pravidla pro B-Tree

Tady 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“ (specifikovaný 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 primárně umístěna data.
  • 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ů, které může obsahovat kořenový uzel i jeho podřízené uzly, se vypočítá podle tohoto vzorce: 
    m - 1
    Například: 
    m = 4max keys: 4 - 1 = 3

  • Každý uzel, kromě root, musí obsahovat minimum klíčů 
    [m/2]-1
    Například: 
    m = 4min keys: 4/2-1 = 1
  • Maximální počet podřízených uzlů, které uzel může mít, se rovná jeho stupni, což je 
    m
  • Minimální počet dětí, které uzel může mít, je polovina řádu, což je m / 2 (hodnota stropu se vezme).
  • Všechny klíče v uzlu jsou seřazeny v rostoucím pořadí.

Proč používat B-Tree

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

  • Snižuje počet čtení na disku
  • Stromy B lze snadno optimalizovat, aby upravily jeho velikost (tj. Počet podřízených uzlů) podle velikosti disku
  • Jedná se o speciálně navrženou techniku ​​pro zpracování objemného množství dat.
  • Je to užitečný algoritmus pro databáze a souborové systémy.
  • Dobrá volba, když se rozhodnete pro čtení a zápis velkých bloků dat

Historie stromu B.

  • Data se na disk ukládají v blocích, tato data se po přenesení do hlavní paměti (nebo RAM) nazývají datová struktura.
  • V případě obrovských dat vyžaduje prohledání jednoho záznamu na disku přečtení celého disku; to zvyšuje čas a spotřebu hlavní paměti kvůli vysoké frekvenci přístupu na disk a velikosti dat.
  • Abychom to překonali, vytvoří se indexové tabulky, které uloží odkaz na záznam záznamů na základě bloků, ve kterých se nacházejí. Tím se drasticky sníží čas a spotřeba 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 Tree pro udržování dat seřazených samovyvažovacím způsobem.

Vyhledávací operace

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

Použije se následující algoritmus:

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

Operace vložení

Vzhledem k tomu, že B Tree je samovyvažovací strom, nemůžete 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 pro 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 rozdělí od prostředního prvku.
  • Střední prvek se stane rodičem pro další dva podřízené uzly.
  • Uzly musí znovu uspořádat klíče ve vzestupném pořadí.

SPROPITNÉ

O vkládacím algoritmu není pravda:

Vzhledem k tomu, že uzel je plný, proto se rozdělí a poté se vloží nová hodnota

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

  • Vyhledejte příslušnou pozici v uzlu pro klíč
  • Vložte klíč do cílového uzlu a zkontrolujte pravidla
  • Má uzel po vložení více než minimální počet klíčů, což je 1? V tomto případě ano. Zkontrolujte další pravidlo.
  • Má uzel po vložení více než maximální počet klíčů, což jsou 3? V tomto případě ne, není. To znamená, že strom B 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řenem ostatních dvou uzlů.
  • V případě sudého počtu klíčů bude střední uzel vybrán zkreslením vlevo nebo vpravo.

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

  • Uzel má méně než max. Klíčů
  • 1 je vložen vedle 3, ale je porušeno pravidlo vzestupného pořadí
  • Abychom to napravili, jsou klíče seřazeny

Podobně lze do uzlu snadno vložit 13 a 2, protože pro uzly splňují pravidlo menší než max. Klíče.

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

  • Uzel má klíče rovnající se maximálnímu počtu klíčů.
  • Klíč je vložen do cílového uzlu, ale porušuje pravidlo max klíčů.
  • Cílový uzel je rozdělen a prostřední klíč podle zkreslení 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 stromu B.

Smazat operaci

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

Platí následující algoritmus:

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

Pokud je cílový klíč v uzlu listu

  • Cíl je v listovém uzlu, více než min. Klíčů.
    • Smazáním tohoto nebude porušena vlastnost stromu B
  • Cíl je v listovém uzlu, má minimální klíčové uzly
    • Jeho smazáním bude porušena vlastnost stromu B
    • Cílový uzel si může vypůjčit klíč z bezprostředního levého uzlu nebo okamžitého pravého uzlu (sourozence)
    • Sourozenec řekne 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 odstraněna cílová hodnota
  • Cíl je v listovém uzlu, ale žádní sourozenci nemají více než minimální počet klíčů
    • Vyhledejte klíč
    • Sloučit 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ástupce v pořadí bude vybrán minimální klíč z jeho pravého podstromu
  • Pokud předchůdce cílového klíče v pořadí má více než min klíčů, pak může 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ástupce v pořadí.
  • Pokud mají předchůdce a následník v cílovém klíči klíče menší než min, sloučte předchůdce a následníka.

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

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

Nyní pochopíme operaci odstranění na příkladu.

Výše uvedený diagram zobrazuje různé případy operace mazání v B-stromu. Tento strom B 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. Vzhledem k tomu, že minimální a maximální počet klíčů pro jakýkoli uzel mohou mít 2, respektive 4.

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

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

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

  • Cílový uzel má klíče rovné minimálním klíčům, takže jej nelze přímo smazat, protože by tím došlo k porušení podmínek

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 inorder bude přenesena do nadřazeného objektu 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 od svého následného pořadí.

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

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

Viz postup odstranění takového klíče:

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

Smažte pseudo kód operace

private int removeBiggestElement(){if (root has no child)remove and return the last elementelse {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.

Souhrn:

  • B Tree je samovyvažující datová struktura pro lepší vyhledávání, vkládání a mazání dat z disku.
  • Strom B je regulován stanoveným stupněm
  • B Klíče a uzly stromu jsou seřazeny 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 vložení stromu B je poměrně podrobná, což nejprve najde vhodnou pozici vložení pro cílový klíč, vloží jej, vyhodnotí platnost stromu B proti různým případům a poté odpovídajícím způsobem restrukturalizuje uzly stromu B.
  • Operace odstranění stromu B nejprve hledá 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, sourozenců a rodiče.