1

7.1 Externes Suchen

• Bisherige Algorithmen: geeignet, wenn alle Daten im Hauptspeicher.

• Große Datenmengen: oft auf externen Speichermedien, z.B. Festplatte.

Zugriff: immer gleich auf einen ganzen Block (eine Seite) von Daten, z.B: 4096 Bytes.

Effizienz: Zahl der Seitenzugriffe klein halten!

2

Für externes Suchen: Variante von Suchbäumen mit:Knoten = Seite

Vielwegsuchbäume!

3

Definition (Vielweg-Suchbaum)

Der leere Baum ist ein Vielweg-Suchbaum mit der Schlüsselmenge {}.

Seien T0, ..., Tn Vielweg-Suchbäume mit Schlüsseln aus einer gemeinsamen Schlüsselmenge S, und sei k1,...,kn eine Folge von Schlüsseln mit k1 < ...< kn. Dann ist die Folge

T0 k1 T1 k2 T2 k3 .... kn Tn

ein Vielweg-Suchbaum genau dann, wenn:

• für alle Schlüssel x aus T0 gilt: x < k1 • für i=1,...,n-1, für alle Schlüssel x in Ti gilt: ki < x < ki+1, • für alle Schlüssel x aus Tn gilt: kn < x .

4

B-Baum

Definition 7.1.2

Ein B-Baum der Ordnung m ist ein Vielweg-Suchbaum mit folgenden Eigenschaften

• 1 #(Schlüssel in Wurzel) 2m und m #(Schlüssel in Knoten) 2m für alle anderen Knoten.• Alle Pfade von der Wurzel zu einem Blatt sind gleichlang. • Jeder innere Knoten mit s Schlüsseln hat genau s+1 Söhne.

5

Beispiel: Ein B-Baum der Ordnung 2:

6

Abschätzungen zu B-Bäumen

Ein minimal gefüllter B-Baum der Ordnung m und Höhe h:• Knotenzahl im linken wie im rechten Teilbaum

1 + (m+1) + (m+1)2 + .... + (m+1)h-1

= ( (m+1)h – 1) / m.

Die Wurzel hat einen Schlüssel, alle anderen Knoten haben m Schlüssel.

Insgesamt: Schlüsselzahl n in einem B-Baum der Höhe h: n 2 (m+1)h – 1

Also gilt für jeden B-Baum der Höhe h mit n Schlüsseln:h logm+1 ((n+1)/2) .

7

BeispielAlso gilt für jeden B-Baum der Höhe h mit n Schlüsseln:

h logm+1 ((n+1)/2).

Beispiel: Bei• Seitengröße: 1 KByte und • jeder Eintrag nebst Zeiger: 8 Byte, kann m=63 gewählt werden, und bei • einer Datenmenge von n= 1000 000 folgt

h log 64 500 000.5 < 4 und damit hmax = 3.

8

7.1 Externes Suchen

Definition 7.1.2

Ein B-Baum der Ordnung m ist ein Vielweg-Suchbaum mit folgenden Eigenschaften

• 1 #(Schlüssel in Wurzel) 2m und m #(Schlüssel in Knoten) 2m für alle anderen Knoten.• Alle Pfade von der Wurzel zu einem Blatt sind gleichlang. • Jeder innere Knoten mit s Schlüsseln hat genau s+1 Söhne.

9

Beispiel: Ein B-Baum der Ordnung 2:

10

Abschätzungen zu B-Bäumen

Ein minimal gefüllter B-Baum der Ordnung m und Höhe h:• Knotenzahl im linken wie im rechten Teilbaum

1 + (m+1) + (m+1)2 + .... + (m+1)h-1

= ( (m+1)h – 1) / m.

Die Wurzel hat einen Schlüssel, alle anderen Knoten haben m Schlüssel.

Insgesamt: Schlüsselzahl n in einem B-Baum der Höhe h: n 2 (m+1)h – 1

Also gilt für jeden B-Baum der Höhe h mit n Schlüsseln:h logm+1 ((n+1)/2) .

11

BeispielAlso gilt für jeden B-Baum der Höhe h mit n Schlüsseln:

h logm+1 ((n+1)/2).

