파일에서의 레코드 삭제 방법과 관리(File Processing)

    이전 글에서 파일에서 레코드 저장하는 고정길이와 가변길이 방식을 설명하였다. 이번 글에서는 저장된 레코드를 삭제했을 때의 관리 방법에 대해 알아보겠다.

    레코드를 삭제한 경우 가장 단순한 방법은 삭제된 레코드가 차지한 공간을 없애는 방법이다. 즉 삭제된 레코드 오른쪽에 있는 모든 데이터들을 이동(shift)시키는 방법이다. 이 방식을 Storage Compaction이라고 한다. 레코드가 삭제되었을 때 표시를 해놓고 그 레코드를 제외하고 다른 파일에 그대로 옮겨서 저장하는 방식이다. 이 방법은 파일 크기를 줄이는 장점이 있지만 파일의 크기가 클 경우 굉장히 많은 비용이 들기 때문에 삭제가 될 때마다 할 수 없다. 그렇기 때문에 얼마나 자주 compaction을 할지는 삭제 레코드의 수나 시간 등을 정해놓고 수행하는 것이 좋다. 다른 파일에 쓰는 경우 out-of-place 방식이지만 시간이 더 걸리고 복잡한 방식으로 in-place 방식으로 같은 파일에 쓸 수 있는 방법도 있다.

    Storage Compaction방식은 현실적으로 어려우니 삭제된 공간을 재사용하는 방법이 이상적이다. 이 경우 고정길이 방식과 가변길이 방식에 큰 차이점이 있다.

    먼저 고정길이 레코드 방식의 경우 레코드가 삭제되었다고 생각해보자. 이 경우 삭제된 레코드에 특수문자인 delete mark를 맨 앞에 써놓아 이 레코드는 삭제되었다는 것을 표시한다. 고정길이 레코드는 모든 레코드의 길이가 동일하기 때문에 어떤 레코드든 삭제된 레코드에 쓸 수 있다. 이때 레코드를 새로 추가할 때 삭제된 레코드의 위치를 빠르게 찾는 것이 중요하다. 가장 좋은 방법으로 링크드리스트 방법이 있다. 삭제된 레코드의 위치를 링크드리스트 방법으로 관리하는 방법이다. 아래의 그림과 같이 표현할 수 있다. 

헤더영역에 삭제된 레코드의 첫번째 주소(RRN : Relative Record Number)를 쓴다. 그 다음 4번레코드에는 2가 있고 2번에는 5번, 5번에는 -1이 들어있다. 링크드리스트의 마지막에는 -1을 넣어 끝임을 알린다. 이렇게 삭제된 레코드의 번호를 링크드리스트 방식으로 다룰 수 있다. 만약 새로 레코드를 추가할 겨우 4번 레코드에 쓰게 되며 헤더의 레코드번호는 그 다음 주소인 2번이 존재하게 된다. 이때 추가로 삭제되는 레코드를 가장 연결리스트의 첫번째 노드에 오게 할 지 맨 마지막에 오게 할 지는 스스로 결졍하면 된다. 이 글에서는 가장 최근에 삭제된 레코드를 헤더에 쓰겠다. 이렇게 고정길이 방식에서의 삭제 레코드 관리를 알아보았다. 그 다음 가변길이 레코드 방식에서의 삭제 레코드 관리방법에 대해 알아보겠다.

    가변길이 레코드 방식은 고정길이보다 더 복잡하다. 고정길이 방식은 레코드의 길이가 고정되어있으므로 어떤 삭제레코드든 삽입할 수 있었다. 하지만 가변길이는 모든 레코드의 길이가 다르므로 레코드의 길이를 판별하는 과정이 추가된다. 또한 레코드의 길이가 다르기 때문에 RRN이 아닌 레코드의 주소인 offset을 사용한다. 따라서 delete mark를 쓰고 레코드의 RRN이 아닌 레코드의 길이와 다음 연결리스트 노드의 주소를 쓴다. 따라서 레코드를 삽입하고자 할 때 처음 연결리스트의 노드부터 길이를 비교하여 추가하는 레코드의 길이가 삭제된 레코드의 길이보다 작거나 같은지 확인하고 맞지 않을 경우 다음 노드의 offset으로 이동하여 비교하는 과정을 거친다. 모든 연결리스트의 레코드 길이가 맞지 않은 경우 맨 마지막에 추가해야한다.

    만약 추가하려는 레코드의 길이가 60이고 삭제된 레코드의 길이가 100이라고 가정하자. 추가 레코드의 길이가 더 작으므로 삭제 레코드에 쓸 수 있다. 쓴 경우 40의 길이가 남게 된다. 이렇게 낭비되는 공간을 internal fragmentation이라고 한다. 이 공간은 다시 재사용할 수 있게된다. 그 이후 길이 35의 레코드를 추가한다고해보자 이 경우 40의 공간을 또 재사용하여 35길이의 레코드를 추가했다. 남은 공간은 5가 된다. 크기가 5인 공간은 또 다른 레코드를 할당하기에 너무 작아 재사용되지 못하고 낭비하게 된다. 이 공간을 external fragmentation이라고 한다. 그렇다면 internal fragmentation과 external fragmentation을 관리하려면 어떻게 해야할까? 삭제레코드를 관리하는 연결리스트에서 레코드를 추가할 때의 순서에 영향을 받는다. 이 방법에 세 가지가 존재한다.

    첫 번째로 first-fit이다. 말 그대로 첫 번째로 발견하는 삭제 레코드를 할당하겠다는 말이다. 만약 40 -> 72 -> 68 -> 57 크기의 연결리스트로 연결된 삭제 레코드가 있다고 하자 이때 추가하고자 하는 레코드의 길이가 55라면 55보다 크거나 같은 가장 첫 번째인 72에 할당한다는 말이다.

    두 번째로 best-fit이 있다. 이 방식은 크기가 가장 가까운 공간에 할당하는 방법이다. 위의 예시에서 55의 길이와 가장 가까운 57에 할당하게 된다. 이 방법은 external fragmentation이 발생할 확률이 늘어나게 된다.

    마지막으로 worst-fit이 있다. 이 방식은 크기의 차이가 가장 많이나는 공간에 할당하는 방법이다. 위의 예시에서 55와 가장 차이가 많이나는 72에 할당한다. 이 방식은 internal fragmentation을 발생시켜 재사용할 수 있는 가능성을 높이는 방법이다.

    지금까지 파일에서 레코드를 삭제할 경우 삭제된 레코드를 관리하는 방법에 대해 알아보았다. 실제에서 적용할 경우 레코드의 특징과 길이, 파일의 크기 등을 고려하여 가장 적절한 방법을 찾아 적용해야할 것이다.