B-Baum: Unterschied zwischen den Versionen
aus GlossarWiki, der Glossar-Datenbank der Fachhochschule Augsburg
Kowa (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Kowa (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
(Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt) | |||
Zeile 11: | Zeile 11: | ||
}} | }} | ||
==Definition ([[Rudolf Bayer|Bayer]], [[Edward McCreight|McCreight]] 1970<ref>{{Quelle|Bayer, McCreight (1970)}}</ref>)== | ==Graphentheoretische Definition ([[Rudolf Bayer|Bayer]], [[Edward McCreight|McCreight]] 1970<ref>{{Quelle|Bayer, McCreight (1970)}}</ref>)== | ||
Let $h \ge 0$ be an integer, $k$ a natural number. A directed tree $T$ is in the class $\tau(k,h)$ of [[B-Tree]]s if $T$ | Let $h \ge 0$ be an integer, $k$ a natural number. A directed tree $T$ is in the class $\tau(k,h)$ of [[B-Tree]]s if $T$ | ||
Zeile 17: | Zeile 17: | ||
<ol style="list-style-type: lower-roman;"> | <ol style="list-style-type: lower-roman;"> | ||
<li>Each path from the root to any leaf has the same length $h$, also called the ''height'' of $T$. i.e., $h$ = number of nodes in path. | <li>Each path from the root to any leaf has the same length $h$, also called the ''height'' of $T$. i.e., $h$ = number of nodes in path. | ||
<li>Each node except the root and the leaves has at least $k + 1 | <li>Each node except the root and the leaves has at least $k + 1$ sons. The root is a leaf or has at least two sons. | ||
<li>Each node has at most $2k +1$ sons. | <li>Each node has at most $2k +1$ sons. | ||
</ol> | </ol> | ||
=Übersetzung ([[Wolfgang Kowarschick|Kowarschick]] 2015)= | ===Übersetzung ([[Wolfgang Kowarschick|Kowarschick]] 2015)=== | ||
Es seien $h \ge 0$ eine ganze Zahl und $k$ eine natürliche Zahl [größer Null]. Ein [[gerichteter Baum]] $T$ ist Element der [[Klasse]] $\tau(k,h)$ von [[B-Tree|B-Bäumen]], wenn $T$ | Es seien $h \ge 0$ eine ganze Zahl und $k$ eine natürliche Zahl [größer Null]. Ein [[gerichteter Baum]] $T$ ist Element der [[Klasse]] $\tau(k,h)$ von [[B-Tree|B-Bäumen]], wenn $T$ | ||
Zeile 28: | Zeile 28: | ||
<ol style="list-style-type: lower-roman;"> | <ol style="list-style-type: lower-roman;"> | ||
<li>Jeder Pfad von der Wurzel zu irgendeinem Blatt hat dieselbe Länge $h$, welche auch die ''Höhe'' von $T$ genannt wird. Das heißt, $h$ = Anzahl der Knoten im Pfad. | <li>Jeder Pfad von der Wurzel zu irgendeinem Blatt hat dieselbe Länge $h$, welche auch die ''Höhe'' von $T$ genannt wird. Das heißt, $h$ = Anzahl der Knoten im Pfad. | ||
<li>Jeder Konten mit Ausnahme der Wurzel und der Blätter hat mindestens $k + 1 | <li>Jeder Konten mit Ausnahme der Wurzel und der Blätter hat mindestens $k + 1$ Söhne. Die Wurzel ist entweder ein Blatt oder hat mindestens zwei Söhne. | ||
<li>Jeder Knoten hat höchstens $2k +1$ Söhne. | <li>Jeder Knoten hat höchstens $2k +1$ Söhne. | ||
</ol> | </ol> | ||
==Beispiel für einen B-Baum== | ==Beispiel für einen B-Baum== | ||
[[Datei:Beispiel_B_Baum.png]] | [[Datei:Beispiel_B_Baum.png]] |
Aktuelle Version vom 16. März 2015, 10:33 Uhr
Der B-Baum ist ein eine spezielle Datenstruktur zur effizienten Speicherung und Verwaltung von Massendaten auf einem Massenspeicher mit wahlfreiem Zugriff, wie Festplatte oder SSD. Ein B-Baum ist vollständig balanziert und sehr flach, dafür aber sehr breit.
Dieser Artikel erfüllt die GlossarWiki-Qualitätsanforderungen nur teilweise:
Korrektheit: 4 (großteils überprüft) |
Umfang: 2 (wichtige Fakten fehlen) |
Quellenangaben: 4 (fast vollständig vorhanden) |
Quellenarten: 5 (ausgezeichnet) |
Konformität: 3 (gut) |
Graphentheoretische Definition (Bayer, McCreight 1970[1])
Let $h \ge 0$ be an integer, $k$ a natural number. A directed tree $T$ is in the class $\tau(k,h)$ of B-Trees if $T$ is either empty ($h=0$) or has the flollowing properties:
- Each path from the root to any leaf has the same length $h$, also called the height of $T$. i.e., $h$ = number of nodes in path.
- Each node except the root and the leaves has at least $k + 1$ sons. The root is a leaf or has at least two sons.
- Each node has at most $2k +1$ sons.
Übersetzung (Kowarschick 2015)
Es seien $h \ge 0$ eine ganze Zahl und $k$ eine natürliche Zahl [größer Null]. Ein gerichteter Baum $T$ ist Element der Klasse $\tau(k,h)$ von B-Bäumen, wenn $T$ entweder leer ist ($h=0$) oder folgende Eigenschaften hat:
- Jeder Pfad von der Wurzel zu irgendeinem Blatt hat dieselbe Länge $h$, welche auch die Höhe von $T$ genannt wird. Das heißt, $h$ = Anzahl der Knoten im Pfad.
- Jeder Konten mit Ausnahme der Wurzel und der Blätter hat mindestens $k + 1$ Söhne. Die Wurzel ist entweder ein Blatt oder hat mindestens zwei Söhne.
- Jeder Knoten hat höchstens $2k +1$ Söhne.
Beispiel für einen B-Baum
Quellen
- Bayer, McCreight (1972): Rudolf Bayer und Edward M. McCreight; Organization and Maintenance of Large Ordered Indexes; in: Acta Informatica; Band: 1; Nummer: 3; Seite(n): 173-189; Verlag: Springer-Verlag; Web-Link; 1972; Quellengüte: 5 (Artikel)
- Bayer (1982): Rudolf Bayer; Datenstrukturen – Kurseinheit 6: Datenstrukturen für Peripheriespeicher; Band: 6; Hochschule: Fernuniversität – Gesamthochschule – in Hagen; Adresse: Hagen; 1982; Quellengüte: 4 (Skript)