Inhoud

• Vergelijkingstabel
• Definitie van B-boom
• Eigenschappen van B-boom van orde M
• Definitie van binaire boom
• Traversale technieken
• Gevolgtrekking

B-boom en Binaire boom zijn de soorten niet-lineaire gegevensstructuur. Hoewel de termen op elkaar lijken, maar in alle opzichten verschillen. Een binaire boom wordt gebruikt wanneer de records of gegevens worden opgeslagen in het RAM-geheugen in plaats van op de schijf, omdat de toegangssnelheid van RAM veel hoger is dan de schijf. Aan de andere kant wordt B-boom gebruikt wanneer de gegevens op de schijf worden opgeslagen. Het vermindert de toegangstijd door de hoogte van de boom te verminderen en de vertakkingen in het knooppunt te vergroten.

Een ander verschil tussen de B-boom en de binaire boom is dat B-boom alle onderliggende knooppunten op hetzelfde niveau moet hebben, terwijl binaire boom niet zo'n beperking heeft. Een binaire boom kan maximaal 2 subbomen of knooppunten hebben, terwijl in B-boom M aantal subbomen of knopen kan hebben waarbij M de volgorde van de B-boom is.

1. Vergelijkingstabel
2. Definitie
3. Belangrijkste verschillen
4. Gevolgtrekking

Vergelijkingstabel

Basis voor vergelijking	B-tree	Binaire boom
Essentiële beperking	Een knooppunt kan maximaal M aantal onderliggende knooppunten hebben (waarbij M de volgorde van de boom is).	Een knooppunt kan maximaal 2 subbomen bevatten.
Gebruikt	Het wordt gebruikt wanneer gegevens op schijf worden opgeslagen.	Het wordt gebruikt wanneer records en gegevens worden opgeslagen in RAM.
Hoogte van de boom	logM N (waarbij m de volgorde van de M-way tree is)	log2 N
Toepassing	Gegevensstructuur voor code-indexering in veel DBMS.	Code-optimalisatie, Huffman-codering, enz.

Definitie van B-boom

Een B-boom is de gebalanceerde M-way tree en wordt ook wel de gebalanceerde sorteerboom genoemd. Het is vergelijkbaar met een binaire zoekboom waarbij de knooppunten zijn georganiseerd op basis van inorder traversal. De ruimtecomplexiteit van B-boom is O (n). De complexiteit van het invoegen en verwijderen is O (log n).

Er zijn bepaalde voorwaarden die voor een B-boom moeten gelden:

• De hoogte van de boom moet zo min mogelijk liggen.
• Boven de bladeren van de boom mogen er geen lege substructuren zijn.
• De bladeren van de boom moeten op hetzelfde niveau komen.
• Alle knooppunten moeten het minste aantal kinderen hebben, behalve knooppunten.

Eigenschappen van B-boom van orde M

• Elk knooppunt kan maximaal M aantal kinderen en minimaal M / 2 aantal kinderen hebben of een willekeurig aantal van 2 tot het maximum.
• Elke knoop heeft één sleutel minder dan kinderen met maximum M-1 sleutels.
• De indeling van de toetsen is in een bepaalde volgorde binnen de knooppunten. Alle sleutels in de subtree links van de sleutel zijn voorgangers van de sleutel en die aanwezig rechts van de sleutel worden opvolgers genoemd.
• Op het moment dat een volledige knoop wordt ingevoegd, splitst de boom zich in twee delen en wordt de sleutel met mediaanwaarde ingevoegd op de bovenliggende knoop.
• Het samenvoegen vindt plaats wanneer de knooppunten worden verwijderd.

Definitie van binaire boom

Een binaire boom is een boomstructuur die maximaal twee verwijzingen naar zijn onderliggende knooppunten kan hebben. Het betekent dat de hoogste graad die een knooppunt kan hebben 2 is en dat er ook een knooppunt van nul of één graad kan zijn.

Er zijn bepaalde varianten van een binaire boom zoals strikt binaire boom, volledige binaire boom, uitgebreide binaire boom, etc.

• De strikt binaire boom is een boom waarbij elke niet-terminale node een subtree en een juiste subtree moet hebben.
• Een boom wordt een complete binaire boom genoemd wanneer deze voldoet aan de voorwaarde van het hebben van 2 ^ik knooppunten op elk niveau waar ik het niveau is.
• Threaded binary is een binaire boom die bestaat uit 0 no knooppunten of 2 aantal knooppunten.

Traversale technieken

Tree traversal is een van de meest voorkomende bewerkingen op boomgegevensstructuur waarbij elk knooppunt precies één keer op een systematische manier werd bezocht.

• In volgorde - In deze boomverplaatsing wordt de linkersubboom recursief bezocht, vervolgens wordt het basisknooppunt bezocht en wordt in de laatste rechtersubboom bezocht.
• Preorer- In deze boomverplaatsing wordt eerst de wortelknoop bezocht en vervolgens linksonder en uiteindelijk rechtsonder.
• Postorder - Deze techniek bezoekt linker subtree dan rechter subtree en ten slotte root node.

1. In B-boom is het maximale aantal onderliggende knooppunten dat een niet-terminaal knooppunt kan hebben M waarbij M de volgorde van de B-boom is. Aan de andere kant kan een binaire boom maximaal twee substructuren of onderliggende knooppunten hebben.
2. B-tree wordt gebruikt wanneer gegevens op schijf worden opgeslagen, terwijl binaire boom wordt gebruikt wanneer gegevens worden opgeslagen in snel geheugen zoals RAM.
3. Een ander toepassingsgebied voor B-tree is de datastructuur van code-indexering in DBMS. Binaire tree wordt daarentegen gebruikt voor code-optimalisatie, huffman-codering, enz.
4. De maximale hoogte van een B-boom is log_MN (M is de volgorde van de boom). Daarentegen is de maximale hoogte van de binaire boom log₂N (N is het aantal knooppunten en base is 2 omdat het voor binair is).

Gevolgtrekking

De B-boom wordt gebruikt via binaire en binaire zoekboom. De belangrijkste reden hiervoor is de geheugenhiërarchie waar CPU is verbonden met de cache met de kanalen met hoge bandbreedte, terwijl CPU is verbonden met schijf via een kanaal met lage bandbreedte. Een binaire boom wordt gebruikt wanneer records worden opgeslagen in RAM (klein en snel) en B-tree wordt gebruikt wanneer records worden opgeslagen op schijf (groot en langzaam). Het gebruik van B-boom in plaats van Binaire boom vermindert dus de toegangstijd aanzienlijk vanwege de hoge vertakkingsfactor en de verminderde hoogte van de boom.