Allgemeines zum B-Baum / B*-Baum

Dastellung:  [B-Baum (K,H)]

K = Knoten, die vorgegebene zahl K ist der min wert für Elemente in einem Knoten, und max ist 2*k

H = Höhe, die vorgebene zahl H, ist die max. höhe die ein Baum erreichen darf (wobei die wurzel bereits 1 ist)

• wenn kein wert angegeben ist, heisst es, das es schlichtweg kein limit gibt.
• für die wurzel gilt stehts: anzahl elemente egal

für uns heisst das jetzt: [2,h]

• 2 Knoten = min 2 Elemente pro knoten, max 4 (2*k), sobald also ein 5ter hinzu kommt, muss dieser nach oben hin rausgeschoben werden.
• h = nicht gegeben, also kann es unendlich groß werden (in unserem fall wird die höhe bei 2 stoppen)

Formel zur Berechnung der Knoten

• minimal: 1(Wurzel) + 2/k*((k+1)^(h-1) – 1)
• maximal: (1/2k)*((2k+1)^h – 1)

Formel zur Berechnung der Anzahl der Elemente

• minimal:   2(k+1)^(h-1) + 1
• maximal: ( 2(k+1)^(h-1) ) – 1