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.(Der vorstehende, nicht signierte Beitrag – siehe dazu Hilfe:Signatur – stammt von Sparti (Diskussion • Beiträge) 09:54, 12. Sep. 2005 (CET))

Als Fachfremder möchte ich mich dem anschließen, vor allem was die Punkte 1 und 3 angeht. Mittlerweile habe ich, glaube ich, durch Lektüre des englischen Wikipedia-Artikels das Prinzip eines B-Baumes verstanden. Einfache Sache eigentlich. Den Überblicksabschnitt hier fand ich hingegen unverständlich und mangelhaft. Nur so als Beispiel, was ist ein Schlüssel, und wozu dient er? Wird nicht definiert. Die Lektüre des konkreten Teils hätte mich vielleicht noch zum Ziel geführt, aber dazu kam es nach diesem Intro gar nicht mehr. --Tohuwaboho 13:07, 12. Dez. 2008 (CET)

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*
•  Kontra Der B-Baum ist ein wichtiger Schritt in der Entwicklung, von praktischer Bedeutung ist aber der B+-Baum, der unzureichend gewürdigt wird.

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

Um die Begriffe auseinander zu halten, kannst du den Schlüssel im Suchbaum als Suchschlüssel und den Schlüssel in der Datenmodellierung als Identitätsschlüssel verstehen. Mit etwas Einarbeitung verwechselst du die beiden entsprechend des Kontexts eh nicht mehr

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

Das haengt davon ab, wie die Konstante t definiert wird. Im Beweis liegt die Anzahl der Schluessel zwischen t/2 und t. Hier im Artikel wurde t so definiert, dass die Schluessel zwischen t und 2t liegen. Also lediglich eine Aenderung des Betrachtungsstandpunktes.

Wegen der Herleitung: Es wuerde ja schon reichen, die Beweisidee auszufuehren. Aber auch eine Herleitung wuerde ich nicht wieder loeschen, wenn sie erstmal hier steht. Denn ich denke wir sollten schreiben, was jemanden interessiert und nicht, was irgendwelche Regeln vorschreiben. -- sparti 13:20, 19. Dez 2005 (CET)

maximale Schlüsselanzahl?

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.

1. Widerspricht sich das schon mal selbst, da $t^{(h+1)}-1$ bei $h=4$ sicherlich $1024^{4+1}-1$ ist, nicht $1024^{4}-1$.

2. Macht das aber eh keinen Sinn. Denn wenn jeder Knoten bis $2t-1$ Schlüssel hat und bis zu $2t$ Nachfolgeknoten, dann haben wir z.B. bei einem Baum der Höhe 2 und $t=2$ bereits $3+4*3=15$ Knoten, gegenüber den $t^{(h+1)}-1=2^{3}-1=7$ Knoten ist das doch ein deutlicher Unterschied. --OmEgA 15:44, 2. Jun. 2007 (CEST)

maximale Anzahl von Schlüsseln bei minimalem Verzweigungsgrad t

"oder die minimal erlaubte Anzahl von Kindknoten - in diesem Fall wäre die maximal erlaubte Anzahl an Schlüsseln $2t-1$." siehe #REDIRECT B-Baum#Idee_und_.C3.9Cbersicht
Wieso ist das so? --BuZZdEE.BuzZ 12:57, 29. Okt. 2010 (CEST)

Definition Kindknoten

Bei den Formeln hab ich mich gefragt, ob $x.k_{j-1}\leq k$ Sinn macht, also das Gleichzeichen stört mich irgendwie, damit hätte Eltern- und Kindknoten den gleichen Schlüssel, was prinzipiell nicht stört, aber die eindeutige Suche kann man damit vergessen. Vor allem würde $x.k_{j-1}\leq k\leq x.k_{j}$ bedeuten, dass ein Index sowohl links als auch rechts vom Elternknoten eingefügt werden könnte. --Cyber1000 16:42, 15. Aug. 2007 (CEST)

