화일 처리 및 응용 공부#10 (순차화일)

2021.03.26 - [이론공부/화일처리및응용] - 화일 처리 및 응용 공부 #9 (버퍼)

이전에 배운 내용도 확인해보자.

---

순차 화일

 

스트림화일

 - 데이터가 하나의 연속된 바이트 스트림으로 구성됨

 - 연속적인 판독 연산을 통해 레코드가 화일에 저장되어있는 순서에 따라 데이터를 접근

 

레코드 저장 기준에 의한 종류

 - 입력 순차 화일

     - 레코드가 입력되는 순서대로 저장, heap file, pile file

 

 - 키 순차 화일

     - 레코드의 특정 필드 값 순서에 따라 저장

 

 

화일 생성

 - 데이터 저장장치에 레코드들을 순서대로 입력하여 생성

 - 키 순차 화일의 갱신(삽입, 삭제, 변경) 연산은 트랜잭션 화일을 이용

 

편집

 - 트랜잭션 화일 생성 과정에서 입력되는 데이터 값에 오류가 있는지 검사하는 과정

 - 검사내용

    - 입력된 값이 올바른 범위 안에 있는가

    - 필수적인 필드 값 존재 여부, 필드 타입 적절성, 필드 값 유효성, 관련 필드 값 유무

 

 

 

 

입력순차 화일

• 데이터가 입력되는 순서대로 저장된 화일
• 레코드에 대한 분석, 분류, 표준화 과정을 거치지 않음
• 필드의 순서, 길이 등에 제한이 없음
• 레코드의 길이, 타입이 일정하지 않음
• 레코드는 <필드, 값> 쌍들로 구성
• ex) [CITY = 서울 #POPULATIOPN = 800M;] ,  [SNUMBER = 1234 #NAME = 홍길동 #SEX 남 #IQ =130;]

 

키 순차 화일

• 화일 내에서의 레코드는 키 필드 값에 따라 정렬
• 저장 장치에서의 레코드의 물리적 순서와 레코드 리스트의 논리적 순서가 같은 구조의 화일
• 모든 레코드는 똑같은 순서의 데이터 필드로 구성
• 데이터 필드는 화일 설명자에 한번만 저장하면 됨
• ex) 아래표와 같은 형식

학번	이름	나이	본적	성
1234	홍길동	20	서울	남
1235	김철수	20	충청	남
1236	박영희	19	전라	여

여기서 키필드는 학번

 

갱신(삽입, 삭제, 수정)

삽입,삭제,수정 절차(알고리즘)

 

키 순차 화일 알고리즘

갱신 도중 발생 할 수 있는 오류

• 마스터 화일에 있는 레코드 키 값을 가진 레코드를 삽입
• 마스터 화일에 없는 레코드 키 값을 가진 레코드를 삭제
• 마스터 화일에 없는 레코드 키 값을 가진 레코드를 수정

 

 

 

 

레코드 삽입

1. 레코드 사이에 삽입 위치를 검색
2. 삽입점 앞에 있는 레코드를 새로운 화일로 복사
3. 새로운 레코드를 삽입
4. 새로운 화일에 삽입점 이후에 레코드를 복사

레코드 삭제

1. 삽입과 거의 같은 단계를 거침
2. 삭제할 레코드를 제외하고 나머지 레코드만 새로운 화일로 복사

레코드 수정

1. 수정할 레코드 앞의 모든 레코드를 새로운 화일로 복사
2. 원하는 레코드를 수정해서 새로운 화일에 삽입
3. 나머지 레코드들을 새로운 화일로 복사
4. 직접 접근 저장 장치에 저장된 화일

순차 마스터 화일에 경우 일정기간 갱신 트랜잭션들을 모아서 일괄처리한다.

 

 

전체적인 순차화일 갱신 작업 알고리즘

 

정렬된 화일

순차화일의 정렬 순서

