Forschung
Fotografie - Sammlung  
 
  Dokumentationen
    Allerlei
Formeln -- >
Einfgen eines Records -- >

[ERKLÄRUNG]


Baumstrukturen sind zur schnelleren Durchsuchung von Datenbeständen da. Würde man eine Liste verschiedener Flughafenbezeichnungen von oben nach unten durchparsen, würde dies unter umständen läger dauern, als wenn man die Liste in Segmente unterteilt hätte.
Ein weiterer Vorteil der Unterteilung, ist eine effizientere und schnellere Reorganisation der Daten. Meist sind nach ändern von einzelnen Blöcken nur lokale Modifikationen notwendig, Modifikationen die die gesamte Struktur betreffen, sind eher Ausnahmefälle und daher ebenfalls effizient durchführbar. Wenn man die Liste in verschiedene Segmente unterteilt, so ergibt sich eine Baumstruktur. Diese Unterteilung kann so z.B. aussehen:



Ein B-Baum (Kurzbezeichnung für balancierter Baum) ist ein gerichteter Baum, in welchem jeder Pfad von der Wurzel zu einem Blatt die gleiche Länge hat und für dessen Knoten folgendes gilt:

1. Jeder Knoten des Baumes repräsentiert einen Speicherblock fester Länge und enthält mindestens k sowie 2k Records konstanter Länge für eine fest vorgegebene natürliche Zahl k

2. Jeder Record besteht aus einem Schlüssel- sowie einem Nichtschlüssel-Anteil

3. Jeder Block ist nach aufsteigenden Schlüsselwerten sortiert, und jeder Vater stellt einen Index für seine Söhne dar

4. Die Wurzel hat keinen Sohn oder mindestens zwei Söhne

5. Jeder innere Knoten, welcher also weder Wurzel noch Blatt ist, hat die für ihn maximal mögliche Anzahl von Söhnen, dh. er hat n+1 Söhne, falls er n Schlüsselwerte enthält.

Ein B-Baum mu immer ausgeglichen sein; ein in der Wurzel beginnender Pfad, hat immer eine konstante Länge. Die Enden eines Pfades, werden Blätter genannt. Alles was darüberliegt, sind Knoten. In den Knoten gibt es Schlüsselwerte K (hier grau) und Zeiger P (schwarz dargestellt). Alle Zeiger vor (links) einem Schlüsselwert X, zeigen auf Knoten oder Blätter, deren enthaltene Schlüsselwerte "kleiner" als der obere Schlüsselwert X ist. Umgekehrt gilt für die andere Richtung, das alle Schlüsselwerte "gröer" als der obere Schlüsselwert X sind.






[EINFGEN EINES RECORDS]


Beim einfgen eines Schlsselwertes, ist zu beachten, das der Baum ausbalanciert bleiben mu. Wenn ich in dem hier dargestellten Baum den Schlsselwert 2 hinzufgen mchte, so






[FORMELN]


Für eine Suche mu im Mittel auf

log2 n

Knoten zugegriffen werden, falls die Datei n Records enthält.





Mi - Datenverwaltung
THEMEN:
Impressum
B* Bume