Die Gleichheitszeichen in allen Formeln machen keinen Sinn und sind vollkommen überflüssig, da jeder Schlüssel im gesamten Baum nur ein einziges Mal auftreten kann. Ich werde das gleich korrigieren.

Suche beim Einfügen

Folgende Aussage habe ich nicht verstanden - und denke daher, dass sie entweder berichtigt oder besser erklärt werden sollte ;) Falls es nur an mir liegt bin ich auch mit einer einfachen Antwort zufrieden:

Zitat: "Die Suche bricht nicht in einem inneren Knoten ab, wenn dort der Schlüssel k bereits gefunden wird. Es findet immer ein Abstieg zu einem Blattknoten statt."

Problem 1: Sollte dies wirklich der Fall sein, in welchen Unterbaum steigt man dann ab - den vor dem gefundenen (gleichen) Schlüssel oder den danach?

Problem 2: Ist ein B-Baum nicht inkonsistent, wenn sich der gleiche Schlüssel an zwei verschiedenen Stellen im Baum wiederfindet? --Thekryz 18:02, 2. Apr. 2008 (CEST)

-- Zwei Aussagen beim Unterkapitel Einfügen sind unglücklich bzw. fehlerhaft formuliert. Korrekt müsste es heißen:

1.) Das Einfügen eines neuen Schlüssels k geschieht immer in einem Blattknoten.

Dem Einfügen muss immer ein kompletter Suchlauf vorhergehen, der ergibt, dass der Schlüssel k noch nicht existiert und in welche Knotenseite er einzutragen ist. Dies kann nur ein Blattknoten sein, denn diese Aussage ist erst nach dem Durchsuchen über die gesamte Höhe des Baumes zulässig.

2.) Die Suche bricht in einem inneren Knoten ab, wenn dort der Schlüssel bereits gefunden wird und ein Einfügen deshalb nicht notwendig ist.

Ein Schlüssel k darf nicht mehrfach existieren. Einfügen gilt also nur für einen neuen Schlüssel. Wird ein Schlüssel gefunden, ist zu prüfen, ob weiterführende Daten im Zusammenhang mit dem Schlüssel zu ändern sind. Eine Änderung der Daten oder Datenverweise beim Schlüssel hat auf die Anzahl der Einträge in der Knotenseite ja keinen Einfluß.

Beim Einfügen eines Schlüssels in einen Blattknoten kann es jedoch zum Überlaufen der Seite kommen. Dies wird durch durch Ausgleichen mit der linken oder rechten Nachbarseite auf der gleichen Ebene beseitigt. Falls dies nicht möglich ist, muss der mittlere Schlüssel dieses Knotens in den Vorgängerknoten der nächsten Ebene übertragen werden. Falls diese Operation dort auch einen Überlauf verursacht, wird die Operation auf dieser Ebene in gleicher Weise fortgeführt. Erreicht die Einfügeoperation die Rootseite und verursacht auch dort einen Überlauf, wird die Rootseite zerlegt. Das mittlere Elemente wird als neue Rootseite auf eine höhere, neue Ebene gelegt, der linke und rechte Teil der Seite in zwei neuen inneren Knotenseiten abgelegt. Nur auf diese Weise kann ein B-Baum wachsen. Alle Schlüssel in inneren Knotenseiten sind ursprünglich Mitglieder von Blattknoten gewesen und wurden bei Vergrößerung der Schlüsselmenge in höhere Ebenen verschoben.

Unabhängig davon kann es bei Namenlisten als Schlüssel (Telefonbuch) zu Konflikten kommen, wenn es gleichlautende Namen gibt (Müller, Meier, Schulze). Dieses Problem muss durch Schlüsselerweiterungen (z.B. Meier1, Meier2 usw. im einfachsten Fall) außerhalb der Datenbank beseitigt werden.