Beispiel: Bei• Seitengröße: 1 KByte und • jeder Eintrag nebst Zeiger: 8 Byte, kann m=63 gewählt werden, und bei • einer Datenmenge von n= 1000 000 folgt

h log 64 500 000.5 < 4 und damit hmax = 3.

12

Algorithmen zum Einfügen und Löschen von Schlüsseln in B-Bäumen

Algorithmus insert (root, x) //füge Schlüssel x in den Baum mit Wurzelknoten root ein suche nach x im Baum mit Wurzel root; wenn x nicht gefunden { sei p Blatt, an dem die Suche endete; füge x an der richtigen Position ein; wenn p nun 2m+1 Schlüssel {overflow(p)} }

13

Algorithmus overflow (p) = split (p)

Algorithmus split (p) Erster Fall: p hat einen Vater

q.

Zerlege den übervollen Knoten. Der mittlere Schlüssel wandert in den Vater.

Anmerkung: das Splitting muss evtl. bis zur Wurzel wiederholt werden.

Algorithmus Split (1)

14

Algorithmus split (p) Zweiter Fall: p ist die

Wurzel.

Zerlege den übervollen Knoten. Eröffne eine neue Ebene nach oben mit einer neuen Wurzel mit dem mittleren Schlüssel.

Algorithmus Split (2)

15

//entferne Schlüssel x aus dem Baum mit Wurzel root suche nach x im Baum mit Wurzel root; wenn x gefunden { wenn x in einem inneren Knoten liegt { vertausche x mit dem nächstgrößeren Schlüssel x' im Baum // wenn x in einem inneren Knoten liegt, gibt // es einen nächstgrößeren Schlüssel // im Baum, und dieser liegt in einem Blatt } sei p das Blatt, das x enthält; lösche x aus p; wenn p nicht die wurzel ist { wenn p m-1 Schlüssel hat {underflow (p)} } }

Algorithmus delete (root ,x)

16

Algorithmus underflow (p)

// behandle die Unterläufe des Knoten p wenn p einen Nachbarknoten hat mit s>m Knoten { balance (p,p') } anderenfalls // da p nicht die Wurzel sein kann, muss p Nachbarn mit m

Schlüsseln haben { sei p' Nachbar mit m Schlüsseln; merge (p,p')}

17

Algorithmus balance (p, p') // balanciere Knoten p mit seinem Nachbarknoten p'

(s > m , r = (m+s)/2 -m )

18

Algorithmus merge (p,p') // verschmelze Knoten p mit seinem Nachbarknoten Führe die folgende Operation durch:

Anschließend:wenn ( q <> Wurzel)

und (q hat m-1 Schlüssel) underflow (q)

anderenfalls (wenn (q= Wurzel) und (q leer)) {gib q frei und lasse root auf p^ zeigen}

19

Rekursion

Wenn es bei underflow zu merge kommt, muss evtl. underflow eine Ebene höher wiederholt werden.

Dies kann sich bis zur Wurzel fortsetzen.

20

Beispiel:B-Baum derOrdnung 2

21

Aufwand

Sei m die Ordnung des B-Baums, n die Zahl der Schlüssel.

Aufwand für Suchen, Einfügen, Entfernen: O(h) = O(logm+1 ((n+1)/2) ) = O(logm+1(n)).

22

Anmerkung:

B-Bäume auch als interne Speicherstruktur zu gebrauchen:

Besonders: B-Bäume der Ordnung 1 (dann nur 1 oder 2 Schlüssel pro Knoten – keine aufwändige Suche innerhalb von Knoten).

Aufwand für Suchen, Einfügen, Löschen: O(log n).

23

Anmerkung: Speicherplatzausnutzung: über 50%Grund: die Bedingung:

1/2•k #(Schlüssel in Knoten) k Für Knoten Wurzel

(k=2m)

24

Noch höhere Speicherplatzausnutzung möglich, z.B. über 66% mit Bedingung:

2/3•k #(Schlüssel in Knoten) kfür alle Knoten mit Ausnahme der Wurzel und ihrer

Kinder.

Erreichbar durch 1) modifiziertes Balancieren auch beim Einfügen und 2) split erst, wenn zwei Nachbarn ganz voll.

Nachteil: Häufigere Reorganisation beim Einfügen und Löschen notwendig.