Rozdíl mezi B-stromem a binárním stromem
Obsah
- Srovnávací tabulka
- Definice B-stromu
- Vlastnosti B-stromu řádu M
- Definice binárního stromu
- Traversal Techniques
- Závěr
B-strom a binární strom jsou typy nelineární datové struktury. Ačkoli se tyto podmínky zdají být podobné, ale ve všech aspektech se liší. Binární strom se používá, když jsou záznamy nebo data uložena v RAM místo na disku, protože rychlost přístupu k RAM je mnohem vyšší než na disku. Na druhé straně, strom B se používá, když jsou data uložena na disku, snižuje přístupový čas snižováním výšky stromu a zvyšováním větví v uzlu.
Další rozdíl mezi B-stromem a binárním stromem je v tom, že B-strom musí mít všechny své podřízené uzly na stejné úrovni, zatímco binární strom takové omezení nemá. Binární strom může mít maximálně 2 podstromy nebo uzly, zatímco v B-stromu může mít M žádné podstromy nebo uzly, kde M je pořadí B-stromu.
- Srovnávací tabulka
- Definice
- Klíčové rozdíly
- Závěr
Srovnávací tabulka
| Základ pro srovnání | B-strom | Binární strom |
|---|---|---|
| Základní omezení | Uzel může mít maximálně M počet podřízených uzlů (kde M je pořadí stromu). | Uzel může mít maximálně 2 počet podstromů. |
| Použitý | Používá se, když jsou data uložena na disk. | Používá se, když jsou záznamy a data uložena v paměti RAM. |
| Výška stromu | logM N (kde m je pořadí stromu M-way) | log2 N |
| aplikace | Struktura dat indexování kódu v mnoha DBMS. | Optimalizace kódu, Huffmanova kódování atd. |
Definice B-stromu
B-strom je vyvážený strom M-way a také známý jako vyvážený strom setřídění. Je to podobné binárnímu vyhledávacímu stromu, kde jsou uzly uspořádány na základě inorderového průchodu. Složitost prostoru B-stromu je O (n). Časová náročnost vkládání a mazání je O (log n).
Pro strom B platí určité podmínky:
- Výška stromu musí ležet co nejmenší.
- Nad listy stromu by neměly být žádné prázdné podstromy.
- Listy stromu musí přijít na stejné úrovni.
- Všechny uzly by měly mít nejméně počet dětí s výjimkou uzlů.
Vlastnosti B-stromu řádu M
- Každý uzel může mít maximální počet M dětí a minimální počet dětí M / 2 nebo libovolný počet od 2 do maxima.
- Každý uzel má o jeden klíč méně než děti s maximálním počtem kláves M-1.
- Uspořádání klíčů je v konkrétním pořadí v uzlech. Všechny klíče v podstromu, které se nacházejí v levé části klíče, jsou předchůdci klíče a ty, které se nacházejí v pravé části klíče, se nazývají nástupci.
- V době vložení celého uzlu se strom rozdělí na dvě části a klíč se střední hodnotou se vloží do nadřazeného uzlu.
- Operace slučování probíhá, když jsou uzly vymazány.
Definice binárního stromu
Binární strom je stromová struktura, která může mít nejvýše dva ukazatele pro své podřízené uzly. To znamená, že nejvyšší stupeň, který může mít uzel, je 2 a mohl by existovat i nulový nebo jeden stupeň.
Existují určité varianty binárního stromu, například striktně binární strom, kompletní binární strom, rozšířený binární strom atd.
- Striktně binární strom je strom, ve kterém musí mít každý ne-terminálový uzel levou podstromu a pravou podstromu.
- Strom se nazývá Kompletní binární strom, pokud splňuje podmínku 2 i uzly na každé úrovni, kde i je úroveň.
- Threaded binary je binární strom, který se skládá buď z 0 bez uzlů, nebo ze 2 uzlů.
Traversal Techniques
Procházení stromů je jednou z nejčastějších operací prováděných na struktuře stromových dat, ve které každý uzel systematicky navštěvoval přesně jedenkrát.
- Inorder - V tomto stromovém průchodu je levý podstrom navštěvován rekurzivně, pak je navštíven kořenový uzel a v posledním pravém podstromu.
- Preorer - V tomto stromovém průchodu je kořenový uzel nejprve navštíven, poté vlevo podstrom a napravo vpravo podstrom.
- Postorder - Tato technika navštěvuje levý podstrom, potom pravý podstrom a na posledním kořenovém uzlu.
- V B-stromu je maximální počet podřízených uzlů, které může mít nekoncový uzel, M, kde M je pořadí B-stromu. Na druhé straně binární strom může mít nejvýše dva podstromy nebo podřízené uzly.
- B-strom se používá, když jsou data uložena na disku, zatímco binární strom se používá, když jsou data uložena v rychlé paměti, jako je RAM.
- Další oblastí aplikace pro B-strom je datová struktura indexování kódu v DBMS, naopak, binární strom se používá při optimalizaci kódu, huffmanově kódování atd.
- Maximální výška stromu B je logMN (M je pořadí stromu). Proti tomu je maximální výška binárního stromu log2N (N je počet uzlů a základna je 2, protože je pro binární).
Závěr
B-strom se používá přes binární a binární vyhledávací strom. Hlavním důvodem je hierarchie paměti, kde je CPU spojeno s mezipamětí s kanály s velkou šířkou pásma, zatímco CPU je připojeno k disku prostřednictvím kanálu s malou šířkou pásma. Binární strom se používá, když jsou záznamy uloženy v RAM (malé a rychlé) a B-strom se používá, když jsou záznamy ukládány na disk (velké a pomalé). Takže použití B-stromu místo Binárního stromu výrazně snižuje čas přístupu kvůli vysokému faktoru větvení a snížené výšce stromu.
