Een ander verschil tussen de B-structuur en de binaire structuur is dat de B-tree al zijn onderliggende nodes op hetzelfde niveau moet hebben, terwijl de binaire tree niet zo'n beperking heeft. Een binaire boom kan maximaal 2 substructuren of knopen hebben, terwijl in de B-tree een M kan zijn van subbomen of knooppunten waar M de volgorde van de B-tree is.
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 in RAM worden opgeslagen. |
| Hoogte van de boom | log M N (waarbij m de volgorde is van de M-way-boom) | log 2 N |
| Toepassing | Code-indexering van gegevensstructuur in veel DBMS. | Code optimalisatie, Huffman-codering, etc. |
Definitie van B-tree
Een B-tree is de gebalanceerde M-way tree en staat ook bekend als de gebalanceerde sorteerboom. Het is vergelijkbaar met de binaire zoekboom waarin de knooppunten zijn georganiseerd op basis van in volgorde doorlopen. De ruimtecomplexiteit van de B-tree is O (n). Insertie- en deletietijd complexiteit is O (log n).
Er zijn bepaalde voorwaarden die moeten gelden voor een B-tree:
- De hoogte van de boom moet zo minimaal mogelijk liggen.
- Boven de bladeren van de boom mogen geen lege substructuren zijn.
- De bladeren van de boom moeten op hetzelfde niveau komen.
- Alle knooppunten moeten het minste aantal kinderen hebben behalve knooppunten verlaten.
Eigenschappen van B-boom van orde M
- Elk knooppunt kan een maximum aantal M-kinderen hebben en een minimum aantal M / 2-kinderen of een willekeurig getal van 2 tot het maximum.
- Elk knooppunt heeft één sleutel minder dan kinderen met maximum M-1-sleutels.
- De rangschikking van de sleutels bevindt zich in een bepaalde volgorde binnen de knooppunten. Alle toetsen in de substructuur die links van de toets aanwezig is, zijn de voorgangers van de sleutel, en de sleutels rechts van de sleutel worden opvolgers genoemd.
- Op het moment van het invoegen van een volledig knooppunt splitst de boom in twee delen en de sleutel met mediaanwaarde wordt ingevoegd op het bovenliggende knooppunt.
- De samenvoegbewerking vindt plaats wanneer de knooppunten worden verwijderd.
Definitie van binaire boom
Een binaire boom is een boomstructuur die maximaal twee aanwijzers voor de onderliggende knooppunten kan hebben. Het betekent dat de hoogste mate 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, enz.
- De strikt binaire boom is een boom waarbij elk niet-eindknooppunt de substructuur en de rechterboom moet hebben verlaten.
- Een boom wordt een Complete Binary-structuur genoemd als deze voldoet aan de voorwaarde dat hij 2 i-knooppunten heeft op elk niveau waarop i het niveau is.
- Genummerd binair getal is een binaire structuur die uit 0 knopen of 2 knopen bestaat.
Traversal Techniques
Tree traversal is een van de meest voorkomende bewerkingen die worden uitgevoerd in de structuur van boomgegevens, waarin elk knooppunt precies één keer op een systematische manier is bezocht.
- Inorder- In deze tree-traversal wordt de linkerboomboom recursief bezocht en vervolgens wordt het knooppunt bezocht en in de laatste rechterboom wordt de substructuur bezocht.
- Preorer- In deze tree traversal wordt het rootknooppunt eerst bezocht en vervolgens de linkerboom en ten slotte de rechterboom.
- Postorder- Deze techniek bezoekt de linkerboom, vervolgens de rechterboom en uiteindelijk het knooppunt.
Belangrijkste verschillen tussen B-boom en binaire boom
- In B-tree is het maximale aantal onderliggende knooppunten dat een niet-eindknooppunt kan hebben M, waarbij M de volgorde van de B-tree is. Aan de andere kant kan een binaire boom maximaal twee subbomen of onderliggende knooppunten hebben.
- B-tree wordt gebruikt wanneer gegevens worden opgeslagen op de schijf, terwijl de binaire structuur wordt gebruikt wanneer gegevens worden opgeslagen in een snel geheugen zoals RAM.
- Een ander toepassingsgebied voor de B-tree is de codecodering van de datastructuur in DBMS, in tegenstelling hiermee wordt de binaire tree gebruikt in code-optimalisatie, huffman-codering, enz.
- De maximale hoogte van een B-tree is log M N (M is de volgorde van de boom). Daarentegen is de maximale hoogte van binaire bomen log 2 N (N is het aantal knooppunten en basis is 2 omdat het voor binair is).
Conclusie
De B-tree wordt gebruikt voor binaire en binaire zoekbomen. De belangrijkste reden hierachter is de geheugenhiërarchie waarbij de CPU is verbonden met de cache met de hoge bandbreedtekanalen terwijl de CPU via een kanaal met lage bandbreedte met de schijf is verbonden. Een binaire structuur wordt gebruikt wanneer records worden opgeslagen in RAM (klein en snel) en B-tree worden gebruikt wanneer records worden opgeslagen op schijf (groot en langzaam). Dus, het gebruik van B-tree in plaats van Binary tree vermindert de toegangstijd aanzienlijk vanwege de hoge vertakkingsfactor en verminderde hoogte van de boom.
