Diskussion:B-Baum

Indexstrukturen

Letzter Kommentar: vor 19 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

-- 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.Beantworten

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"

(von Diskussion:Sparti und Diskussion:Hauix hierher verschoben)

Hallo Sparti,

in den Abschnitt "Idee und Überblick" bei B-Bäumen habe ich wirklich viel Liebe reingesteckt. Damit, dass Du im Handstreich alles "umgekrempelt" hast bin ich nicht einverstanden. Könntest Du Deine Änderungen zurücknehmen und darlegen, was Dir nicht gefällt?

hauix 20:07, 5. Sep 2005 (CEST)

... und dabei auch noch Rechtschreibfehler eingebaut hast...

hauix 20:19, 5. Sep 2005 (CEST)

Hallo Hauix,

also Du hast in der Tat viel Arbeit in den Artikel gesteckt und ich weiss das zu schaetzen. Leider bin ich aber der Ansicht, dass der Abschnitt mit der Idee voellig ungeeignet war. Viel zu lang und zu kompliziert.

Was verstehst Du denn an dem Einleitungsabschnitt konkret nicht?

Du hast aus 374 Wörtern 354 gemacht und dabei keinen einzigen Satz heile gelassen. Das nenne ich nicht kürzen.

Das hier ist eine Encyklopaedie und der Artikel muss fuer jeden (auch fuer nicht Datenbank Experten und nicht Informatiker) verstaendlich sein.

Für "nicht Datenbank Experten" ja, (ein solcher bin ich). Für "jeden" bestimmt nicht, sondern nur für denjenigen, der sich für die Materie interessiert - sonst würde er den Artikel nicht lesen.

Das war so nicht gegeben ...

Wie gesagt, was verstehst Du nicht?

und ich fuerchte, dass es da noch immer nicht ist.

Es ist auf jeden Fall nicht besser geworden. (Grrr...)

An den Kommentaren kannst Du erkennen, dass auch andere Deine Formulierung nicht verstehen.

Der Kommentar bezog sich nicht auf diesen Abschnitt. Und Du hast diese Formulierung auch nicht geändert!

Ich finde sie uebrigens weder schlecht noch falsch. Aber fuer diesen Rahmen nicht angebracht!

Welche Formulierungen denn genau?

Dann noch etwas zum Wikiprinzip. Es ist nunmal so, dass hier jeder Mitarbeiten darf und soll.

Ja, Du bist herzlich eingeladen, mitzuarbeiten - nur wenn ich mich mehrere Stunden an einen Abschnitt setzte und der dann von einem Mitarbeiter im Handstreich komplett über den Haufen geworfen wird, ohne dass vorher konkrete Kritikpunkte klargestellt werden, dann kann ich keine Mitarbeit erkennen.

Ich wuerde mir wuenschen, dass Du lieber versuchst, meinen Vorschlag aufzugreifen und den Text noch weiter vereinfachen wuerdest. Es ist niemanden gedient, wenn der Artikel irgendwann einen Unverstaendlichkeitsstempel erhaelt.

Du hast keinen Vorschlag gemacht, sondern meinen noch taufrischen Text unangekündigt komplett zerlegt. Ich würde mir wünschen, dass Du Vorschläge gemacht hättest, die ich hätte aufgreifen können. Ein neugeschriebener Absatz der jetzt nicht nur unverständlich sondern auch noch umständlich formuliert ist, ist kein Vorschlag.

Wenn Du ein Teil von dem, was ich geschrieben habe fuer spaeter wichtig ist, dann koennen wir das jederzeit wieder herbeizaubern.

Wegen der Rechtschreibfehler muss ich mich entschuldigen. Das liegt daran, dass ich immer gehetzt schreibe, bis ich keine Zeit mehr habe und dann ohne Korrekturlesen speichern muss. Das ist in der Tat nicht optimal und ich werde mich bemuehen, hier einen besseren Weg zu finden.

Nochmal: wenn ein ausgearbeiteter Text, der mehrfach Probegelesen ist mit sowas "Gehetztem" innerhalb kürzester Zeit überbügelt wird, dann macht das in höchstem Maße ärgerlich!

Viele Gruesse -- sparti 21:04, 5. Sep 2005 (CEST)

Not amused, hauix 02:25, 6. Sep 2005 (CEST)

Nimms mir nicht uebel, aber Dein Aerger hilft hier garnix. Der Absatz war ungeeignet und dazu stehe ich. Werde aber meinen Text heute Abend nochmal ueberarbeiten. Ansonsten sollten wir die Diskussion auf B-Baum weiterfuehren. Wenn Du Dich nicht arrangieren kannst wirst Du damit leben muessen, dass Dir frueher oder spaeter einer ein Unverstaendlich reinschreibt. Den Exzellenten Artikel kannst Du dann erstmal knicken. Wir sollten also zusehen, daran zu arbeiten, dass jeder den Artikel verstehen kann. mfg -- sparti 10:56, 6. Sep 2005 (CEST)

