Diskussion:B-Baum

Indexstrukturen

-- Sparti 00:59, 26. Jan 2005 (CET): Ja, es ist zwar richtig, dass B-Bäume Datenstrukturen sind, aber in der Datenbanktechnik ist relevant, dass es sich dabei um einen Index handelt. Daher bitte als Indexstruktur definieren. Andersklingende Meinungen dürfen ignoriert werden.

Hat sich erledigt Danke.

-- WhiteCrow 16:27, 17. Mai 2005 (CET): Was ist eigentlich ein externer Suchbaum? Der Begriff wird in der Definition benutzt aber nicht erklärt.

Bruder-Baum

Bei einem externen Suchbaum werden die Daten nur in den Blättern gespeichert. Die inneren Knoten beinhalten nur Verwaltungsinformationen.

Ich habe vor kurzem bei uns im Informatiokuntericht etwas von Brüder-Bäumen erfahren. Irgendwie gleicht die Definition von B-Bäumen der von Brüder-Bäumen. Kann es sich da um die selbe Datenstruktur handeln? --unbekannt

Nein, kurze Recherche ([1]) ergibt, dass Bruder-Baeume binaer sind. B-Baume haben aber sehr zahlreiche Kinder.

Gruss -- Sparti 17:33, 13. Jun 2005 (CEST)

Kandidaten für exzellente Artikel

Hallo allerseits,

der Artikel hat enorm zugelegt. Ich halte ihn fuer einen Kandidaten für exzellente Artikel. Ich schlage vor, den Artikel vorab noch eine Zeit lang zum Review zu belassen und Ihn dann als Kandidat anzumelden. Gibt es jemanden, der anderer Ansicht ist oder den Artikel noch weiter verbessern moechte? Viele Gruesse -- sparti 14:38, 2. Aug 2005 (CEST)

Nee, das ist noch zu früh. Ich würde die Autoren lieber noch etwas weiterschreiben lassen. Ich glaube die können noch eine Menge mehr liefern. Und bevor man ihn dann auf den Kandidaten verheizt gehört der Artikel auch erstmal in den Review. Dann bekommt man die Probleme, die der Artikel sicher noch hat, mit, bevor er durch haufenweise Contra-Stimmen keine Chance mehr hat. --Coma 14:48, 2. Aug 2005 (CEST)

Die Idee war auch nicht, sofort einen Eintrag dort zu tun, sondern auf den Artikel aufmerksam zu machen. Ich denke der Artikel kann noch einen Absatz fuer Laien gebrauchen, wo beschrieben wird, was das ganze eigentlich soll. @Hauix, willst Du etwas in der Richtung schreiben? Sonst wuerde ich mich mal ransetzen. Gruss -- sparti 13:17, 3. Aug 2005 (CEST)

Übersichtsabschnitt wäre schön

Hallo, der Artikel ist bereits sehr gut, ein Lob an die Autoren. Meiner Ansicht nach würde der Artikel viel gewinnen, wenn das Grundprinzip in einem einleitenden Abschnitt Übersicht in 10 bis 15 verständlichen Sätzen zusammengefasst würde. Derzeit ist der Leser gezwungen, die Defininitionen und Operationen einzeln durchzuarbeiten, um sich über die Funktionsweise zu informieren. --84.168.216.64 15:56, 21. Aug 2005 (CEST)

Bitte sehr,... Wäre schön, wenn Du's mal lesen könntest und evtl. noch Vorschläge machen könntest. Gruß hauix 10:11, 5. Sep 2005 (CEST).

• Lässt sich die Formulierung "Das Einfügen, Suchen und Löschen von Daten in B-Bäumen ist in amortisiert logarithmischer Zeit möglich." vielleicht etwas WP:OMA-tauglicher machen? Danke im Voraus, Fleasoft 12:25, 5. Sep 2005 (CEST)

Links innerhalb der Seite

Benutzer:84.168.216.64 hat alle Verweise der Bauart #Links innerhalb der Seite in Links innerhalb der Seite geändert. Ist das Wikipedia-Konvention? Ich finde das nicht schick, da ich schon gerne vor dem Klick auf den Link wüsste, dass es ein Sprung innerhalb der Seite ist. Die jetzige Link-Schreibweise ist unnötig kompliziert. Wenn einem "global" das "#" nicht gefällt, könnte man das in der Wikimedia-Software entsprechend anpassen...

--Hauix15:41, 3. Sep 2005 (CEST)

Mir ist keine solche Konvention bekannt und halte das fuer eine persoenliche Praeferenz des Autors. Mir selbst waere es egal, wobei ich mir nie mehr Muehe als notwendig machen wuerde. -- Gruss sparti 21:20, 3. Sep 2005 (CEST)