Das Unterkapitel Einfügen sollte meines Erachtens in diesem Sinne ergänzt werden.--Hubert_Badtke 16:30, 10. Mai 2008 (CEST)

Ich habe das mal so ergänzt. --Thekryz 16:36, 26. Jun. 2008 (CEST)

-- Vielen Dank an Thekryz für die Änderung. Ich habe dies in die Diskussion gestellt, denn es gibt beim B-Baum Varianten, die vom Einsatzgebiet abhängen. Das von mir oben beschriebene Einfügen entspricht dem Algorithmus von R. Bayer und E. McCreight (siehe auch: "Algorithmen und Datenstrukturen" von Niklaus Wirth). Auch das Suchen eines Schlüssels kennt mehrere Varianten:

• Lesen eines konkreten Schlüssels k
• Lesen des Schlüssels k+1 auf der Basis des Schlüssels k (direkter Nachfolger)
• Lesen des Schlüssels k-1 auf der Basis des Schlüssels k (direkter Vorgänger)
• Lesen des ersten Schlüssels in der Datenbank
• Lesen des letzten Schlüssels in der Datenbank

B-Bäume lassen sich sehr flexibel an bestimmte Einsatzbereiche anpassen und optimieren. Eine nähere Erläuterung würde jedoch wahrscheinlich den Rahmen einer Enzyklopädie etwas überschreiten. Falls Sie das interessiert, können Sie von mir Unterlagen per Email anfordern, oder Sie besorgen sich das schon fast mit Kultstatus belegte Buch von Niklaus Wirth. Mit freundlichem Gruß --Hubert_Badtke 10:03, 29. Jun. 2008 (CEST)

Löschen aus inneren Knoten

Beschreibt nicht, was passiert, wenn Schlüssel in Kindknoten (symmetrischer Nachfolger / Vorgänger) Kinder hat. Wohin werden diese Verschoben, zusammengeführt ...? Wäre eine Erkläreung wert. Ich nehme mal an, dass man das ganze rekursiv machen kann (also beim Löschen im inneren Knoten wieder Löschen im inneren Knoten (mit Kindschlüssel) durchführen). --Thekryz 12:27, 1. Jul. 2008 (CEST)

-- Beim Löschen eines Schlüssels in einem inneren Knoten wird aus einer Nachfolgeseite der Nachfolger- oder Vorgängerschlüssel "gestohlen". Diese Aktion läuft durch, bis die nachfolgende Ebene die Blattebene ist, wo eine Entnahme des Schlüssels ohne Konsequenzen auf weitere Verweise ist. Jedoch kann es vorkommen, dass keine der fraglichen Seiten auf der Blattebene genügend Einträge aufweist, um ein Unterlaufen der Mindesteinträge zu vermeiden. Dann müssen beide Seiten verschmolzen werden, was die Entnahme eines Schlüssels in der Vorgängerebene erfordert und dort eventuell zum selben Problem führt. Die Verschmelzung von Seiten kann also rückwärts bis zum Wurzelknoten laufen. Wird dieser dadurch leer, wird sein durch Verschmelzen einziges Kind der neue Wurzelknoten. Der Baum schrumpft um eine Ebene von der Wurzel her in Richtung Blattebene. --Hubert_Badtke 12:31, 4. Jul. 2008 (CEST)

Binärbaum vs. B-Baum: Typo?

"Ein Knoten des Binärbaumes kann dann als ein Block gelesen bzw. gespeichert werden." - Muss das hier nicht B-Baum oder einfach nur Baum heißen? LG, Flo --129.187.41.12 12:24, 24. Aug. 2009 (CEST)

ja, so war es wohl gemeint - danke für die Änderung Flo. Grüsse -- hroest Disk 10:29, 31. Aug. 2009 (CEST)

Im Abschnitt Suche wird mal x.k mal x.c verwendet.

