Joonas' Note

Joonas' Note

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

후기/수업 요약

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

2017. 10. 30. 15:42 joonas

    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(레코드의 위치)>로 저장된다면 레코드가 가리키는 위치만 변경하면 마치 정렬된 것처럼 사용할 수 있다.


    '후기 > 수업 요약' 카테고리의 다른 글

    정보 보호 수업 요약  (0) 2020.01.06
    파일구조 요약 (3~4장)  (0) 2017.10.30
    파일구조 요약 (1~2장)  (0) 2017.10.30
    Comments