09. Simple Algorithm

 

9. 1. Algorithm

 

- 디스크 안에 있는 파일들을 정렬하기 위해서 여러 알고리즘을 사용할 수 있습니다.

 

  파일을 정렬하기 위해서 디스크 안에 있는 파일을 메모리 안으로 읽어와 판독을 진행하고,

 

  정렬한 뒤, 정렬한 파일들을 디스크에 기록합니다.

 

 

1) Key를 정렬하기 위해서 Heap Sort를 사용합니다.

 

    Key들이 메모리 안에 로드되는 동시에 정렬을 수행할 수 있습니다.

 

 

2) 용량이 큰 파일들을 정렬하기 위해서 External Sort를 사용합니다.

 

  a) Secondary Storage에 있는 정렬하고자 하는 파일들을 여러 개의 Block으로 나눕니다.

 

  b) 각각의 Block들을 Main Memory로 읽어와서 Block단위로 Sorting을 진행하고,

 

      다시 Secondary Storage에 기록합니다.

 

  c) Sorting한 각 Block의 가장 앞 부분부터 일정하게 조금씩 Main Memory로 읽어와서 Sorting한 뒤,

 

      합병하여 기록합니다.

 

  d) Block의 모든 데이터에 대하여 앞에서부터 c)를 반복.

 

- 더 빠른 동작을 위해 합병을 여러 번 수행할 수 도 있습니다. (Multiple-Step Merges)

 

 

3) B-Tree: DB와 File System에서 빠른 데이터 저장과 검색을 위해서 사용하는 Tree Structure.

 

    Index를 저장하고 검색할 때 사용합니다.

 

 

4) Virtual B-Tree: B-Tree로 Data를 읽기 위해서는 Root Node가 저장된 Page를 Secondary Storage에서 읽어야하므로, 속도저하가 발생하게 됩니다.

    이러한 문제를 해결하기 위해서 Root Node Page뿐만 아니라, 다수의 B-Tree Page를 Memory상의 Buffer에 저장하여, Secondary Storage의 접근을 최소화하는 B-Tree의 개선형입니다.

 

 

5) B-Tree외에 B+-Tree를 사용하기도 하며, 빠른 검색을 위해 Hashing을 사용하기도 합니다.

 

(Heap Sort, B-Tree, B+-Tree, Hashing은 자료구조, 알고리즘에서 정리)

 

---