ch6-2) Organizing Files for Performance

Binary Search and Internal Sorting

1. Sequential search

  - At most n comparisons -> O(n)

  - Too expensive -> keyed access를 다루기 위해 더 나은 방법을 찾아야함

 

2. Binary search

  - At most [log2 n] + 1 comparisons -> O(log n)

  - 단, 파일이 키 기준으로 정렬되어 있어야 함

 

3. Internal sort

  - RAM 안에 있는 디스크 파일을 읽어 정렬 (Disk 에서 RAM으로 데이터를 올린 후에 sort)

    ( 통째로 올려서 sort하는 방식)

  - 얼마나 적게 읽고 사용했는가? 

  - 데이터가 많은 경우에는 유용하지 못하다

 

4. external sort

  - 통째로 올릴수는 없으니까 부분적으로 올려서 sort

 

Limitations of Internal Sorting and Binary Search

1. Binary searching은 많은 양의 disk access cost가 발생함 

 

2. file sorted를 유지하는데 비용이 많이 듦

 

3. internal sort는 단지 작은 파일에서만 작동

 

External sort

1. Hard disk 에서 하나씩 읽어옴

2. 읽어온 데이터에서 (key, address)만 뽑아서 저장 후 순서에 맞게 저장

 

한계 :

 1. 같은 레코드를 2번 읽어버림

 

 

 

 

 

하나의 record 파일에 대해 여러개의 Index file을 만들 수 있음