B-Baum - Versionsgeschichte

Kowa am 16. März 2015 um 08:33 Uhr

2015-03-16T08:33:34Z

← Nächstältere Version		Version vom 16. März 2015, 08:33 Uhr
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$

Kowa am 16. März 2015 um 08:25 Uhr

2015-03-16T08:25:17Z

← Nächstältere Version		Version vom 16. März 2015, 08:25 Uhr
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>~~		<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" sons. The root is a leaf or has at least two sons.~~</li>~~		<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>~~		<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>~~		<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" Söhne. Die Wurzel ist entweder ein Blatt oder hat mindestens zwei Söhne.~~</li>~~		<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>~~		<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]]

Kowa am 16. März 2015 um 08:22 Uhr

2015-03-16T08:22:11Z

← Nächstältere Version		Version vom 16. März 2015, 08:22 Uhr
Zeile 11:		Zeile 11:
	}}		}}

	==Definition (Bayer, McCreight 1970<ref>{{Quelle\|Bayer, McCreight (1970)}}</ref>)==		==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 20:		Zeile 20:
	<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>		<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>
	<li>Each node has at most $2k +1$ sons.</li>		<li>Each node has at most $2k +1$ sons.</li>
			</ol>

			=Ü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$
			entweder leer ist ($h=0$) oder folgende Eigenschaften hat:

			<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>
			<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>
			<li>Jeder Knoten hat höchstens $2k +1$ Söhne.</li>
	</ol>		</ol>
	==Beispiel für einen B-Baum==		==Beispiel für einen B-Baum==

Kowa am 16. März 2015 um 08:15 Uhr

2015-03-16T08:15:01Z

← Nächstältere Version		Version vom 16. März 2015, 08:15 Uhr
Zeile 1:		Zeile 1:
			Der [[B-Baum]] ist ein eine spezielle [[Datenstruktur]] zur effizienten Speicherung und Verwaltung von Massendaten auf einem
			Massenspeicher mit [[wahlfreier Zugriff\|wahlfreiem Zugriff]], wie [[Festplatte]] oder [[SSD]].
			Ein B-Baum ist vollständig balanziert und sehr flach, dafür aber sehr breit.

	{{Qualität		{{Qualität
	\|correctness = 4		\|correctness = 4
Zeile 6:		Zeile 10:
	\|conformance = 3		\|conformance = 3
	}}		}}
	~~Der [[B-Baum]] ist ein eine spezielle [[Datenstruktur]] zur effizienten Speicherung und Verwaltung von Massendaten auf einem~~
	~~Massenspeicher mit [[wahlfreier Zugriff\|wahlfreiem Zugriff]], wie [[Festplatte]] oder [[SSD]].~~
	~~Ein B-Baum ist vollständig balanziert und sehr flach, dafür aber sehr breit.~~

	==Definition (Bayer, McCreight 1970<ref>{{Quelle\|Bayer, McCreight (1970)}}</ref>)==		==Definition (Bayer, McCreight 1970<ref>{{Quelle\|Bayer, McCreight (1970)}}</ref>)==

Kowa am 16. März 2015 um 08:13 Uhr

2015-03-16T08:13:47Z