besser x.c nehmen, sonst kommt man mit dem gesuchten k durcheinander (nicht signierter Beitrag von 134.91.90.5 (Diskussion) 19:56, 21. Jun. 2010 (CEST))

Banyan-Feige

Folgenden Satz habe ich gerade aus dem Abschnitt „Geschichte und Namensgebung“ entfernt:

Eine andere Interpretation entsteht durch Betrachtung der Banyan-Feige, einer Pflanzenart, die durch Wurzelteilung wächst.

Mir scheint das Theoriefindung (siehe Wikipedia:Keine Theoriefindung). Wenn jemand eine Quelle dafür findet, darf er's gern wieder einbauen. -- Levin 03:26, 12. Aug. 2010 (CEST)

Grafik fehlerhaft

in der Grafik gilt k1 < k2 (da im ersten Kindknoten geordnet), aber auch k2 < k1 (da k1 in der Wurzel steht und somit die Teilbäume trennt). Das kann nicht sein. Besser: die Grafik aus der engl. Wikipedia verwenden. (nicht signierter Beitrag von Teddy87 (Diskussion | Beiträge) 19:08, 14. Aug. 2011 (CEST))

Fehler

Die Konstante dieser Abschätzung ist aber deutlich geringer als bei (balancierten) binären Suchbäumen mit Höhe $\log _{2}(n)$:

${\log _{2}(n) \over {\log _{t}({n+1 \over 2})}}\approx \log _{2}(t)$

Das is vollkommer Schwachsinn was da steht, denn ein balancierter binärer Suchbaum hat Höhe log2 ((n+1)/2) (nicht signierter Beitrag von 79.229.173.103 (Diskussion) 22:25, 5. Okt. 2011 (CEST))

Um es genau zu sagen ist der Binärbaum um den Faktor O( log_2(n) / log_t(n) ) langsamer als der B-Baum wenn t>2 ist. (nicht signierter Beitrag von 79.229.175.76 (Diskussion) 22:47, 6. Okt. 2011 (CEST))

Fehler in Graphiken bei den Operationen?

Ich bin der Meinung, dass die Angabe "t=3" bei den Graphiken zu den Operationen (Abbildungen 3-6) falsch ist. Richtig müsste es meiner Ansicht nach "t=2" heißen. 80.110.19.234 11:01, 17. Apr. 2015 (CEST)

Grafiken zu Löschoperationen mangelhaft

Hallo allerseits, also ich habe schon so einige Zeit Wiki durchforstet. Aber so eine undurchsichtige Grafik ist mir selten untergekommen. Eine Grafik wie diese sollte selbsterklärend sein. (auf Löschoperationen bez.) Leider ist sie einfach nur grauselig. Das ganze Thema ist mir geläufig und ich hatte mich in meinem Studium oft damit ausseinandergesetzt. Nach solch unverständlichen Grafiken wird der Leser lediglich verwirrt. Best Regards JL

Beispielcode fehlerhaft

Der C++ Code im Abschnitt "Programmierung" enthält m.E. einen Bug und eine Unschönheit. Der Bug ist in der Funktion BTreeNode::splitChild. Die Zuweisung "node->n = t - 1;" kommt in dieser Funktion zweimal vor. Beim zweiten Mal muss es jedoch "_node->n = t - 1;" heißen, sonst bleibt die Anzahl der Keys im Knoten _node auf einem falschen Wert. Es ist m.E. ungeschickt, zwei Variablen "node" und "_node" zu benennen. In der verlinkten Quelle zum Beispielcode ist der Bug nicht enthalten, und die Variablen sind besser unterscheidbar benannt.

Die Unschönheit ist, dass die Funktion BTreeNode::insert im Beispiel redundant ist, nicht aufgerufen wird und gelöscht werden kann. Identischer Code befindet sich auch in der Klasse BTree, in Funktion BTree::insert. --2003:E3:739:C00:81D3:5491:BECF:96F5 16:30, 14. Dez. 2023 (CET)