unterschied zwischen B-Baum und B*-Baum

  • 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).

    Damn, here I was, minding my own business, just enjoying my second amendment rights, and you people have to FREAK out on me!

  • 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"

  • 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------ .

  • 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!