← Nächstältere Version		Version vom 16. März 2015, 08:13 Uhr
Zeile 10:		Zeile 10:
	Ein B-Baum ist vollständig balanziert und sehr flach, dafür aber sehr breit.		Ein B-Baum ist vollständig balanziert und sehr flach, dafür aber sehr breit.

	==Definition (Bayer, McCreight 1970<ref>{{Quelle\|Bayer, McCreight (1970)}}</ref><)==		==Definition (Bayer, 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 25:		Zeile 25:
	==Quellen==		==Quellen==
	<references/>		<references/>
	<ol start = "4">		<ol start = "2">
	<li>{{Quelle\|Bayer, McCreight (1972)}}		<li>{{Quelle\|Bayer, McCreight (1972)}}
	<li>{{Quelle\|Bayer (1982)}}		<li>{{Quelle\|Bayer (1982)}}
	</ol>		</ol>

Kowa am 16. März 2015 um 08:12 Uhr

2015-03-16T08:12:49Z

← Nächstältere Version		Version vom 16. März 2015, 08:12 Uhr
Zeile 10:		Zeile 10:
	Ein B-Baum ist vollständig balanziert und sehr flach, dafür aber sehr breit.		Ein B-Baum ist vollständig balanziert und sehr flach, dafür aber sehr breit.

	==Definition (Bayer, McCreight 1970<ref>{{Quelle\|Bayer, McCreight (1970)}}</ref><~~ref>{{Quelle\|Bayer, McCreight (1972)}}</ref><ref>{{Quelle\|Bayer (1982)}}</ref>~~)==		==Definition (Bayer, 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$
			is either empty ($h=0$) or has the flollowing properties:

			<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>
			<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>
			<li>Each node has at most $2k +1$ sons.</li>
			</ol>
	==Beispiel für einen B-Baum==		==Beispiel für einen B-Baum==
	[[Datei:Beispiel_B_Baum.png]]		[[Datei:Beispiel_B_Baum.png]]
Zeile 18:		Zeile 26:
	<references/>		<references/>
	<ol start = "4">		<ol start = "4">
			<li>{{Quelle\|Bayer, McCreight (1972)}}
			<li>{{Quelle\|Bayer (1982)}}
	</ol>		</ol>

Kowa am 16. März 2015 um 08:04 Uhr

2015-03-16T08:04:10Z

← Nächstältere Version		Version vom 16. März 2015, 08:04 Uhr
Zeile 10:		Zeile 10:
	Ein B-Baum ist vollständig balanziert und sehr flach, dafür aber sehr breit.		Ein B-Baum ist vollständig balanziert und sehr flach, dafür aber sehr breit.

	=Definition (Bayer, McCreight 1970<ref>{{Quelle\|Bayer, McCreight (1970)}}</ref><ref>{{Quelle\|Bayer, McCreight (1972)}}</ref><ref>{{Quelle\|Bayer (1982)}}</ref>)=		==Definition (Bayer, McCreight 1970<ref>{{Quelle\|Bayer, McCreight (1970)}}</ref><ref>{{Quelle\|Bayer, McCreight (1972)}}</ref><ref>{{Quelle\|Bayer (1982)}}</ref>)==

	=Beispiel für einen B-Baum=		==Beispiel für einen B-Baum==
	[[Datei:Beispiel_B_Baum.png]]		[[Datei:Beispiel_B_Baum.png]]

	=Quellen=		==Quellen==
	<references/>		<references/>
	<ol start = "4">		<ol start = "4">
	</ol>		</ol>

Kowa am 16. März 2015 um 08:03 Uhr

2015-03-16T08:03:45Z

← Nächstältere Version		Version vom 16. März 2015, 08:03 Uhr
Zeile 10:		Zeile 10:
	Ein B-Baum ist vollständig balanziert und sehr flach, dafür aber sehr breit.		Ein B-Baum ist vollständig balanziert und sehr flach, dafür aber sehr breit.

	=Definition (Bayer, McCreight 1970<ref>{{Quelle\|Bayer, McCreight (1970)}}</ref>)		=Definition (Bayer, McCreight 1970<ref>{{Quelle\|Bayer, McCreight (1970)}}</ref><ref>{{Quelle\|Bayer, McCreight (1972)}}</ref><ref>{{Quelle\|Bayer (1982)}}</ref>)=

	=Beispiel für einen B-Baum=		=Beispiel für einen B-Baum=
Zeile 17:		Zeile 17:
	=Quellen=		=Quellen=
	<references/>		<references/>
	<ol start = "2">		<ol start = "4">
	~~<li> {{Quelle\|Bayer, McCreight (1972)}}~~
	~~<li> {{Quelle\|Bayer (1982)}}~~
	</ol>		</ol>

Kowa am 16. März 2015 um 08:00 Uhr

2015-03-16T08:00:57Z

← Nächstältere Version		Version vom 16. März 2015, 08:00 Uhr
Zeile 10:		Zeile 10:
	Ein B-Baum ist vollständig balanziert und sehr flach, dafür aber sehr breit.		Ein B-Baum ist vollständig balanziert und sehr flach, dafür aber sehr breit.

			=Definition (Bayer, McCreight 1970<ref>{{Quelle\|Bayer, McCreight (1970)}}</ref>)

	=Beispiel für einen B-Baum=		=Beispiel für einen B-Baum=
Zeile 15:		Zeile 16:

	=Quellen=		=Quellen=
	* {{Quelle:Bayer, McCreight (1970)}}		<references/>
	* {{Quelle:Bayer, McCreight (1972)}}		<ol start = "2">
	* {{Quelle:Bayer (1982)}}		<li> {{Quelle\|Bayer, McCreight (1972)}}
			<li> {{Quelle\|Bayer (1982)}}
			</ol>

Kowa am 16. März 2015 um 07:57 Uhr

2015-03-16T07:57:28Z

← Nächstältere Version		Version vom 16. März 2015, 07:57 Uhr
Zeile 1:		Zeile 1:
	{{Qualität		{{Qualität
	\|correctness = 0		\|correctness = 4
	\|extent = 2		\|extent = 2
	\|numberOfReferences = 3		\|numberOfReferences = 4
	\|qualityOfReferences = 3		\|qualityOfReferences = 5
	\|conformance = 3		\|conformance = 3
	}}		}}
	Der [[B-Baum]] ist ein eine spezielle ~~Datenstruktur – ein sehr breiter, aber flacher, vollständig balanzierter~~ [[~~Baum~~]] – zur Speicherung von Massendaten ~~in einer~~ [[~~Datei~~]].		Der [[B-Baum]] ist ein eine spezielle [[Datenstruktur]] zur effizienten Speicherung und Verwaltung von Massendaten auf einem
			Massenspeicher mit [[wahlfreier Zugriff\|wahlfreiem Zugriff]], wie [[Festplatte]] oder [[SSD]].
			Ein B-Baum ist vollständig balanziert und sehr flach, dafür aber sehr breit.

	~~=Eigenschaften=~~
	* der B-Baum ist vollständig balanciert, d.h. die gleiche Tiefe von der Wurzel zum Blatt
	* pro Knoten mind. n und max. 2n Schlüssel (n ⩽ m ⩽ 2n Datensätze)
	* Wurzel mind. 1 oder max 2n Schlüssel (1 ⩽ m ⩽ 2n Datensätze)
	* jeder Knoten mit n Schlüssel (außer den Blättern) hat n+1 Kindknoten
	* der Baum und alle Schlüssel sind sortiert
	* Knoten mit 0 Kindknoten heißen Blätter, diese liegen beim B-Baum auf einer Ebene.

	=Beispiel für einen B-Baum=		=Beispiel für einen B-Baum=
Zeile 20:		Zeile 15:

	=Quellen=		=Quellen=
	*~~Objektrelationale Datenbanken, Can Türker, Gunter Saake, 2006~~, ~~ISBN 3-89864-190-2~~		* {{Quelle:Bayer, McCreight (1970)}}
	* ~~http~~:~~//mmdb.hs-augsburg.de/literatur/~~		* {{Quelle:Bayer, McCreight (1972)}}
	* http://cis.cs.tu-berlin.de/Lehre/WS-0304/Sonstiges/db-pages/Inhalt/datenorganisation/Folien		* {{Quelle:Bayer (1982)}}
	* ~~http~~:~~//de.wikipedia.org/wiki/B-Baum~~