Algorithm] 외부 정렬(External Sort)

 

외부정렬(External Sort)은 입력 크기가 매우 커 읽고 쓰기가 오래 걸리는 보조 기억 장치에

저장할 수밖에 없는 상태에서 수행되는 정렬이다.

통상적으로 주기억장치에서 다룰 수 있는 크기의 데이터를 다루던

기존의 정렬은 내부정렬(Internal Sort)로 분류한다.

예를 들어, 주기억 장치 용량이 1GB라면, 데이터의 크기가 극단적으로 128GB라고 하자.

이런 경우에는 주기억 장치에 데이터를 모두 올릴 수는 없는 상황이라

어떤 내부 정렬 알고리즘으로도 직접 정렬할 수는 없어 보조기억장치(HDD,SDD)를 이용해야 한다.

그렇다면 이제 입력을 분할해 주기억 장치가 수용 가능한 만큼의 데이터에 대해

내부 정렬을 수행하고 다시 이를 저장하는 방법을 반복하여,

점진적으로 크기를 늘려나가는 방식을 고려해야 한다.

내부정렬은 성능이 좋은 퀵 정렬을 사용하면 된다.

주기억장치 보조기억장치 액세스 속도가 극단적으로 차이가 나기 때문에,

최대한 보조기억장치에 접근하는 횟수를 최소화하는 것을 우선사항으로 두어야 한다.

 

주기억 장치 용량을 M, 외부정렬 알고리즘에 입력된 데이터의 크기를 N라고 했을 때알고리즘은 아래와 같다.

 

Input : input data 저장된 input HDD

Output : 정렬된 데이터가 저장된 output HDD

Input HDD에 저장된 입력을 M만큼씩 주기억 장치에서 읽어 들이고, 내부정렬을 수행한 후, 별도의 HDD에 저장한다. 다음 단계에서 Input HDD는 Output HDD로 사용되고, 별도의 HDD를 Input HDD로 사용함.

while(Input HDD에 저장된 블록 수>1)

{

    Input HDD에 저장된 블록 2개씩 선택, 각각 블록으로부터 데이터를 부분적으로 주 기억장치에 읽어 들여 합병     수행하고 그 결과를 Output HDD에 저장한다.

단, Input HDD에 저장된 블록 수가 홀수인 경우, 마지막 블록을     그대로 Output HDD에 저장.

    이 과정이 끝나면 Output, Input을 뒤집어 선택해 역할을 바꿈.

}

return Output HDD

 

성능은 미리 말했듯 Data를 얼마나 읽고 쓰는 것을 측정한다.

전체 데이터를 읽고 쓰는 것을 Pass라고 하고,

위 알고리즘에서 while문이 한 번 실행될 때마다 Pass가 1회 실행되기 때문에, 이것이 시간 복잡도가 된다.

 

Input Data Size N, Main Memory Size M일 때,

while문이 반복되는 과정에 따라서 블록의 크기가 2M, 4M, 2^kM으로 증가하며,

마지막으로 남게 되는 하나의 블록이 정렬의 결과를 가지고 있는 것이 된다.

분할, 합병, 정렬 과정을 포함하는 while문 수행 횟수가 k고, 2^kM=N이기 때문에, 2^k =N/M,

k= log_2(N/M), 시간복잡도는 결국 O(log(N/M))이다.

 

물론 이는 하나의 보조 기억 장치에서 두 개의 블록을 동시에 읽어 들이는 경우를 가정한 것이다.

동시에 읽어 들이는 것이 불가능한 경우에는,

서로 다른 보조 기억 장치에서 정보를 읽어 들여, 정렬하는 경우도 있을 수 있다.

합병하며 만드는 블록을 저장장치에 번갈아가며 저장하면 해결할 수 있다.

이러한 것을 다방향 합병 알고리즘이라고도 하는데, 여기서 자세한 것을 다루지는 않겠다.

 

외부정렬은 물품/재고 DB, 인사 DB, 전화번호 DB 등 방대한 데이터을 관리하는 것에서 사용하기에 알맞고,

일반적인 DB의 중복 데이터 제거에서도 사용되기도 한다.