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.
I REF föreslår författarna att block från olika körningar placeras i på varandra följande diskadresser för att minska sökandet overhead under sammanslagningsfasen (på bekostnad av extra sökkostnad under körning).
Speeding up External Mergesort
{'venue': 'IEEE Transactions on Knowledge and Data Engineering', 'journal': None, 'mag_field_of_study': ['Computer Science']}