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