[파일처리] 파일처리 개요

파일이란 secondary memory(HDD, SSD 등)에 저장된 같은 형식을 가진 record들의 집합이다.

파일의 종류

• Physical Files
  - 물리적 파일로 실제 디스크에 저장되며 OS가 관리하는 물리적인 파일
• Logical Files
  - 논리적 파일로 프로그램 상에서 접근하는 파일
  - file open 시 OS가 Physical file과 맵핑된 Logical file을 넘겨주어, 이 파일을 읽거나 쓰게 된다.

 

파일 구조(File Structure)

파일 구조란 데이터를 표현하는 representation과 그 데이터를 접근하는 operation의 조합이다. representation의 예시로는 C언어의 구조체 등이 있고 operation은 삽입, 삭제, 검색 등이 있다. 좋은 파일 구조를 만들기 위해서는 데이터로부터 정보를 얻어 올 때 적은 비용이 들어야 한다. 파일 처리에서 가장 성능과 비용에 큰 영향을 미치는 부분은 디스크 접근이다. 따라서 파일 구조 설계의 목표는 disk I/O 즉, 파일 접근 횟수를 줄이는 것이다.

 

※ 디스크(Disk)와 램(RAM) 비교

디스크는 램에 비해 굉장히 느리다. 식으로 나타내면 다음과 같다.

 

RAM : Disk = 120 nanosec : 30 milisec

                      = 1 sec : (25 * 10^4) sec

                      = 1sec : 2일 22시간

 

하지만 램에 비해 디스크의 용량이 훨씬 크고 훨씬 싸다.

 

다양한 파일 처리 기법

1. Sequential access

- 테이프와 같이 파일의 맨 처음부터 순차적으로 읽는 방법

- 찾고자 하는 파일이 파일의 끝 부분에 위치한다면 많은 시간이 소요된다.

 

2. Simple index

- index file을 따로 만들어 key와 주소(인덱스)만을 저장하여 RAM에서 관리

- RAM에서 이진 탐색과 같은 방식으로 인덱스를 찾아 HDD의 특정 인덱스를 바로 접근할 수 있게 한다. (Random access)

 

 

3. Binary search tree

- 데이터를 이진 탐색 트리로 관리(한 노드 기준으로 왼쪽에는 작은 값, 오른쪽에는 큰 값)

- 평균적으로 O(logN)의 빠른 시간 복잡도를 가지며 삽입, 삭제 등이 쉽다는 장점이 있다.

- 하지만 최악의 경우 한쪽 방향으로 치우치며 트리가 형성되는 skew 현상이 발생하여 순차처리와 같은 성능을 보일 수 있다.

 

4. AVL tree

- BST의 단점을 보완한 트리

- 임의의 한 노드 기준으로 왼쪽 subtree와 오른쪽 subtree의 depth 차이에 제한을 두어 skew 현상을 방지한다.

 

5. Balanced binary tree

- 항상 이진트리가 밸런스를 유지하도록 관리하는 방식

- 밸런스를 유지하기 위한 비용이 듦 

- ex) B-tree, B+ tree

 

6. Hashing

- key값을 통해 항목이 들어있는 배열의 인덱스를 결정하는 방식

---