View Full Version : [Frage] Graphik B* Baum
hi leute
ich hab in einigen Vorlesungen gefehlt und glaube, dass in einer VO ein Beispiel für einen B* Baum gezeichnet wurde. Es wäre mir eine große Hilfe, wenn ihn mir wer einscannen/zeichnen könnte :bounce:
BITTE
wird ganz genau wie ein b_Baum gezeichnet ,der einzige unterschied ist das der b*baum die info nur in den blättern stehen hat und der b_baum hat sie auch in den anderen knoten
aber für das konstruieren des baumes ist das nicht wichtig
mfg hagbard
p.s: wenns geht kannst mal schauen ob du eine antwort auf mein mst posting hast wäre echt cool
eine anmerkung noch. du musst aber natürlich schauen, daß wenn du teilst, der datensatz natürlich auch noch in den blättern bleibt. teilst du z.B. den Knoten (3,5,7) für m=3 so wandert 5 als Schlüssel nach oben. 5 der als [edit] Referenz/Verweis zum Datensatz [edit] im Blatt war muss aber klarerweise auch noch im Blatt bleiben.
Grüße,
Wolti
Nein da verwechselst Du etwas. Der Knoten (3, 5, 7) ist auch in einem normalen B-Baum _kein_ Blatt sondern ein innerer Knoten und er hat noch vier Kinder in denen halt nichts drinnen steht. Das sind dann die Blaetter.
In einem B*-Baum waeren eben diese Kinder nicht leer, sondern enthielten die Datensaetze zu den Schluesseln.
das habe ich nicht ganz verstanden, wie ich den dann finden sollte.
Ich meine ich habe sagen wir, sagen wir in der Wurzel den 5 er stehen, und suche jetzt den datensatz dazu.... wie komm ich zu dem?
(wenn der z.B. in einem Blatt irgendwo im Unterbaum hängt?)
ist jetzt aber nimma so wichtig... glaub ich überlebe auch ohne das wissen
Naja, die verteilt man schon nach einem System, so dass man spaeter auch wieder was findet. Zum Beispiel: geh direkt vor dem Schluessel nach unten und nimm so lange den "rechtesten" Pfad nach unten bis Du zu einem Blatt kommst. So muss man, nachdem man den Schluessel gefunden hat, nur noch ein paar Ebenen im Baum nach unten (wobei man aber keine Vergleiche mehr braucht, sondern nur noch den Pointern folgt) und hat seinen Datensatz. Und da man die Datensaetze ja genau deshalb in die Blaetter speichert, damit man die Orndung erhoehen kann, wird der Baum ja nicht so hoch.
Nein da verwechselst Du etwas. Der Knoten (3, 5, 7) ist auch in einem normalen B-Baum _kein_ Blatt sondern ein innerer Knoten und er hat noch vier Kinder in denen halt nichts drinnen steht. Das sind dann die Blaetter.
In einem B*-Baum waeren eben diese Kinder nicht leer, sondern enthielten die Datensaetze zu den Schluesseln.
Dann habe ich aber dazu eine Frage.
m = 3
(3,"A")
(4,"B")
(5,"C")
(6,"D")
( 3 ) => ( 3 4 ) => ( 3 4 5 )
/ / / / / /
"A" "A" "B" "A" "B" "C"
Wir müssen jetzt hier auf jedenfall teilen bei unserere vorgebenen
Ordnung. Wir teilen in der Mitte und wollen den Schlüssel 4 nach
oben ziehen. Es gibt nun zwei Möglichkeiten wenn man das meiner
Meinung nach nach deiner Variante macht.
1) Wie ich deine verstanden habe,
( 4 )
/ \
/ \
( 3 ) ( 5 )
/ \ /
"A" "B" "C"
Was mich zu der Frage bringt, wie du sicher jetzt den zu Schlüssesl
4 gehörigen Datensatz finden willst ?
Kopierst du aber den Schlüssel nur nach oben rauf, und läßt ihn
unten, so kannst du danach, wenn du noch in dem letzten inneren
Knoten bist runtergehen, dort findest du den Schlüssel 4 und dann
weisst im welchen Unterast sicher der Datensatz befindet.
Meine Lösung mit dem kopieren des Schlüssel führt zu einem gültigen
B*-Baum ohne das oben genannte Problem.
:edit: Zusammenfassend. Ich halte eine Kopie des Schlüssel bei dem geteilt wurde nach oben
durchaus für sinnvoll.
PS: Anbei als Referenz und der geringen Ausführung dieses Kapitels
im Skriptum. http://wwwagr.informatik.uni-kl.de/~tombers/ESSY2/ESSY2_I04_2.pdf
hab schnell was im photoshop gekritzelt ;)
hope that helps, die theorie dazu hat yrucrem ja schon gepostet :)
thx, kenn mich jetzt aus glaub ich.. :D
danke hat mir sehr geholfen :)
thnx, sollte geholfen haben :verycool:
hoffe bei einem Baum mit m=11 komm ich dann nicht durcheinander :ausheck:
Nein da verwechselst Du etwas. Der Knoten (3, 5, 7) ist auch in einem normalen B-Baum _kein_ Blatt sondern ein innerer Knoten und er hat noch vier Kinder in denen halt nichts drinnen steht. Das sind dann die Blaetter.
In einem B*-Baum waeren eben diese Kinder nicht leer, sondern enthielten die Datensaetze zu den Schluesseln.
Hallo,
will hier nicht der nitpicker sein- du hast es wahrscheinlich uebersehen, und ich sag's nur, damit's nicht sonstwen verwirrt: Aber der Knoten (3, 5, 7) fuer m=3 existiert in einem B-Baum entweder nur kurzzeitig oder gar nicht- fuer m=3 haben wir ja max. 2 Schluessel in einem Knoten, und max. 3 Kinder.
Mit den Blaettern hast du natuerlich recht, obwohl das im Skriptum nur anfangs erwaehnt wird und dann zur Analyse und Diskussion von B-Baeumen durchaus der Begriff "Blaetter" fuer die (inneren) Knoten in der letzten Ebene verwendet wird.
Mal abgesehen davon ist mir nicht ganz klar, wieso im Skriptum fuer "Einfuegen" nicht erwaehnt wird, dass hier ueblicherweise beim "Suchen" des entsprechenden Blatts gleich alle Knoten mit m-1 Schluesseln gesplittet werden, dadurch gibt's beim Einfuegen dann keine langwierigen Split-/ Verschmelzvorgaenge. Wahrscheinlich eignet sich das besser fuer die Uebung / VO zum Verstaendnis, aber ich dachte, dass das in der Praxis durchaus so gemacht wird ...
-- Elessar
Georg Kraml
09-03-2004, 02:07
Mal abgesehen davon ist mir nicht ganz klar, wieso im Skriptum fuer "Einfuegen" nicht erwaehnt wird, dass hier ueblicherweise beim "Suchen" des entsprechenden Blatts gleich alle Knoten mit m-1 Schluesseln gesplittet werden,
Möglicherweise, nicht üblicherweise.
Es gibt sehr viele Situationen, in denen ich davon ausgehen können muss, dass eine Suchoperation meinen Baum nicht verändert. Denk zum Beispiel an die Probleme mit write locks bei Dateizugriffen und bei Multithreading, oder an die Verliebtheit objektorientierter Programmierung in die saubere Trennung von Inspektoren und Mutatoren.
Wahrscheinlich eignet sich das besser fuer die Uebung / VO zum Verstaendnis,
Ja, definitiv. Wir brauchen kein Pre-Splitting, um den B-Baum zu erklären. Wir müssten aber umgekehrt ziemlich viel Kenntnisse aus anderen Lehrveranstaltungen voraussetzen, um den vernünftigen Umgang mit Pre-Splitting zu erläutern. Keine gute Idee in einer Lehrveranstaltung, in der viele Leute daran scheitern, dass sie keinerlei Programmierkkompetenz mitbringen.
.
Möglicherweise, nicht üblicherweise.
Es gibt sehr viele Situationen, in denen ich davon ausgehen können muss, dass eine Suchoperation meinen Baum nicht verändert. Denk zum Beispiel an die Probleme mit write locks bei Dateizugriffen und bei Multithreading, oder an die Verliebtheit objektorientierter Programmierung in die saubere Trennung von Inspektoren und Mutatoren.
[...]
.
I stand corrected. Du hast natuerlich recht; ich fand es nur verwirrend, dass es nicht erwaehnt wurde.
Danke fuer die Klarstellung.
-- Elessar
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.