+ All Categories
Home > Documents > 7.1 Externes Suchen

7.1 Externes Suchen

Date post: 23-Feb-2016
Category:
Upload: arnold
View: 51 times
Download: 0 times
Share this document with a friend
Description:
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. - PowerPoint PPT Presentation
24
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!
Transcript
Page 1: 7.1 Externes Suchen

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!

Page 2: 7.1 Externes Suchen

2

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

Vielwegsuchbäume!

Page 3: 7.1 Externes Suchen

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 .

Page 4: 7.1 Externes Suchen

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.

Page 5: 7.1 Externes Suchen

5

Beispiel: Ein B-Baum der Ordnung 2:

Page 6: 7.1 Externes Suchen

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) .

Page 7: 7.1 Externes Suchen

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.

Page 8: 7.1 Externes Suchen

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.

Page 9: 7.1 Externes Suchen

9

Beispiel: Ein B-Baum der Ordnung 2:

Page 10: 7.1 Externes Suchen

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) .

Page 11: 7.1 Externes Suchen

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.

Page 12: 7.1 Externes Suchen

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)} }

Page 13: 7.1 Externes Suchen

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)

Page 14: 7.1 Externes Suchen

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)

Page 15: 7.1 Externes Suchen

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)

Page 16: 7.1 Externes Suchen

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')}

Page 17: 7.1 Externes Suchen

17

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

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

Page 18: 7.1 Externes Suchen

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}

Page 19: 7.1 Externes Suchen

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.

Page 20: 7.1 Externes Suchen

20

Beispiel:B-Baum derOrdnung 2

Page 21: 7.1 Externes Suchen

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)).

Page 22: 7.1 Externes Suchen

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).

Page 23: 7.1 Externes Suchen

23

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

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

(k=2m)

Page 24: 7.1 Externes Suchen

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.


Recommended