PDA

View Full Version : [FRAGE] - unterschied zwischen B-Baum und B*-Baum

lord
18-05-2002, 00:17
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. :D
ich danke euch im voraus!
Ciao
yrucrem
18-05-2002, 12:56
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).
GetStoopid
19-05-2002, 16:51
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?!
steve
19-05-2002, 16:58
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.
GetStoopid
21-05-2002, 13:16
aso... einfach grundsätzlich höhere ordnungen wählen um weniger ebenen zu durchforsten zu haben...?!
gck
21-05-2002, 14:30
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!
GetStoopid
21-05-2002, 14:56
naja so halbwegs... zumindest kann ich mir was drunter vorstellen, dank dir gck! =)