Extern fusionssort implementeras normalt så att varje körning lagras kontinuerligt på disk och datablock avläses exakt i den ordning de behövs vid sammanslagning. Vi undersöker två idéer för att förbättra prestandan för extern sammanslagningsort: interleaved layout och en ny lässtrategi. Inbunden layout placerar block från di erent körs i på varandra följande diskadresser. Detta görs i hopp om att interleaving kommer att minska söka overhead vid sammanslagning. Den nya lässtrategin förberäknar i vilken ordning datablock ska läsas beroende på var de finns på disken och när de behövs för sammanslagning. Extra utrymme gör det möjligt att läsa block i en ordning som minskar söka overhead, istället för att läsa dem exakt i den ordning de behövs för sammanslagning. En detaljerad simuleringsmodell användes för att jämföra de två layoutstrategierna och tre lässtrategier. Eekterna av att använda flera arbetsdiskar undersöktes också. Vi fann att, i de flesta fall, interleaded layout inte förbättrar prestanda, men att den nya lässtrategin konsekvent presterar bättre än dubbel bu ering och prognostisering.
Zheng och Larson introducerade en ny lässtrategi för extern sammanslagningsort som konsekvent presterar bättre än dubbel buffring och prognos REF.
Speeding up External Mergesort
{'venue': 'IEEE Transactions on Knowledge and Data Engineering', 'journal': None, 'mag_field_of_study': ['Computer Science']}