Video 9-13: Überblick B-Bäume

0:03 Eine leichte Abwandlung von dem, was sie über zwei drei Bäume gelernt haben, hat noch einen einen größeren ähm Einsatzzweck in Datenbanken. Das sind die B-Bäume. Und die Idee ist da schlicht, ähm, wenn man nicht für internen Speicher optimiert, wie wir das hier in aller Regel annehmen, wir optimieren für den Arbeitsspeicher, da landen unsere Rotchwarzbäume und so weiter, sondern für größeren Speicher mit etwas anderen Eigenschaften. Ganz klassisch für Festplatten, die in Rechenzentrern auch immer noch relevant sind, weil sie einfach das Speichermedium sind, von dem man große Kapazität in kleinem Raum und für günstigen Preis kriegen kann. auch wenn natürlich ähm mitten zwischen diesen beiden würden heute SSDs sitzen, die so ein bisschen Eigenschaften von den beiden äh zwischen Arbeitsspeicher und und Festplatte so ein bisschen dazwischen liegen. Es bleibt aber dabei, dass gerade auch auf diesen SSDs äh man in in ganzen Blöcken arbeiten will. Also einzeln an bestimmte Stellen im Speicher springen ist teuer. Einen ganzen Block sequentiell lesen, insbesondere auf Festplatten ist viel viel günstiger.

1:13 Also möchte man eigentlich sequentiell arbeiten. Ist ein langes Thema äh für ein großes Kapitel in einer anderen Vorlesung. Die einfache Idee hier, die zu diesem Thema passt, ist in den zwei, drei Bäumen noch viel viel mehr Schlüssel pro Knoten zuzulassen. Also statt zwei oder drei Kinder, ein oder zwei Schlüssel, haben wir irgendwas zwischen m halbe und m -1 ähm für einen Parameter M viele Kinder und ich kann das M als als Tuning Parameter wählen, passend zu meiner Hardware und es ist durchaus üblich, dass das so in den drei und vierstelligen Größenordnung ist und dementsprechend haben sie ganz ganz großen Fanout von jedem Knoten. Was umgekehrt auch heißt, wenn ich immer mindestens m halbe Kinder habe, dann bin ich nach log zur Basis m halbe von n leveln mit meinem Baum fertig. Und ähm deswegen verwendet man das in Datenbanken viel, weil am Ende die Daten dort auf Festplatte liegen und man eben diesen diesen großen Fanout braucht, um da effizienter drauf zu arbeiten.

2:24 Algorithmisch passiert fast gar nichts Neues Besonderes, erstmal in der Grundvariante, außer dass wir statt den zwei Dreibäumen diesen großen Fanout haben. Das ist aber die gleiche Art von Operationen. Wenn ich einfüge, dann ähm ist glaube ich auch Folien zu. Wenn ich suchen kann ich so wie bei den zwei, drei Bäumen, wenn ich einfüge, dann kann es mir passieren, dass ein Knoten überläuft. Der ist jetzt zu voll. Dann gibt er einen mittleren Knoten an den Elternknoten und teilt sich in zwei Knoten auf. Das ist, wie wir es auch in kleinen gesehen hatten. Äh und löschen ist hier auf den Folien gar nicht drauf. funktioniert dann so wie Variante 1 aus den zwei drei Bäumen, die wir nicht verfolgt haben. Deswegen wollte ich sie ihnen aber zeigen, damit Sie gesehen haben, wie das bei B-Bäumen funktioniert. Auch wenn wir es sozusagen, dieses Kapitel ist nur so ein bisschen Randnotiz, weil ich hoffe, dass es Ihnen noch helfen wird, aber ist nicht Teil des Prüfungsstoffs.

3:25 Okay, Höhe hat man schon gesagt. Also der große Vorteil von B-Bäumen ist in der Praxis, so viel Daten haben sie dann doch nie, mehr als Höhe 4 kriegt das Ding nicht. Und dann ist eben nach äh vier Zugriffen auf die Festplatte der entsprechende Eintrag gefunden. Ähm B-Bäume sind insbesondere dann für alle Indizes in Datenbanken im Einsatz.

3:48 Also letzter Punkt, wir hatten Rotchwarzbäume als die Standardimplementierung im schnellen Arbeitsspeicher für diese ja order Symbolle Tables. Ähm hier steht noch mal, wie die in verschiedenen Sprachen heißen oder verschiedenen Umgebungen heißen. Äh zu diesen BBäumen gibt's natürlich noch viel viel mehr zu sagen. Ähm fehlt dann auch noch B FS, Butter FS oder Bree FS. Da steckt schon im Name, dass das am Ende alles ein B-Baum ist. Ähm, wann sie mal aufs Platte wann immer es auf Platte geht und Sie suchen müssen, ist wahrscheinlich eine B-Baumvariante, was Sie haben wollen. Das ist so die große Unterscheidung an dieser Stelle. Ja.