Vielleicht geht es ihm um die Darstellung für Ausdrucke? Ich würde die Version ohne # für lesbarer halten. -- Fleasoft 12:25, 5. Sep 2005 (CEST)

Komplettüberschreibung von "Idee und Übersicht"

Kritik am Absatz:

1. Diese ist keine Informatik Enzyclopaedie. Das heisst, es duerfen keine Annahmen ueber den technischen Hintergrund des Lesers gemacht werden.

technische Phrasen wie "in amortisiert logarithmischer Zeit", "minimieren die Anzahl der wahlfreien Zugriffe", "speichern pro Baumknoten eine variable Anzahl von Schlüsseln", "schnell und ohne Belastung des Prozessors über DMA", "charakteristischen Eigenschaften des Hintergrundspeichers", "Verzweigungsgrad) auf eine variable Anzahl mit festgelegtem Schwankungsbereich" muessen erlaeutert werden, sonst kann nur noch der Eingeweihte folgen. Am Besten man laesst sie weg, wenn es nicht fuer die Erlaeuterung notwendig ist. Man kann es auch gerne weiter unten schreiben, aber doch nicht da, wo man die Idee erklaert.

2. Ein Exkurs ueber die Mechanik von Festplatten verwirrt hier nur. Festplattenzugriffe sind teuer und gut. Mal davon abgesehen, dass durch den Read Ahead immer mehrere Sektoren gelesen werden und nie nur einer.

3. Die grundlegende Idee, des Teilen und Herrschens geht garnicht aus dem Absatz hervor. Ich kenne B-Baeume und weiss, dass Du das gemeint hast, aber selbst ein Informatik Student des 4. Semester wird hier nicht begreifen, warum das Verfahren schnell ist.

4. Ganze wichtige Frage bleibt offen: Warum tut man das ganze eigentlich? Ist das ein Zeitvertreib von Informatikern oder gibts da eine Anwendung?

5. Der Teil mit den Schluesseln ist fuer die Idee nicht essentiell. Weiter unten erklaeren.

6. Uebertreibungen (sehr gross, Bruchteil) mögen einen Text auflockern, in Enzylcopaedien wirken sie aber schnell unsachlich. Man sollte sie also vermeiden. Und ganz ehrlich damit hab ich die geringsten Bauchschmerzen.

Alternativvorschlag vom 7. Sep 2005

Ich möchte das nicht gleich über den Artikeltext drüberkopieren, daher hier:

Datenbanken müssen mit erheblich größeren Datenmengen umgehen, als gleichzeitig in den Hauptspeicher eines Rechners passen. Die Daten sind daher persistent im Hintergrundspeicher (z.B. Festplatten) abgelegt. Da die größte Verzögerung beim Zugriff dort durch die mechanische Positionierung des Schreib-/Lesekopfes entsteht, während nach der Positionierung eine große Datenmenge (ein logischer Sektor) schnell und ohne Belastung des Prozessors über DMA eingelesen werden kann, sind Datenstrukturen nötig, die dies berücksichtigen.

Da jeder Sprung von einem Baumknoten zum nächsten auch eine Neupositionierung des Schreib-/Lesekopfes verursachen würde, eignen sich binäre Suchbäume nicht für die Strukturierung persistenter Daten. Sie benötigen für ihre Operationen Suchen, Einfügen und Löschen eine Vielzahl wahlfreier Zugriffe.

B-Bäume speichern pro Baumknoten eine variable Anzahl von Schlüsseln (statt nur eines einzelnen Schlüssels beim Binärbaum), womit auch die Anzahl der Verweise auf Kindknoten (der Verzweigungsgrad) des Knotens auf eine variable Anzahl steigt. Die Variabilität hat einen festgelegten Schwankungsbereich von minimal $t$ und maximal $2t$ (gegenüber zwei beim Binärbaum). Der Parameter $t$ ist wählbar und wird verwendet, um die Datenstruktur so an die Blockgröße des Speichermediums anzupassen, dass ein Baumknoten maximal genau einen kompletten Block des Speichermediums belegt.

Der große Verzweigungsgrad reduziert die Baumhöhe und damit die Anzahl der kostspieligen wahlfreien Zugriffe auf den Hintergrundspeicher. Gleichzeitig vermeidet die variable Schlüsselmenge pro Knoten ein häufiges Balancieren des Baumes.

