[FRAGE] - unterschied zwischen B-Baum und B*-Baum
Results 1 to 7 of 7
  1. #1

    Title
    Veteran
    Join Date
    Feb 2002
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Lightbulb unterschied zwischen B-Baum und B*-Baum

    hallo,
    kann mir wer von euch sagen was der unterschied zwischen einem B-Baum und einem B*-Baum ist? Wahrscheinlich ist es eh sehr simpel.
    ich danke euch im voraus!
    Ciao

  2. #2

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    Bei B*-Baeumen sind in den inneren Knoten nur die Schluessel der Datensaetze. Die Daten selbst sind immer in den Blaettern.

    Da man in den Zwischenknoten keine Datensaetze mehr speichen muss, kann man m (die Ordnung des Baumes) erhoehen, wodurch der baum Breiter wird (ie. man kommnt mit weniger Ebenen aus).

  3. #3

    Title
    Elite
    Join Date
    Jan 2002
    Location
    vienna/austria
    Posts
    471
    Thanks
    0
    Thanked 1 Time in 1 Post
    versteh nicht ganz was mit erhöhen der ordnung gemeint ist, wenn die ordnung 4 ist, dann bleibt sie doch 4... kann ja nicht nach dem einfügen des 7. elements zum bsp jetzt sagen, meine neue ordnung ist 5 oder 6 oder so...???
    und wie ich grundsätzlich die ordnung wähle ist ja meine sache... kann ja bei nem b-baum auch ordnung 5000 annehmen... wär halt nicht sehr sinnvoll, aber möglich?!
    "Von allen Dingen die mir verloren gegangen, hab ich am meisten an meinem Verstand gehangen"

  4. #4
    steve's Avatar
    Title
    Baccalaureus
    Join Date
    Jan 2002
    Location
    planet earth
    Posts
    539
    Thanks
    14
    Thanked 2 Times in 2 Posts
    yrucrem meint, dass durch das wegfallen der Werte in den Zwischenknoten (sind ja jetzt alle in den blättern) eigentlich ein höherer Baum notwendig wäre --> längere suchzeit. das kannst ausgleichen, indem du die ordnung erhöhst.
    wahrscheinlich nur begrenzt sinnvoll, würd ich sagen.
    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GAT d-(+) s++: a- C++$>+$ U++>+++ P++>+++ L+++ !E W++>$ !N K? w(--)@ !O !M V? PS+ PE++(-)> Y+ PGP(+) t---(-) !5 X R- tv-(--) b++>$ DI+ D+(++) G(+) e>++++* h-- r++ y++
    ------END GEEK CODE BLOCK------ .

  5. #5

    Title
    Elite
    Join Date
    Jan 2002
    Location
    vienna/austria
    Posts
    471
    Thanks
    0
    Thanked 1 Time in 1 Post
    aso... einfach grundsätzlich höhere ordnungen wählen um weniger ebenen zu durchforsten zu haben...?!
    "Von allen Dingen die mir verloren gegangen, hab ich am meisten an meinem Verstand gehangen"

  6. #6

    Title
    Elite
    Join Date
    Feb 2002
    Posts
    482
    Thanks
    0
    Thanked 0 Times in 0 Posts
    naja, eigentlich sinkt der Suchaufwand überhaupt nicht, wenn einfach die Ordnung des Baumes erhöht ie ihn breiter macht...

    der Vorteil ist ein anderer: die Knoten eines B-Baumes kann man sehr gut auf Festspeicher auslagern, und dann beim Suchen immer nur die Knoten nachladen, wo ich auch hinkomm: wenn jetzt in jedem Knoten mehr Elemente sind, d.h. es insgesamt weniger Knoten gibt, müssen auch weniger langsame Plattenzugriffe erfolgen und die Suche wird schneller (obwohl sies von der Algorithmik nicht ist, nur eben, weil das Laden von der Platte so lange dauern würde)...

    Wenn du einen B-Baum und einen B*-Baum mit denselben Elementen, aber größerer Ordnung, beide KOMPLETT im Speicher hast, dauert die Suche asymptotisch gleich lang, wenn aber jeder Knoten auf der Platte liegt, ist eben jener B-Baum schneller.
    Wenn ein B- und ein B*-Baum dieselbe Ordnung haben, sind beide in jedem Fall gleich schnell/langsam.

    hoffe, dass das so verständlich ist!

  7. #7

    Title
    Elite
    Join Date
    Jan 2002
    Location
    vienna/austria
    Posts
    471
    Thanks
    0
    Thanked 1 Time in 1 Post
    naja so halbwegs... zumindest kann ich mir was drunter vorstellen, dank dir gck! =)
    "Von allen Dingen die mir verloren gegangen, hab ich am meisten an meinem Verstand gehangen"

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •