Abstrakt
Metody externího třídění, tedy třídění využívajícího vnější paměť, jsou velmi dobře známy již mnoho desetiletí. Tyto metody byly původně navrženy pro systémy s malým množstvím interní paměti a magnetickými páskami coby vnější pamětí.
Magnetické pásky jsou specifické čistě sekvenčním přístupem k datům, který také ovlivnil návrh metod externího třídění. Pásky byly nahrazeny pevnými disky s~magnetickými plotnami, které přinesly možnost náhodného přístupu k datům, avšak sekvenční přístup zůstal nadále výrazně výkonnější.
Většina hardwarových předpokladů, na kterých je externí třídění postaveno se za poslední desetiletí výrazně změnila, zejména s příchodem SSD disků a vývojem non-volatilních pamětí. V tomto článku představujeme nový přístup k externímu třídění, který reflektuje parametry současného hardware.
Dále předkládáme empirické srovnání s již existujícími metodami, které se hojně používají v soudobých systémech.