레코드의 관리

레코드들을 식별하기 위해서 레코드 필드 값에 기반한 레코드 키를 생성합니다.

키는 다음 2가지로 구분됩니다.

 

• 주 키 (Primary Key)
• 보조 키 (Secondary Key)

주 키는 응용프로그램 환경에서 주로 사용될 키이고, 보조 키는 이름대로 보조 수단의 키이며 주 키에서 가지는 필요조건 중 유일성이 중요하지 않습니다.

 

키의 필요 조건은 다음 2가지입니다.

 

• 유일성 (Uniqueness)
• 희소성 (Minimality)

유일성은 하나 이상의 필드의 조합으로 유일하게 레코드를 식별할 수 있음을 의미합니다. 희소성은 유일성을 만족시키는 최소개수의 필드 조합을 의미합니다.

 

키를 선택할 때는 다음 3가지 조건을 만족해야합니다.

 

• 유일성 (Uniqueness)
• 데이터 포함 X (Dataless)
• 지속성 (Permanence)

레코드들을 관리하기 위해서 RRN(Relative Record Number)이라고 불리는 레코드 상대 번호를 사용하기도 합니다.

 

파일 내에서 공간을 재활용 하는 방법으로는 파일들의 수정 연산들이나 레코드 삭제 및 저장공간 압축이 있습니다.

 

고정길이 레코드의 삭제는 삭제된 레코드의 삭제 표시를 사용하여 동적으로 공간 재활용이 가능합니다. 또한, 파일 내에 삭제된 레코드에 대한 즉각적인 탐색으로 빠른 재활용 방안을 찾으며, Avail List를 연결리스트의 형태로 스택으로 관리하여 파일 내에 재활용가능한 삭제된 레코드들에 대한 리스트를 사용합니다.

 

가변길이 레코드의 삭제는 다음 요구사항이 있습니다.

 

• 삭제된 레코드들을 리스트로 연결할 방법
• Avail List로 삭제된 레코드를 추가하는 알고리즘
• 빈 공간이 필요할 때 Avail List에서 삭제된 레코드를 찾아서 제거할 알고리즘

이 때, Avail List는 삭제된 레코드에 대한 연결점으로 RRN을 사용할 수 없으므로, 삭제된 레코드의 바이트주소를 사용합니다.

 

고정길이 레코드의 경우 레코드 내의 사용되지 않는 공간으로 인해 내부단편화가 발생하고, 가변길이 레코드의 경우 외부단편화가 발생합니다. 이를 해결하기 위해서는 다음 3가지 방법을 고려할 수 있습니다.

 

• 저장공간 압축 (Storage Compaction)
• Coalesing
• 배치 전략 (Placement Strategy)

Coalesing은 작인 빈공간들의 합병을 하는 방법으로, 물리적으로 연속된 두 삭제된 레코드를 하나의 더 큰 빈공간으로 합병하는 방법입니다.

 

배치 전략의 경우, 빈 공간을 선택할 때 First - Fit, Best - Fit, Worst - Fit 등의 여러 배치 전략을 사용하여 외부단편화를 방지하는 방법입니다.

 

탐색을 하는 방법에는 많은 방법이 있지만, O(log N)인 이진 탐색을 대표적으로 사용한다고 가정합니다.

하지만, 이 방법을 사용하기 위해서는 정렬을 해야하기 때문에 O(N log N)이라고 볼 수 있습니다. 즉, CPU혹은 RAM의 입장에서 레코드들이 저장된 기억장치를 정렬하기에는 너무 오랜시간이 걸립니다.

 

따라서 파일 전체가 메모리에 적재될 수 있는 경우는 메모리 내에서 정렬합니다. (Internal Sorting)

그렇지 못한 경우 외부 정렬 기법을 사용합니다. (External Sorting)