Pass 1, 2
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2F9587d5ec-6776-4b94-8229-29433d3f1692%2Fimage.png)
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2Fdf0a1161-2849-4d96-8472-89182dfac81d%2Fimage.png)
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2Fae9df00e-287c-4392-944d-aecdf7022cfc%2Fimage.png)
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2F843e28de-6b37-4e88-b7be-a01dbc9beec2%2Fimage.png)
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2Fd3fd3e28-8463-4681-834c-7218236a4d53%2Fimage.png)
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2F4c1ece3e-c1e2-4979-bb16-6bf277c784b4%2Fimage.png)
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2F4432cc0a-84b8-4369-a7d4-d2bdc6d96939%2Fimage.png)
2-Way External Merge Sort
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2F211776c5-2372-4ac0-8028-c7d6b001ebca%2Fimage.png)
General External Merge Sort
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2Ff9fa5d2e-6115-4376-bb50-352ddfa2551a%2Fimage.png)
Pass 0
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2Fb033755a-d61f-4c37-9699-877442f5852c%2Fimage.png)
Pass 1, 2, ....
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2Fa9ab2dee-6ce4-40fa-a820-4023d4373b76%2Fimage.png)
General External Merge Sort
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2Fbb60af11-b635-4843-8ae8-177ce8a03914%2Fimage.png)
I/O Pages of External Merge Sort
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2F7d975055-b666-466e-9a82-7586a0b3f8ff%2Fimage.png)
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2F2d370f81-2dbf-488d-91f4-9768459f78f7%2Fimage.png)
Number of Passes of External Sort
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2F6a9039e6-04ed-4cbf-a5b5-708b1f4e4370%2Fimage.png)
Blocked buffer: I/O pages vs I/O time
- If pages are sequentially stored on disk, I/O time per page can be reduced by having larger (b>1) input buffer.
- read b pages with 1 seek time and 1 rotational delay.
- (B-1)/b runs will be merged at a time, thus, more passes and more I/O pages.
2 Choices for 5-page Buffer (B=5)
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2Ff5f1652d-bd59-4ba5-931e-8f0052c35ba5%2Fimage.png)
I/O cost in terms of number of page 는 오른쪽이 더 크다. more pass to merge because because each time can merge two. 하지만 오른쪽은 smaller I/O time per page이다. disk에 sequentially하게 저장되어있으면 1 seek time만 필요하기 때문이다.
Sorting cost for blocked buffers
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2F924c7136-1d82-46cf-ad0b-662177ed5495%2Fimage.png)
Using B+ Trees for Sorting
- If the file to be sorted has B+ tree index on the sorting column(s), can retrieve records in order by traversing leaf pages.
- Is this a good idea?
- If B+ tree is clustered, very good idea!
- If B+ tree is not clustered, could be a very bad idea
B+ tree with searh key <A,B,C>. Can it be used to sort on A, on (A,B), on B, on (A,C)?
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2F5a7a740a-34b0-4cd2-a65e-f552f8ea59db%2Fimage.png)
처음 두 개의 경우에는 B+트리 사용하기 좋고, 나머지는 좋은 경우가 아니다.
Clustered B+ Tree Used for Sorting
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2F4089bf8b-3212-4f0a-9fd0-29d613ce1a9b%2Fimage.png)
Unclustered B+ Tree Used for Sorting
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2F67055596-ed63-4e67-96c3-d38a9f64c25a%2Fimage.png)
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2F3367a166-87bb-4565-8612-cf705322e279%2Fimage.png)
1*
에서 p1 읽고, 2*
에서 p2 읽고 3*
에서 p3 읽고 4*
에서 p4 읽고 5*
에서 다시 p1 읽고 ...
-> 총 8 page를 읽는다.
External Sorting vs. Unclustered Index
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2F5084681b-9f94-41cb-a47c-f5952dd23cb8%2Fimage.png)
Summary
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2F520807ab-af49-4989-aa52-0b7b4ab97b09%2Fimage.png)
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2Fa6b83c8d-3074-4b4f-b0bb-81a0227760b5%2Fimage.png)
Replacement Sort (pp429)
![](https://velog.velcdn.com/images%2Finjoon2019%2Fpost%2F00d8ca4f-ca78-405d-adcf-708083c0ff7d%2Fimage.png)