파일구조 요약 (5~6장)

2017/10/30 - 파일구조 요약 (1~2장)
2017/10/30 - 파일구조 요약 (3~4장)
2017/10/30 - 파일구조 요약 (5~6장) (이 글)

5장. 레코드 관리

Record length

레코드의 길이는 field의 크기와 상관있다. 따라서 Access, fragmentation, 구현의 정도를 보고 적절한 구조를 선택한다.

header (meta-data)

파일에 관한 전반적인 정보(수정 시간, 레코드의 수 등)를 기술한다. 보통 파일의 앞쪽에 적는다.

IO Buffer Class Methods

• Write: 파일에 record를 적는다.
• Read: 파일로부터 record를 읽는다.
• WriteHeader: 파일의 앞에 “IOBuffer”라고 적지만, 어떤 버퍼로 풀어야하는가를 의미한다.
• ReadHeader: 헤더의 정보를 읽고 Buffer Object과 값이 같은 지 확인한다.
• DWrite/DRead: record의 byte 주소로 직접 연산한다.

RecordFile Class (BufferFile을 상속받음)

C++ template 기능을 사용하여 어떤 record type을 Buffer를 거쳐 File에 쓰고 읽을 수 있도록 한다.

Abstract Data Model

특정한 도구로만 볼 수 있는 데이터가 아니다.

They does not view data as it appears on a particular medium.

Portability (이식성)

서로 다른 컴퓨터 또는 프로그램에서 파일을 접근할 수 있도록 한다. 

표준이 되는 물리적인 레코드 형식에 동의하고 그것을 따르는 등으로 달성한다. (XDR)

6장. Organizing FIles for Performance

• Data compression 방법을 살펴본다.
• 저장 공간을 재활용하여 Storage compaction하는 간단한 방법을 살펴본다.
• Avail List
• Internal fragmentation과 External fragmentation
• Key sort

Data compression

데이터 압축을 하는 이유는 1. 저장공간을 줄이고, 2. 빠른 전송과 빠른 접근 시간과, 3. 빠른 순차 처리를 위해서이다. 표현 방법은 여러 가지가 있는 데,

1. 몇 개의 비트가 압축된 정보를 나타낸다. (비트마스크를 생각하면 된다)
   - 단점) 사람이 읽을 수 없고, 인코딩 시간이 발생한다.
2. 반복되는 구간을 압축하여 나타낸다. aa bx …(6번)... bx cc 를 aa ## bx 08 c 라던지.
   - 단점) 메타데이터때문에 압축 후의 크기가 더 커질수도 있다.
3. 허프만 트리
   - 확률적으로 빈도수가 높은 문자열을 짧게 표현하여 트리로 나타낸다.

Avail List

파일에서 한 레코드를 삭제할 때, 실제로 값을 모두 지우고 뒤의 모든 레코드의 주소를 재배치하는 것은 비효율적이다. 레코드에 삭제되었음을 표시만 하고, 다시 사용이 가능함(available)을 알 수 있도록 List로 관리한 것이다.

Storage Fragmentation

- Internal fragmentation
Fixed-length Records 에서 나타난다. 레코드 내부에서 생기는 빈 공간을 의미한다.

- External fragmentation
Variable-length Records 에서 나타난다. 레코드와 레코드 사이에 낭비되는 공간을 말한다.

Placement Strategies

- First-fit
들어갈 수 있는 가장 가까운 위치를 선택한다.

- Best-fit
Avail List에서 현재 저장하려는 레코드와 가장 비슷한 크기를 가진 공간을 선택한다.
크기별로 정렬할 수 있다면, 정렬 후 first-fit을 하는 방식과 같다.

- Worst-fit
가장 큰 공간을 선택하여 그 곳에 저장한다. External fragmentation이 발생하기 쉽다.

Key sorting & Its Limitations

Tag sort라고도 부른다. Key만을 가지고 레코드를 정렬한다. Key와 레코드를 연결하는 KeyNode Table이 있다. 파일 자체를 정렬할 수 있지만 I/O의 오버헤드가 크다.

Problem) key sort의 단점과 이유, 그리고 그 보완법을 서술하시오.

Solve)

단점
I/O는 한 블럭 단위로 일어난다. 레코드를 읽는 과정에서 최대 레코드 개수만큼 I/O가 일어날 수 있으므로 그 오버헤드가 너무 크다.

보완법
파일의 내용을 정렬하는 것이 아닌, 메모리 상에서 <key, RRN(레코드의 위치)>로 저장된다면 레코드가 가리키는 위치만 변경하면 마치 정렬된 것처럼 사용할 수 있다.