Aufgabe 1.4Eine Implementierung einer effiziente externe geordnete (!) lineare Liste

Operationen:Search(x)Insert(x)Delete(x)

Terminologie: B: die Blockgröße N: alle Elemente, die eingefügt werden

können I: Initialisierung der Blöcke soll mit I

Elementen erfolgen S: Schwellwert zum Verschmelzen der

Blöcke bei der Delete(x) Operation

Externe Listen:

Durchlaufe alle Blöcke im Speicher und lade jeweils einen Block in den Hauptspeicher um auf ihm zu suchen.

Analyse I/O Zugriffe: O(N/B)

Externe Listen: Search(x)

Suche auf der Datenstruktur in dem das Element mit Search(x) gesucht wird.

Lösche das gefundene Element Enthält der Block mit seinen Nachbarn

weniger als S Elemente, so verschmelzen wir diese zwei/drei zu einem einzigen.

Analyse I/O Zugriffe: O(N/B)

Externe Listen: Delete(x)

Suche den richtigen Block in der Datenstruktur Füge den neuen Wert ein -> so immer O(N/B) I/Os Aber Überlauf? Wenn im Nachbarblock ist noch Platz für ein

weiteres Element -> + 1 I/O Sonst erzeuge einen neuen Block zu den

Blöcken mit Überlauf, die dann wieder zu 2/3 voll sind

Externe Listen: Insert(x)