[파일구조] - 레코드 관리

1. 레코드 삭제

파일을 이용하다보면 특정 레코드를 삭제하는 경우가 발생한다. 만약 삭제된 레코드가 파일의 가장 끝에 있는 레코드가 아니라면, 삭제된 레코드가 있었던 공간을 재사용하기 위한 방법이 필요하다. 레코드가 있었던 공간을 재사용하기 위해서는 가장 먼저 삭제된 레코드가 어디에 있었는지를 알고 있어야 한다.

2. Available List

Available list는 파일에서 사용 가능한 공간을 저장하고 있는 데이터 집합이다. Available list는 스택(stack), 연결 리스트(linked list) 등의 자료구조를 이용하여 구현할 수 있다. 파일구조에서 available list의 구현에 대한 고려사항은 available list의 저장 위치이다. Available list를 저장할 수 있는 위치는 크게 두 가지가 있다.

• 데이터 파일과 개별적으로 저장: 별도의 저장 공간을 할당하여 available list를 데이터 파일과는 개별적으로 저장하는 방법으로써, 이 경우에는 별도의 저장 공간이 필요하기 때문에 효율적인 방법이 아니다.
• 데이터 파일 내부에 저장: available list를 데이터 파일 내부에 저장하는 방법이로써, available list의 첫번째 요소는 헤더 레코드에 저장하고 레코드가 삭제되어 비어있는 저장 공간에 available list의 요소를 저장하는 방식이다. 별도의 저장 공간이 필요없기 때문에 개별적으로 available list를 저장하는 방식보다 효율적이다.

3. 레코드 저장 방식과 Available List

고정 길이 레코드를 이용하는 파일의 경우에는 스택(stack)을 유지하여 삭제된 레코드를 기록할 수 있다. 예를 들어, 3번, 5번, 1번 레코드가 이 순서대로 삭제되었다면 스택에는 1번 레코드의 주소, 5번 레코드의 주소, 3번 레코드의 주소가 저장되어 있다. 파일 시스템은 새로운 레코드를 저장해야 할 때 스택을 참조하여 레코드가 저장될 위치를 선정한다.

그러나 가변 길이 레코드를 이용하는 파일의 경우에는 사용 가능한 공간의 크기도 저장해야하며, 사용 가능한 공간의 크기에 대한 정보 또한 크기가 가변적이기 때문에 스택보다는 연결 리스트의 구조로 available list를 구현하는 것이 더 바람직하다.

4. 단편화(Fragmentation)

메모리와 마찬가지로 파일에서도 레코드 삭제와 저장 공간 재사용이 반복될수록 저장 공간 단편화(storage fragmentation)가 발생한다. 단편화에는 아래와 같이 두 가지 종류가 있다.

• 내부 단편화(internal fragmentation): 특정 크기의 레코드에 레코드의 크기보다 작은 데이터가 저장될 경우 레코드의 저장 공간이 낭비되는 현상이 발생하는데, 이를 내부 단편화라고 한다.
• 외부 단편화(external fragmentation): 저장 공간 재사용이 반복되면 크기가 큰 저장 공간을 계속 분할하여 새로운 레코드에게 할당한다. 이러한 작업이 반복되면 크기가 큰 저장 공간이 점점 작아져서 어떠한 데이터도 할당할 수 없을 정도로 크기가 작아지는 현상이 발생하는데, 이를 외부 단편화라고 한다.

단편화에 의한 성능 문제를 해결하기 위해서는 단편화 발생을 최소화하도록 저장 공간을 할당하는 정책을 이용하는 것이 최선이 방법이다. 저장 공간 할당을 위한 정책을 storage placement strategy라고 하며, first-fit, best-fit, worst-fit이 존재한다.

단편화가 발생하는 것을 방지할 수 없는 경우에는 단편화가 발생한 저장 공간을 압축함으로써 단편화를 제거할 수 있다. Windows에서 제공하는 디스크 조각 모음이라는 유틸리티 소프트웨어는 디스크에 발생한 단편화를 제거하여 컴퓨터의 성능을 향상시키는 기능을 한다.

5. Storage Placement Strategies

저장 공간에 데이터를 할당하기 위한 정책은 아래와 같이 세 가지가 존재한다.

• first-fit: available list 상에서 처음으로 나타나는 할당 가능한 저장 공간에 데이터를 할당하는 정책이다.
• best-fit: 저장하고자 하는 데이터의 크기와 사용 가능한 저장 공간의 크기 차이가 가장 적은 사용 가능한 저장 공간에 데이터를 할당하는 정책이다.
• worst-fit: available list 상에서 저장 공간의 크기가 가장 큰 공간에 데이터를 할당하는 정책이다. 일반적으로 worst-fit가 가장 좋은 성능을 보여주는 것으로 알려져있다.

가장 좋은 성능을 보여주는 worst-fit 정책은 available list가 정렬되어 있어야 한다는 단점을 갖고 있다.