Zwei-Wege-Mehrwege-Merge-Sortierung

Question

Dies ist eine Frage aus dem Buch 'Datenbanksysteme Das komplette Buch, 2. Auflage' - Kapitel 15: Zwei-Durchlauf-Algorithmus basierend auf Sortierung. "Manchmal ist es möglich, einige Festplatten-E/As zu speichern, wenn wir die letzte Teilliste im Speicher belassen. Es kann sogar sinnvoll sein, Teillisten mit weniger als Blöcken zu verwenden. Wie viele Festplatten-E/A 's kann auf diese Weise gespeichert werden? "

Ich habe herausgefunden, dass Sie die ursprüngliche Relation in Unterlisten aufteilen und im ersten Durchlauf sortieren und die letzte Liste im Speicher behalten, die weniger als M-1-Block belegen wird. Wie gehst du mit dem Sortieren voran?

Answer 1

Das ist nur eine Vermutung, aber ich vermute, dass die Antwort wie folgt beschrieben werden kann. Standard „Level-at-a-time“ merge Sortierung sieht wie folgt aus:

1 1 1 1 1 1 1 1 
--- --- --- --- -- pass 1 
2 2 2 2 
----- ----- -- pass 2 
    4  4 
    ---------  -- pass 3 
     8 

Hinweis hier, dass wir einen vollständigen Durchlauf der Eingangsdaten, bevor sie auf die nächste Stufe durchzuführen.

Eine Alternative ist „Teilbaum-at-a-time“ merge Sortierung, die wie folgt aussieht:

1 1 1 1 1 1 1 1 
--- | | | | | | 
2 --- | | | | 
| 2 | | | | 
----- | | | | 
    4 --- | | 
    |  2 --- 
    |  | 2 
    |  ----- 
    |  4 
    --------- 
     8 

Hier sind wir jeden Teilbaum mit seinem Nachbarn in gleicher Höhe verschmelzenden, sobald dieser Nachbar wurde gebaut. Wir machen die gleiche Arbeit, aber die Lokalität wird verbessert.

Prost.