Leider scheinst Du ja nicht erklären zu können, was Dir daran nicht gefällt. Da nützt das zu seiner Meinung stehen garnix. Das ist nur gut für die Politik. -- hauix 14:49, 6. Sep 2005 (CEST)

Lieber Huix, ich kann Dir meine Kritik durchaus erklaeren. Aber ich ziehe es mittlerweile vor, aggressiven Diskussionen aus dem Weg zu gehen. Daher must Du leider mit meinem Bemerkung oben leben und warten, bis ich den Absatz ueberarbeitet habe. Dannach kannst Du ja dann Deine Kritik an meinem Text aeussern. Aber bitte in einem freundlichen Ton, wie ich es auch getan habe. -- sparti 15:02, 6. Sep 2005 (CEST)

Die Diskussion hat noch nicht einmal begonnen -- wo soll sie da aggressiv sein? Das Wegducken machts nicht besser.

Dannach kannst Du ja dann Deine Kritik an meinem Text aeussern

Das ist ja prima. Ich darf dann das tun, wovor Du Dich zu drücken versuchst...

Bevor Du den Text nochmal umschreibst, könntest Du das Kritisieren vorher hieran üben (als besonderen Service kopiere ich meine letzte Version hierher:

Idee und Übersicht (vom 10:08, 5. Sep 2005)

Datenbanken müssen mit sehr großen Datenmengen umgehen, von denen nur ein Buchteil gleichzeitig in den Hauptspeicher eines Rechners passt. Die Daten sind daher persistent auf Hintergrundspeicher (z.B. Festplatten) abgelegt. Für die effiziente Verwaltung werden Datenstrukturen benötigt, welche die charakteristischen Zugriffseigenschaften des Hintergrundspeichers berücksichtigen: Die größte Verzögerung beim Festplattenzugriff entsteht durch die mechanische Positionierung des Schreib-/Lesekopfes. Ist der Schreib-/Lesekopf aber einmal positioniert, kann eine große Datenmenge (ein logischer Sektor) schnell und ohne Belastung des Prozessors über DMA eingelesen werden. Binäre Suchbäume eignen sich für die Strukturierung persistenter Daten nicht, weil sie für ihre Operationen Suchen, Einfügen und Löschen eine Vielzahl wahlfreier Zugriffe benötigen, da jeder Sprung von Knoten zu Knoten eine Neupositionierung des Schreib-/Lesekopfes verursachen würde.

B-Bäume minimieren die Anzahl der wahlfreien Zugriffe unter Ausnutzung der charakteristischen Eigenschaften des Hintergrundspeichers. Sie speichern pro Baumknoten eine variable Anzahl von Schlüsseln (statt nur eines einzelnen Schlüssels beim Binärbaum). Mit der Schlüsselanzahl steigt auch die Anzahl der Verweise auf Kindknoten pro Knoten (der Verzweigungsgrad) auf eine variable Anzahl mit festgelegtem 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 gerade einen kompletten Block des Speichermediums belegt. Der große Verzweigungsgrad reduziert die Baumhöhe und damit die Anzahl der kostspieligen wahlfreien Zugriffe. Die variable Schlüsselmenge pro Knoten vermeidet 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 aber 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.

-- hauix 14:49, 6. Sep 2005 (CEST)

Ich mach' Dir das mit Deiner Version mal vor:

Idee und Übersicht (Umgekrempelte Version vom 19:35, 5. Sep 2005)

Datenbanken müssen mit sehr großen Datenmengen umgehen, von denen nur ein kleiner Teil gleichzeitig im schnellen Hauptspeicher eines Rechners gespeichert werden kann.

"ein kleiner Teil" statt "Bruchteil" ist umständlicher und klingt flacher. -- hauix 15:21, 6. Sep 2005 (CEST)
"im schnellen Hauptspeicher eines Rechners gespeichert": Das Attribut "schnell" passt zwar zu Hauptspeicher, ist beim Verb "speichern" aber irrelevant. Ob der Hauptspeicher schnell ist, oder nicht spielt keine Rolle für den Vorgang des gespeichert haltens. Und ums gespeichert halten geht es hier auch gar nicht, sondern ums Verarbeiten! Dass Datenbanken ihre Daten auf der Festplatte halten hat ja ganz andere Gründe, als dass der Hauptspeicher zu klein ist! -- hauix 15:21, 6. Sep 2005 (CEST)

Die Daten werden daher auf einer Festplatte dauerhaft (persistent) gespeichert.

Nein. Die Daten werden auf der Festplatte gespeichert, weil die nicht verlohren gehen dürfen, wenn der Rechner abstürtzt. Das hat aber alles überhaupt nichts mit diesem Artikel zu tun! -- hauix 15:21, 6. Sep 2005 (CEST)

Man spricht hier auch von Primär- und Sekundärspeicher.

Worauf bezieht sich das? Wer ist Primär und wer Sekundärspeicher? Was hat das für eine Relevanz für diesen Artikel? -- hauix 15:21, 6. Sep 2005 (CEST)

Indexstrukturen wie B-Bäume werden für die effiziente Verwaltung dieser Daten benötigt. Sie erlauben das sehr schnelle Suchen von Datensätzen in einer Datenbank.

Das Stichwort "Indexstruktur" finde ich gut. -- hauix 15:21, 6. Sep 2005 (CEST)
Aber, worauf bezieht sich "dieser Daten"? Wichtig ist doch wohl das Verwalten von Daten in einem Speicher mit ganz gewissen Eigenschaften. -- hauix 15:21, 6. Sep 2005 (CEST)
Die Einschränkung auf Suchen ist unpräzise. -- hauix 15:21, 6. Sep 2005 (CEST)

Dabei spielen die langen Wartezeiten bei einer Lese- und Schreiboperation vom Sekundärspeicher eine wichtige Rolle.

Hier hat ein neuer Absatz angefangen. Ein Absatz, der mit Dabei anfängt ist schlechter Stil. Entweder, der Absatzt bezieht sich so nahe auf das Vorgehende, dass ein Dabei gerechtfertigt ist, dann gibt es keinen Grund, einen Absatzt zu machen, oder aber der Bezug dieses Dabei ist ungenau. -- hauix 15:21, 6. Sep 2005 (CEST)

Ein Zugriff auf die Festplatte dauert um ein vielfaches länger als ein Zugriff auf den Hauptspeicher. Daher gilt als wichtige Kenngröße für Datenbankalgorithmen, die Anzahl der Lese-/Schreiboperationenen auf den Sekundärspeicher. B-Bäume minimieren die Anzahl dieser Zugriffe pro Suchanfrage an die Datenbank.

"Zugriff" ist ungenau. Der Trick bei B-Bäumen ist das Einlesen großer Datenmengen auf einen Streich. Nur weil das schnell geht sind sie effizient. -- hauix 15:21, 6. Sep 2005 (CEST)

Die Idee dabei ist, dass ein B-Baum ähnlich zu einem Binärbaum an jedem Knoten verzweigt und damit die Suche auf den Teilbaum unterhalb eines Zweiges einschränkt.

Schon wieder ein Absatz, der mit Dabei anfängt! -- hauix 15:21, 6. Sep 2005 (CEST)
Das die Idee sein soll, dass ein B-Baum ein Baum ist (weil er verzweigt) kann ja wohl nicht Dein Ernst sein!!! -- hauix 15:21, 6. Sep 2005 (CEST)

Ein wesentlicher Unterschied ist aber, dass er nicht nur zwei Teilbäumen gibt, sondern eine grosse Anzahl von Teilbäumen.

er? -- hauix 15:21, 6. Sep 2005 (CEST)
Dopplung von "Teilbäumen", schwerfällig. -- hauix 15:21, 6. Sep 2005 (CEST)

Massgeblich für die Anzahl von Verzweigungen pro Knoten ist die Anzahl der Daten, die mit einer Leseoperation vom Sekundärspeicher gelesen werden kann.

Wieso soll für die Anzahl der Verzweigungen die Anzahl der Daten pro Leseoperation maßgeblich sein? Willst Du den Leser jetzt vollkommen verwirren??? -- hauix 15:21, 6. Sep 2005 (CEST)

Damit wird sichergestellt, dass nur wenige Operationen nötig sind, um möglichst viele Teilbäume durchsuchen zu können.

Womit wird was sichergestellt? Eine Maßgeblichkeit stellt nichts sicher! -- hauix 15:21, 6. Sep 2005 (CEST)

Die Anzahl der Verzweigungen pro Knoten wird als Verzweigungsgrad bezeichnet.

Das ist klar und sollte bei Baum und nicht bei B-Baum erklärt werden. Dafür einen eigenen Satzt von den gewünschten 12 zu spendieren ist pure Verschwendung! -- hauix 15:21, 6. Sep 2005 (CEST)

Für praktische Anwendungsfälle reduzierten B-Bäume die Zugriffe pro Anfrage auf eine kleine Anzahl von Leseoperationen. 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 aber 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.

Bevor ich angefangen habe zu meckern wusste ich noch gar nicht, dass es so schlimm ist. Ich werde Deine Änderungen zurücknehmen und lade Dich nocheinmal ausdrücklich ein, mir anhand meiner Version zu erklären, was Du nicht verstehst, oder was du meinst, dass andere, die sich fortgeschrittene Themen der Algorithmentechnik interessieren, daran nicht verstehen könnten. Dann können wird gerne zusammen, oder unter Hinzunahme anderer Interessierter die Probleme reparieren.

In der Hoffnung auf besser werdende Zusammenarbeit. Liebe Grüße -- hauix 15:21, 6. Sep 2005 (CEST).

Lieber Huix, Du nervst. -- sparti 15:29, 6. Sep 2005 (CEST)