Další rozdíl mezi B-stromem a binárním stromem je ten, že B-tree 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 subtrees nebo nodes, zatímco v B-stromu může mít M no subtrees nebo nodes kde M je pořadí B-stromu.
Srovnávací graf
| Základ pro srovnání | B-strom | Binární strom |
|---|---|---|
| Základní omezení | Uzel může mít maximální počet M 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 při ukládání dat na disk. | Používá se, když jsou záznamy a data uložena v paměti RAM. |
| Výška stromu | log M N (kde m je pořadí stromu M-way) | log 2N |
| aplikace | Struktura dat indexování dat v mnoha DBMS. | Optimalizace kódu, Huffmanovo kódování atd. |
Definice B-stromu
B-strom je vyvážený strom M-way a také známý jako vyrovnaný třídící strom. Je to podobné binárnímu vyhledávacímu stromu, kde jsou uzly organizovány na základě inorder traversal. Prostorová složitost B-stromu je O (n). Složitost vložení a delece je O (log n).
Existují určité podmínky, které musí platit pro strom B:
- Výška stromu musí být 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 nejmenší počet dětí s výjimkou ponechání 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é číslo od 2 do maxima.
- Každý uzel má o jeden klíč méně než děti s maximálními klávesami M-1.
- Uspořádání klíčů je v určitém pořadí uvnitř uzlů. Všechny klíče v podstromu, které se nacházejí v levé části klíče, jsou předchůdci klíče a to, které se nachází napravo od klíče, se nazývají nástupci.
- V okamžiku vložení úplného uzlu se strom rozdělí na dvě části a klíč s mediánovou hodnotou se vloží do nadřazeného uzlu.
- Operace sloučení probíhá, když jsou uzly odstraněny.
Definice binárního stromu
Binární strom je stromová struktura, která může mít nejvýše dva ukazatele pro podřízené uzly. To znamená, že nejvyšší stupeň, který může mít uzel, je 2 a také uzel nula nebo jeden stupeň.
Existují určité varianty binárního stromu, jako je 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ý nekoncový terminál levý podstrom a pravý podstrom.
- Strom se nazývá úplný binární strom, když splňuje podmínku, že má 2 i uzly na každé úrovni, kde i je úroveň.
- Závitový binární soubor je binární strom, který se skládá buď z 0 no uzlů nebo 2 počtu uzlů.
Traversal techniky
Traversal stromu je jedna z nejčastějších operací prováděných na stromové datové struktuře, ve které každý uzel navštívil přesně jednou systematicky.
- Inorder- V tomto stromovém traversalu je levý podstrom navštěvován rekurzivně, poté je navštíven kořenový uzel a v posledním pravém podstromu je navštíven.
- Preorer - V tomto stromovém traversalu je kořenový uzel navštěvován v prvním a levém podstromu av posledním pravém podstromu.
- Postorder- Tato technika navštíví levý podstrom, poté pravý podstrom a poslední kořenový uzel.
Klíčové rozdíly Mezi B-stromem a binárním stromem
- V B-stromu může mít maximální počet podřízených uzlů non-terminálový uzel hodnotu M, kde M je pořadí B-stromu. Na druhé straně může mít binární strom maximálně 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í použití B-stromu je datová struktura kódování kódů v DBMS, naopak, binární strom je využíván pro optimalizaci kódu, kódování huffmanu atd.
- Maximální výška stromu B je log M N (M je pořadí stromu). Maximální výška binárního stromu je log 2 N (N je počet uzlů a základna je 2, protože je pro binární).
Závěr
B-strom se používá nad binárním a binárním vyhledávacím stromem. Hlavním důvodem je hierarchie paměti, kde je CPU připojeno k cache s vysokorychlostními kanály, zatímco CPU je připojeno k disku přes kanál s nízkou šíř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 uloženy na disku (velké a pomalé). Použití B-stromu namísto binárního stromu tak významně snižuje čas přístupu z důvodu vysokého faktoru větvení a snížené výšky stromu.
