파일의 정렬합병

목차

1.1 File 정렬합병의 개요

1.2 자연 합병(natural merge)

1.3 균형 합병(balanced merge)

1.4 다단계 합병(polyphase merge)

1.5 계단식 합병(cascade merge)

1.6 유틸리티에 의한 정렬 합병

1.7 정렬 합병의 성능

본문내용

입력화일이 새로운 출력화일이 됨
. m-1개의 입력화일이 새로운 출력화일로 합병
. 2개의 입력화일을 합병하는 단계가 되면 합병의 한 주기가 종료
한주기에 각 레코드는 한번씩 처리
* Text 173p (그림7.15) 3-원 계단식합병 참조
* Text 174-175p (그림7.16) m-원 계단식합병 알고리즘 참조
1.6 유틸리티에 의한 정렬 합병
정렬합병 유틸리티(utility)
- 범용화일의 정렬합병을 지원
- 유틸리티의 기능
. 하나 또는 그 이상의 화일 정렬
. 둘 또는 그 이상의 화일 합병
. 둘 또는 그 이상의 화일 정렬과 합병
- 명세 내용
.정렬합병할 화일의 이름
. 키로 사용될 필드의 타입, 길이, 위치
. 키 필드들의 순서(주 에서 보조순으로)
. 각 필드에 적용될 배열 순서 (오름, 내림)
. 각 필드에 적용될 순서기준
. 정렬합병 결과를 수록할 출력화일의 이름
- 세부사항의 지시
. 사용자가 정의한 정렬순서 및 기준
. 내부정렬 단계에서 사용할 알고리즘(예 ; quick, heap)
. 합병단계에서 사용할 알고리즘(예 ; 균형, 다단계, 계단식합병)
. 화일 사용 전후에 필요한 동작(예 ; rewind, unload)
. 합병단계에서 입력레코드가 올바른 순서로 되어 있는가 검증
. recovery를 위해서 check point / dump 레코드를 사용하는 주기
. 예상 입력 레코드의 수
1.7 정렬 합병의 성능
성능 평가의 요소
- 정렬합병되는 레코드의 수
- 레코드의 크기
- 이용될 저장 장치의 수
- 이용가능 I/O 채널에서의 저장장치 분포
- 입력화일에서 키값의 분포

키워드

파일,   정렬합병,   다단계,   계단식,   유틸리티