정렬

# 정렬
- cpu가 함
- 데이터베이스에서 정렬을 하는 목적 :
  SQL 질의 결과를 정렬된 형태로 얻음(order by)
  동등 비교 연산은 중요한 연산
  - 조인은 대부분 동등 비교 연산
  - 정렬을 통하여 동등비교 연산을 효과적으로 구현 가능

- 정렬키에 대하여 인덱스를 구성하는 경우 :
  논리적 정렬 형태임(물리적 정렬 형태가 아님)
  정렬된 형태로 읽을 경우 레코드 하나 당 디스크 접근 한 번씩이 발생할 수도 있음
  레코드에 대한 물리적 정렬이 필요함

- 주기억장치 공간 한계 문제
  내부정렬: 퀵정렬 선택 (버퍼에 읽어 들일 수 있는 경우)
  외부정렬: 합병정렬 선택 (버퍼에 읽어 들일 수 없는 경우)
- O(N^2)일반 vs O(Nlog2(N))퀵,합병
- m-way merge 합병

 

# 외부 정렬 – 합병 (읽기, 정렬, 쓰기)
- 초기 런의 개수 : ⌜br/M⌝ = N  (N=4, M=3, br=12)
- 합병 패스(merge pass) : ⌜logM-1(br/M)⌝ - 단계 수
- 각 합병 패스마다 M-1 비율로 런의 개수가 줄어듦
- 총 블록 전송 횟수 : br (2⌜logM-1(br/M)⌝ + 1) 
- 마지막은 정렬결과를 프로세스에 줌(디스크에 write 안 함)
- 총 탐색 횟수 : 2⌜br/M⌝(초기 런) + ⌜br/bb⌝ (2⌜logM-1(br/M)⌝ - 1)
- M>N 인 경우 N+1개를 합병에 사용(n 개는 input, 1개는 output용) - 한 번에 정렬
- M<=N 인 경우 M-1개를 가져와서 1개는 output용
- Run 크기 : 앞 Run * (M-1)
- Run 개수 : ⌜N/(M-1)^단계⌝ 
- 헤드 : 섹터, 디스크 : 블록, 본체 : 여러 블록 가져옴