Für praktische Anwendungsfälle reduzierten B-Bäume wahlfreie Zugriffe pro Operation sogar auf eine kleine konstante Anzahl. Da ein vollständiger Baum mit Verzweigungsgrad $t$ und Höhe $h$ gerade $t^{(h+1)}-1$ Schlüssel speichert, können bei einem entsprechend groß gewählten $t$ (z.B. $t=1024$) bei einer Höhe von $h=4$ bereits $1024^{4}-1=(2^{10})^{4}-1=2^{40}-1$ Schlüssel gespeichert werden. Da diese Anzahl für alle praktischen Fälle ausreichend groß ist und eine Suchoperation höchstens $h+1$ Knotenzugriffe benötigt, müssen für jede Suchanfrage höchstens fünf Baumknoten inspiziert werden. Hält man die beiden ersten Baumebenen dauerhaft im Hauptspeicher, so benötigt eine Suche nur noch höchstens drei Festplattenzugriffe. Aus theoretischer Sicht ändert sich dadurch zwar nichts an der Komplexität der Suchoperation von O(log(n)) Zugriffen, der konstante Faktor ist aber so klein, dass für praktische Fälle immer eine kleine konstante Zugriffsanzahl ausreicht.

• Die ersten Abschnitte habe ich IMHO ganz gut von der Formulierung vereinfacht, ohne den Sinn zu entfremden (@Hauix: Bitte um Überprüfung). Ich habe absichtlich mehr Absätze eingefügt, weil ich glaube, dass das den Lesefluss erleichtert und die nötigen Pausen zum Durchatmen und überdenken des letzten Abschnitts bietet. Beim letzten Abschnitt ist mir etwas die Luft ausgegangen – ich wusste einfach nicht, wie ich das sinnvoll ändern könnte. Beim letzten Satz habe ich ein „aber“ durch ein „zwar“ ersetzt. Das ist zwar nicht die Welt, aber schöner.

Ich hoffe es gefällt einigermaßen. Bitte um Feedback. Danke, Fleasoft 08:56, 7. Sep 2005 (CEST)

Hallo Fleasoft, vielen Dank für Deine Mühe. Der Absatz ist jetzt zwar etwas verständlicher, was Punkt 1) meiner Kritik betrifft, aber mir waren ausserdem noch die Punkte 3. und 4. wichtig. Vielleicht können wir da auch nochetwas machen?

Ich möchte übrigens ganz dezent darauf hinweisen, dass ein fachlich brauchbarer Artikel keine Garantie gegen Löschungen sind, wie diese Beispiel belegt: Benutzer_Diskussion:Dickbauch#Virtuelle_Tabelle. Ich Teile keines Falles diesen Löschwahn. Aber ich möchte verdeutlichen, wie nicht Informatiker unsere Artikel beurteilen. Meine Intension ist, diesem entgegen zu wirken.

Viele Grüße -- sparti 22:01, 7. Sep 2005 (CEST)

Das ist ja auch im Sinne von Wikipedia:Wikipedia ist kein Fanzine. ;-) Fleasoft 09:40, 8. Sep 2005 (CEST)

Ich finde die Aufteilung und Reihenfolge im Artikel noch nicht so gelungen. Mich hat es z.B. erstaunt, noch vor einer eigentlichen Beschreibung des Wesens von B-Bäumen über Festplattenzugriffe lesen zu müssen. Es wird zwar im Kapitel vorher (Namensgebung) kurz darauf eingegangen, aber dort lediglich zur Abgrenzung von Binärbäumen. Dies sollte eigentlich erst nach einer grundsätzlichen, knappen und leicht verständlichen Erläuterung geschehen. Außerdem wiederholt sich der Namensgebungsteil teilweise nochmal unter Geschichte. Das könnte man zu einem Kapitel kombinieren. Mkone 01:32, 12. Sep 2005 (CEST)

Einfügen falsch beschrieben?

Im Artikel steht, dass beim Einfügen volle Knoten "vorsorglich" geteilt werden, bevor man weiter zu den Kindknoten absteigt. Soweit ich Herrn Bayer verstanden habe, ist das aber falsch und die Knoten werden von unten nach oben aufgeteilt und zwar wirklich erst, wenn sie "übervoll" sind, also geteilt werden müssen.

Durch eine vorsorgliche Teilung kann man sich zwar das Rückwärts-Arbeiten sparen, erhält dadurch allerdings Bäume, die unnötig oft geteilt werden und hat damit etwas anderes als den von Rudolph Bayer beschriebenen B-Baum.

-- Oimel 14:23, 30. Sep 2005 (CEST)

Die Darstellung lehnt sich an die Beschreibung in "Introduction to Algorithms" von Cormen, Leiserson, Rivest und Stein an. Möglicherweise handelt es sich dabei um eine (geringfügige) Modifikation des Original-Vorschlags. Der Unterschied zwischen vorsorglichem Teilen beim Abstieg und reparierendem Teilen beim dann notwendigen Wiederaufstieg ist aber (bei großer oberer Schranke für die Schlüsselzahl) marginal: Es wird nur dafür gesorgt, dass alle Knoten immer einen einzigen Reserve-Platz (von 1024 o.ä) haben. Das ändert die Aufnahmefähigkeit bei gleicher Höhe nur minimal, ändert nichts an den Eigenschaften, vereinfacht aber sowohl Darstellung als auch Implementierung erheblich (insbesondere wohl bei konkurrierenden Zugriffen auf die Datenstruktur).

