데이터을 디스크에 저장하는 경우, 몇 가지 고려 사항이 있을 수 있다. 예를 들어, 데이터을 압축해서 인코딩된 상태로 저장한다면, 크기를 줄일 수 있고, 결과적으로 디스크 공간 사용과 접근 시간(Access Time)에 있어서 유리하다. 여기서 접근 시간이란, 메모리에서 보조 기억 장치(Secondary Storage)에 저장하거나, 보조 기억 장치에서 메모리로 읽어들이는데 걸리는 시간을 의미하는 것이다. 또, 이렇게 압축된 데이터는 줄어든 크기 때문에 전송 시간에서도 이득을 볼 수 있다. 데이터를 인코딩하거나 디코딩하는 것은 메모리에서 일어나는 일이며, 파일 처리에서는 메모리에서 일어나는 일은 중요 관심사가 아니다. 중요한 것은 물리적인 디스크 액세스이며, 실질적으로 이것이 가장 비싼 작업이기 때문이다. 데이터 압축에 있어서, 다음과 같은 방법을 생각해 볼 수 있다.
먼저, 해당 데이터를 다른 표기법을 사용하여 표시하는 방법이 있다. 예를 들어, 어떤 문자열 데이터를 더 작은 크기의 정수형 인덱스와 매핑 할 수 있다면, 문자열 데이터를 그대로 저장하는 것보다 정수형 인덱스를 저장하는 것이 훨씬 유리하다.
데이터가 만약 동일한 데이터가 연속적으로 저장되는 형태라면, 연속되는 횟수와 해당 데이터를 한번만 저장하는 것도 좋은 방법이 될 수 있다. 예를 들어, 래스터 비트맵 이미지의 경우, 이 방법을 사용하면 데이터 크기를 크게 줄일 수 있다.
또, 문자의 출현 빈도가 크게 차이가 난다면, ASCII 코드와 같은 고정폭 크기 코드 대신, 허프만 코딩(Huffman Coding)을 사용한 가변폭 크기 코드를 사용하는 방법도 있다. 허프만 코딩은 문자의 출현 빈도를 조사하여, 가장 적은 출현 빈도를 보이는 문자를 선택하여 트리로 계속 병합하는 과정을 거친다. 그리고 루트에서부터 비트를 할당하는데, 결과적으로 가장 많은 출현 빈도를 보이는 문자는 크기에 있어서 가장 적은 비트를 할당받으며, 출현 빈도가 낮은 문자일수록 많은 비트를 가지게 된다. 즉, 고정폭 크기 코드에 비하면 디스크 공간을 절약할 수 있다. 허프만 코딩의 알고리즘은 다음과 같다.
먼저, 대상이 되는 데이터에서 각 문자의 출현 빈도를 조사한다. 그리고, 가장 출현 빈도가 낮은 문자 2개씩 트리로 묶는데, 출현 빈도가 낮은 쪽은 오른쪽 자식으로 합쳐진다. 서브 트리(subtree)의 출현 빈도는 서브트리가 포함하고 있는 모든 문자들의 출현 빈도를 합한 값이다. 그리고, 하나의 단일한 트리가 될 때까지 이 과정을 반복한다. 하나의 트리가 되었다면, 왼쪽 간선에 대해서는 0, 오른쪽 간선에 대해서는 1의 값을 할당한다. 따라서, 각 문자의 허프만 코드 값은 그 리프(leaf)에 도달하기까지의 간선 값이다.
예를 들어보자. 알파벳 5개의 문자로 구성된 어떤 집합에서, 각 문자들은, a = 0.4, b = 0.1, c = 0.2, d = 0.3, e = 0.6의 출현 빈도를 가진다. 이것을 어떻게 허프만 코드로 표현해야 하는가?
먼저, 가장 낮은 출현 빈도를 보이는 문자는 b와 c이므로, c b의 묶음이 생기고, 이것의 총 출현 빈도는 0.3이 된다. 이제 이것과 다른 문자들의 출현 빈도를 비교해보면 d가 같은 값을 가지므로 병합한다. 어느 쪽이 오른쪽에 오더라도 상관없다. 이 서브 트리의 출현 빈도는 0.6이 된다.
이제, a = 0.4, 서브트리 = 0.6, e = 0.6이다. a와 e를 묶어서 서브 트리를 형성하고, 이 서브 트리의 출현 빈도는 1이므로, 아까 만든 서브 트리를 오른쪽에 붙여서 허프만 트리를 완성한다. 그리고 간선의 오른쪽에는 1, 왼쪽에는 0을 할당한다. 다음과 같은 결과를 얻을 수 있을 것이다.
e = 00
a = 01
d = 10
c = 110
b = 111
이러한 데이터 압축 방법은 손실 압축과 무손실 압축으로 나눌 수 있는데, 예를 들어 손실 압축의 경우, 데이터를 인코딩할 때 원래의 데이터에서 원하는 데이터를 샘플링해야 하는데, 여기서 필연적으로 데이터의 손실이 발생한다. 즉, 손실 압축 기법으로 인코딩된 데이터는 다시 원본 데이터와 완전히 동일한 형태로 다시 디코딩할 수 없다. JPEG 이미지 인코딩이나 MP3 오디오 인코딩 기법은 대표적인 손실 압축 기법이다.
이 외에도, 데이터를 데이터 그 자체가 아닌, 데이터를 서술하는 메타 데이터의 형태로도 저장할 수 있는데, XML은 대표적인 메타 데이터 포맷이라고 할 수 있다. 메타 데이터 형식으로 저장된 데이터는 데이터에 접근하기 위해 다양한 부가 정보를 가질 수 있다.
마지막으로, 데이터가 디스크에서 삭제되는 경우, 고정폭 크기의 레코드인지, 가변폭 크기의 레코드인지에 따라 Space Reclaiming 전략이 달라지게 된다. 고정폭 크기의 레코드가 삭제되었고, 디스크에 고정폭 크기의 레코드가 계속해서 저장되는 경우라면, 새로운 빈 공간을 할당하는데 큰 문제는 없다. 다만, 이 경우 고정폭 크기 레코드라고 하더라도 내부에서는 가변폭 필드를 가지는 경우가 있고, 빈 필드의 레코드가 저장되는 경우도 있는데, 이것을 Internal Fragmentation이라고 한다.
가변폭 크기 레코드는 조금 더 복잡하다. 할당을 요청하는 디스크 공간과, 현재 남아있는 각각의 디스크 공간 크기가 일치하지 않을 수도 있기 때문이다. 따라서 여러가지 할당 전략이 있을 수 있는데, 대표적으로 요청을 만족하는 비어있는 단편 공간을 찾은 경우, 즉시 이 공간을 할당하는 First Fit 전략이나, 요청된 할당 크기와 할당이 가능한 공간의 크기가 가장 비슷한 경우 할당하는 Best Fit 전략, 마지막으로 두 크기가 큰 차이가 나는 Worst Fit 전략 따위를 생각할 수 있다. 비어 있는 각각의 디스크 공간과 요청된 할당 크기가 완전하게 같지 않다면 필연적으로 다시 단편화가 발생하는데, 이렇게 발생하는 단편화를 External Fragmentation이라고 한다.
Library/File Structure