외부 정렬(External Sort)

외부정렬은 대용량의 데이터를 정렬하는 알고리즘으로, 메모리보다 큰 데이터셋을 정렬할 때 사용된다.

외부정렬은 기본적으로:

정렬할 파일을 메모리에 적재가능한 크기의 run들로 분할한다.

각 run에 대해 내부 정렬 후 다른 파일에 저장한다.

파일에 저장된 run들을 병합하여 다시 파일에 저장한다.

병합된 run의 수가 1이 될 때까지 병합을 반복한다.

 

병합 방법에 따라 sort/merge 알고리즘은 다음과 같이 분류할 수 있다.

• Binary Sort/Merge
• Balanced Binary Sort/Merge
• Balanced K-way Sort/Merge
• Polyphase Sort/Merge

---

Binary Sort/Merge

Sorting phase - 초기 run들을 정렬한 후, 2개의 외부 파일에 저장

Merging phase - 각 파일에서 run을 하나 씩 선택하여, 세번째 파일에 병합하여 저장한다.

결과 파일을 다시 2개의 파일로 분배한 후 병합을 진행한다.

 

전체 병합 단계의 수 = log2(R)

Balanced Binary Sort/Merge

Binary Sort/Merge에서, 

출력 파일 수를 2개로 늘려, 각 병합마다 두개의  파일에 번갈아가며 출력한다.

그럼, 결과 파일을 다시 2개의 파일로 분배하는 과정을 생략할 수 있다.

 

Balanced k-way Sort/Merge

Balanced Binary Sort/Merge에서 출력파일 개수를 k개로 늘려 사용함.

 

run의 크기가 3이라면 메모리가 3밖에 수용하지 못하므로 출력파일은 3개밖에 만들 수 없음.

 

전체 병합 단계의 수 = logk(R)

 

k개의 run에서 가장 작은 key값을 갖는 run을 검색할 때

linear search시 k-1번이지만,

selection tree 사용시 log2(k)번만에 가능하다.

Polyphase Sort/Merge

 

 

---

2PMM(2 phase multiway merge/sort)

phase 1- 정렬단계

메모리 크기만큼 레코드를 저장

내부 정렬 알고리즘을 이용하여 정렬

정렬된 레코드들을 run에 기록

모든 레코드들이 run에 저장될 때까지 반복

 

phase 2- 병합단계

각 run에서 한 블록씩 판독하여 메모리에 저장

가장 작은 키 값을 갖는 레코드를 판단하여 출력 블록에 저장

출력 블록이 가득차면 디스크에 기록

입력 블록에 레코드가 존재하지 않을 경우, 해당 run에서 다음 블록을 판독하여 메모리에 저장

 

메모리 크기가 M, 하나의 블록 크기가 B일 때

2PMM 정렬이 가능한 최대 파일 크기는

M*((M/B)-1) 이다.

 

---

성능개선 방법들

 

각 run의 병합 순서에 따라 실행속도 차이가 발생한다. 허프만 트리를 이용..

각 run을 memory크기 이상으로 만들면 run의 개수가 적어지고 병합단계를 줄일 수 있다.