Tri de fusion multiway bidirectionnel

Question

Ceci est une question du livre 'Database Systems Le livre complet, 2e édition' - Chapitre 15: Algorithme à deux passes basé sur le tri. "Parfois, il est possible de sauvegarder des E/S de disque si nous laissons la dernière sous-liste en mémoire Il peut même être judicieux d'utiliser des sous-listes de moins de blocs pour profiter de cet effet. de peuvent être sauvés de cette façon? " J'ai compris que vous divisez la relation d'origine en sous-listes et que vous les triez dans la première passe, et conservez la dernière liste en mémoire, qui occupera moins de M-1. Alors, comment progressez-vous avec le tri?

Answer 1

Ceci est juste une supposition, mais je soupçonne que la réponse peut être décrite comme suit. Standard « niveau au-un-temps » fusion ressemble tri comme ceci:

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

Notez ici que nous effectuons une passe complète des données d'entrée avant de passer au niveau suivant.

Une alternative est « sous-arbre-à-un-temps » fusion de tri, qui ressemble à ceci:

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

Ici, nous fusionnons chaque sous-arbre avec son voisin de la même hauteur que dès que le voisin a été construit. Nous faisons la même quantité de travail, mais la localité est améliorée.

Cheers.