• 응용에 따라 결정 - 이름순 상호순 등등
• 하나의 순차 화일은 두개의 상이한 정렬 순서를 만족시킬수 없음
• 여러가지 상이한 정렬 순서의 화일이 필요한 경우에는 임시 화일을 만들어 사용했다가 사용후에 화일을 삭제함

순차 화일의 특징

• 대화식 처리 보다는 일괄 처리에 유리
• 장점 : 데이터 순차접근에서는 차위 레코드의 접근이 신속함
• 데이타의 접근 형태를 고려한 뒤 그 접근 방법에 맞는 화일 구조를 선정

 

 

정렬/합병

내부정렬

• 데이터가 적어서 메인 메모리 내에 모두 저장시켜 정렬 가능할 때 사용
• 레코드 판독, 기록에 걸리는 시간이 크게 문제 되지 않음

외부정렬

• 데이터가 메인메모리 용량을 초과 하는 경우 보조기억장치를 이용하여 정렬하여 정렬하는 방법( 대부분의 저장된 화일 정렬시 주로 외부 정렬을 이용함)
• 레코드 판독, 기록에 걸리는 시간이 중요함
• 정렬/합병 과정
  • 런(run)을 만들어서 합병함 
  • 런 : 하나의 큰 화일을 여러개의 작은 화일로 분할하여 정렬시킨 서브화일
  • 합병(merge) : 런들을 합하여 하나의 정렬된 화일로 만드는것

 

런 생성 방법

• 내부 정렬
• 대체 선택
• 자연 선택

 

내부 정렬

1. 화일을 m개 레코드씩 분할

2. 분할된 레코드들을 내부 정렬 기법으로 정렬

 

내부 정렬 예시

• 마지막 런을 제외하고 모든 런들의 길이가 같음
• 런의 길이를 예측할 수 있으므로 합병 알고리즘이 간단

 

 

대체 선택

특정 알고리즘을 통해서 런을 생성함.

 

대체 선택과정으로 런이 생성되는 과정 정리

대체선택 런 생성 결과

 

 

특징

 - 내부정렬과 다르게 입력화일 내부에 일부 정렬된 레코드들의 순서를 이용

 - 내부 정렬 방법보다 런의 길이가 평균적으로 2*m 만큼 길다

 - 런의 길이가 일정하지 않아 정렬/합병 알고리즘이 복잡

 - 런의 길이가 길수록 합병 비용이 적음

 

 

자연 선택

 - 동결된 레코드들을 버퍼에 유지하지 않고 보조 기억장치의 저장소에 별도 저장

 - 하나의 런 생성 작업은 저장소가 꽉차거나 입력 화일의 끝에 도달할 때까지 계속

 - 런을 길게 만들어 런 수를 줄임으로써 합병 비용을 줄임

 

대체 선택에 비해 주기억장치를 많이 사용하여서 런 길이가 상대적으로 더길다.

 

• 위에 두 방법보다 더 긴 런을 생성할 수 있음
• 저장소로의 입출력이 문제가 됨
• 긴 런 생성에 따른 효율화가 저장소 전송 비용보다 이익이 될 수도 있음

 

 

---

느낀점 : 수업 내용과는 관계없이 빅데이터, 알고리즘에 관해서 조사해보시란다.. 일단 알아두자..
알고리즘은 이전 자료구조 공부할떄 내용이 있으므로 그걸로 다시 이해하자

추가적으로, 갱신 알고리즘으로 인해 발생할 수 있는 오류와 처리 방식과, 내부정렬과 외부정렬의 차이를 이해하자. 내부정렬, 대체선택, 자연선택등의 런을 생성하는 3가지 방법을 이해하자.

2021.03.07 - [이론공부/자료구조] - 자료구조 공부 #1 (자료구조와 알고리즘)

자료구조 공부 #1 (자료구조와 알고리즘)

자료구조시간에 배운 알고리즘 내용을 참고하자