Wenn Du den Original-Artikel gelesen hast, dann kannst Du ja einen Hinweis auf den feinen Unterschied in der Darstellung einbauen.

-- Hauix 13:03, 6. Okt 2005 (CEST).

Ich habe leider gar keinen Artikel, das entsprang lediglich meinem Gedächtnis der Bayerschen Vorlesung für Datenbanksysteme; und wenn ich es richtig in Erinnerung habe, hat er sich sogar darüber beschwert, dass sein ursprünglicher Algorithmus überall falsch beschrieben wird ;)

-- Oimel 12:32, 18. Dez 2005 (CET)

Lesenswert-Diskussion

Ein B-Baum ist in der Informatik eine Daten- oder Indexstruktur, die häufig in Datenbanken und Dateisystemen eingesetzt wird. Ein B-Baum ist ein vollständig balancierter Baum, der Daten sortiert nach Schlüsseln speichert. Das Einfügen, Suchen und Löschen von Daten in B-Bäumen ist in amortisiert logarithmischer Zeit möglich. B-Bäume wachsen anders als die meisten Suchbäume von den Blättern hin zur Wurzel.

•  Pro Ein runder Artikel. Ausreichend bebildert, umfangreich und interessant zu lesen norro 20:27, 2. Dez 2005 (CET)
•  Pro Halte den Artikel schon seit laengerem fuer lesenswert. Wenn jetzt noch ein bischen mehr Wert auf die Oma-Verstaendlichkeit gelegt wird (was zumindest in der Einleitung moeglich ist), dann wird er auch Exzellent. -- sparti 00:50, 3. Dez 2005 (CET)
•  Pro - Interessant --Spacefrank 22:37, 3. Dez 2005 (CET)
• sieht gut aus. Ein paar Dinge kann man sicherlich noch verbessern. Ich würde vorschlagen, die Artikel B-plus-Baum und B*-Baum noch einzuarbeiten, anstatt sie als Stubs zu verlinken. Sie gehören auch inhaltlich rein. Die "Geschichte" würde ich nach oben ziehen und mit der "Namensgebung" vereinen, da gibts eh schon Überschneidungen. Trotzdem ist er schon ein pro wert, würde ich sagen. --Kurt seebauer 22:48, 3. Dez 2005 (CET)
• für mich lesenswert, pro --Andreas ?! 20:55, 4. Dez 2005 (CET)
•  Pro Meiner Meinung nach absolut lesenwert! Allerdings vermisse ich den Unterschied zwischen B, B+ und B* Bäumen. Sandro*

Character sind Schall und Rauch, aber...

Als Laie, der gerade lernt:

Ist es in Ordnung, von "Schlüsseln" zu reden in der Baumstruktur? Vor allem unter dem Gesichtspunkt, daß der BTree ja vor allem in Datenbankumgebungen eingesetzt wird. Die Index/Schlüssel durcheinanderwerferei ist da ja schon Problematisch? Gibt es keinen passenderen Begriff?

Ole

Hmm, ein Index dient dazu, Schluessel zu indizieren. Wo wurden denn diese Begriffe durcheinander geworfen? -- sparti 14:17, 15. Dez 2005 (CET)

NICHT in der Wiki. Allgemein wird dies gerne getan. Selbst die offizielle mySQL-Doku etwa ist da wenig rühmlich.ole

Wieso $log_{t}({(n+1) \over 2})$?

Das beim binären Baum die Höhe = ln(n) ist ist ja eigentlich absolut plausibel. Beim B-Baum hätte ich jetzt eine Höhe von $log_{t}(n)$ erwartet. Im Artikel steht jedoch $log_{t}({(n+1) \over 2})$

Eine knappe Erklärung dazu wäre nett.

--ole

Intuitiv gebe ich Dir recht. Doch findet sich hier [2] ein Beweis, fuer die Behauptung im Artikel. Vielleicht kann das ja mal jemand integrieren... :-) -- Gruss sparti 19:08, 18. Dez 2005 (CET)

erst einmal Danke für den Link. Allerdings lese ich aus der Erklärüng, daß die Höhe nicht $log_{t}({(n+1) \over 2})$, sondern $log_{t \over 2}({(n+1) \over 2})$ beträgt. Ein ja nicht unerheblicher Unterschied. Oder unterliege ich da einem Denkfehler? (wobei ich zugeben muß - sofern die Formel richtig ist - das das Herleiten vielleicht doch etwas zu weit geht. Heisst ja nicht Papulapedia oder so :) .. --ole