파처 ch5) Managing Files of Records

Record Keys

1. Primary key

  - 키값이 존재한다면 유일한 레코드 값을 가져야 함

  - 바뀔수가 없음

 

2. Secondary key

  - 레코드 값이 유일하지 않아도 됨

  - ex) 이름, 도시 이름, 주소 등

 

3. Canonical form

  - 키의 형태를 통일된 형태로 변환을 하고나서 다룸

ex) Ames, AMES, ames -> AMES로 변환

 

Sequential Search

1. 순차 탐색 성능 평가

  (1) read() 호출 수로 성능을 측정

   - 파일에서 데이터를 읽는 read() 시스템 호출을 기준으로 성능을 평가

   

  문제점 : 이 가정은 엄밀히 말하면 정확하지 않음

     운영체제의 버퍼링(buffering) 덕분에 실제로는 성능이 더 나올 수 있음

     (하지만 다중 사용자 환경에서는 이런 단순한 가정이 타당함)

 

  탐색 시간 복잡도 O(n)

  - n개의 레코드 중 하나를 찾기 위해서는 평균적으로 n/2번의 읽기가 필요함

    -> 순차 탐색은 O(n)의 시간 복잡도를 가짐

 

2. 레코드 블로킹(Record Blocking)을 통한 성능 향상

  (1) 여러 레코드를 한꺼번에 읽어서 성능 향상

     - 여러 개의 레코드를 하나의 블록으로 묶어서 한 번에 읽음

     - RAM에 올려서 처리하면 성능이 향상

  (2) 블록 크기는 데이터보다는디스크의 물리적 특성과 관련

     - 블록의 크기는 레코드의 크기보다는 디스크 드라이브의 물리적 특성 (ex: 섹터 크기, 전송 속도 등)에 더 영향을 받음

 

3. 순차 탐색이 좋은 경우

  (1) 패턴을 검색할 때(텍스트 파일, UNIX 명령어)

      - grep, cat, wc 같은 유닉스 명령어로 ASCII 파일에서 특정 패턴을 찾는 경우

  (2) 레코드 수가 매우 적은 파일 (ex : 10개 정도의 레코드만 있는 파일)

  (3) 거의 탐색할 일이 없는 파일 (ex : 테이프 파일처럼 검색보다는 순차 처리나 백업 등에 사용되는 경우)

  (4) 특정 키 값을 가진 모든 레코드를 찾고자 할 때

      - ex) secondary key가 주어졌을 때, 그 값을 가진 모든 레코드를 찾는 경우

      - 일치하는 레코드가 많을 것으로 예상되면, 순차적으로 읽으면서 조건에 맞는 걸 수집하는 것이 효율적

 

Direct Access

1. 순차 탐색의 가장 극단적인 대안

  - 필요한 레코드가 어디에 있는지 정확히 알고 있을 때, 바로 접근하는 방식

 

2. sequential searching은 O(n)이지만 direct access는 O(1)임

 

3. Direct Access의 핵심은 레코드의 시작 위치를 아는 것

  (1) 인덱스 파일 사용 -> 키 값과 레코드 위치의 매핑 정보를 저장한 파일

  (2) RRN(Relative Record Number) 사용

     - 고정 길이 레코드(Fixed-Length Record) 방식일 때 유용

     - ex) 각 레코드가 100바이트일 경우, 5번 째 레코드는 400바이트(offset)부터 시작하니까 바로 계산 가능

 

Choosing a Record Structure and Reocrd Length

 

 

 

Header Records

1. 파일의 시작 부분에 위치한 레코드 (파일의 구성과 내용에 대한 정보를 저장

2. 헤더 레코드가 담고 있는 일반적인 정보

  (1) 전체 레코드 수

  (2) 레코드 길이

  (3) 최종 수정 시각

  (4) 각 필드의 이름

  (5) 필드의 폭

  (6) 한 레코드 안에 포함된 필드 수

 

 

🔹 공통 설명

두 구조 모두 헤더 + 고정 길이 레코드로 구성되어 있고,
레코드 안에는 **가변 길이 필드(variable-length fields)**가 들어 있어요.

---

🔸 (a) 구조 설명

📌 개요:

• 헤더 크기: 32바이트
• 레코드 크기: 64바이트
• 구성: 고정 길이 레코드 안에, 각 필드는 **널 문자(Null character, 0x00)**로 끝나는 가변 길이 필드

✅ 예시 특징:

• "Ames|Mary|123 Maple|Stillwater|OK|74075|" 같은 데이터가 들어감
• 필드 사이를 | 구분자로 나누고, **끝에 null (0x00)**이 들어 있어 구분 가능함

---

🔸 (b) 구조 설명

📌 개요:

• 헤더 크기: 66바이트
• 레코드 크기: 68바이트
• 구성: 각 레코드는 **고정 길이 시작 필드(2바이트)**로 시작하여
  ➜ 해당 레코드의 유효 데이터 길이를 나타냄

✅ 예시 특징:

• 맨 앞 2바이트: 유효한 데이터의 바이트 수
• 데이터 필드 뒤에 남는 공간은 0x20 (공백) 등으로 채워져 있음
• 널 종료가 아닌, 길이 정보로 필드 끝을 판별

---

📘 Figure 설명 요약

(a) 구조는:

• 헤더 32바이트
• 레코드 64바이트
• 널 문자로 필드 종료 표시

(b) 구조는:

• 헤더 66바이트
• 레코드 68바이트
• 시작 2바이트에 데이터 길이 정보 포함

 

 

Portability and Standardization

1. 운영체제 간 차이

  - ex) MS-DOS는 줄바꿈을 만나면 **linefeed 문자(\n)**를 추가로 덧붙이는 특성이 있음

          -> Unix/Linux에서는 줄바꿈을 \n, MS-DOS/Windows에서는 \r\n로 처리

 

2. 프로그래밍 언어 간 차이

  - C언어는 헤더를 32바이트로 만들 수 있지만, Pascal은 64바이트로 강제될 수 있음

  - C++는 유연하게 고정 길이 레코드를 조합할 수 있지만 Pascal은 모든 레코드가 동일한 길이여야 함 (특히 텍스트 파일에서)

 

3. 기계 구조(하드웨어) 간 차이

  - 정수값 500,000,000 (10진수)를 16진수로 표현하면 :

    - Sun 시스템 : 1dcd6500 (Big-endian)

    - IBM PC and VAX : 00065cd1d (Little-endian)

  => 이는 바이트 순서, 즉 Endian 차이 때문

 

  - INTEGER 타입 크기도 다름

    - Cray 2 : 8바이트

    - Sun 3 : 4바이트

    - IBM PC : 2바이트