<Algorithm> External Sort ② 2PMM and Run-Generation

HONG CHANGSUB -

본 게시물은 영남대학교 조행래 교수님의 강의를 기반으로 제작되었습니다.

  1. 2 Phase Multiway Merge/Sort
    • 2 Phase : Sorting Phase + 1번의 Mergint Phase
    • run의 최대크기, 즉 메모리에 최대로 데이터를 담아 정렬하겠다란 뜻!
    • Multiway : 사용 할 수 있는 파일의 수는 무제한
    • 2PMM으로 sorting 할 수 있는 파일의 크기는 메모리의 크기에 의해 결정됨
    • Phase 1 - 정렬 단계
      • 메모리 크기만틈 레코드를 저장
      • 내부 정렬 알고리즘을 이용하여 정렬
      • 정렬된 레코들을 run에 기록
      • 모든 레코드들이 run에 저장될때까지 반복
    • Phase 2 - 병합 단계
      • 각 run에서 한 블록씩 판독하여 메모리에 저장
      • 가장 작은 키 값을 갖는 레코드를 판단해서, 출력 블록에 저장
      • 출력 블록이 가득 차면, 디스크에 기록
      • 입력 블록에 레코드가 없으면, 해당 run에서 다음 블록을 메모리로 들고옴
  1. Run-Generation
    • memory 크기 이상으로 초기 run의 크기를 설정
    • merge-pass의 수 감소
    • memory 크기 = 3
    • input file = (8 6 1 3 2 7 5 4 9)
      • 1st run = (1 3 6 7 8)
      • 2nd run = (2 4 5 9)
run-generation 풀이
  1. Optimal Mergint of Runs
    • run-generation을 하면 다양한 크기의 run들이 생성되는데 이를 가장 효율적으로 실행시키는 알고리즘 --> Huffman Tree사용
    • 비용이 많이 드는 노드를 가장 마지막에 계산하는 원리
      ex) run : 2,3,5,7,9,13