41_정렬방식

• 내부정렬

ㆍ소량의 데이터에 대하여 주기억장치 내에만 기억시켜서 정렬하는 방식

ㆍ종류 : 하프정렬, 삽입정렬, 버블정렬, 선택정렬, 퀵정렬, 2-Way Merge Sort, 기수정렬(=Radix Sort)

• 외부정렬

ㆍ대량의 데이터에 대하여 보조기억장치에 기억시켜서 정렬하는 방식으로, 대부분 합병정렬(Merge Sort)기법으로 처리

ㆍ종류 : 밸런스 병합정렬, 캐스캐이드 병합정렬, 폴리파즈 병합정렬, 오실레이팅 병합정렬

#42_해싱(Hashing)

• Hash Table이라는 기억공간을 할당하고, 해시함수(Hash Function)를 이용하여 레코드 키에 대한 Hash Table 내의 Home Address를 계산한 후, 주어진 레코드를 해당 기억장소에 저장하거나 검색작업을 수행하는 방식

• DAM(직접접근) 파일을 구성할 떄 해싱이 사용되먀, 접근 속도는 빠르나 기억공간이 많이 요구됨

• 검색 속도가 가장 빠름

• 삽입, 삭제 작업의 빈도가 많을 때 유리한 방식

• 해시 테이블(Hash Table)

ㆍ레코드를 1개 이상 보관할 수 있는 Home Bucket들로 구성한 기억공간으로, 보조기억장치에 구성할 수도 있고 주기억장치에 구성할 수도 있음

해시 테이블 구조

ㆍ버킷(bucket) : 하나의 주소를 갖는 파일의 한 구역을 의미하며, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미

ㆍ슬롯(slot) : 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷 형성

ㆍCollision(충돌현상) : 서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상

ㆍSynonym : 같은 Home Address를 갖는 레코드들의 집합

ㆍOverflow : 계산된 Home Address의 Bucket 내에 저장할 기억공간이 없는 상태(버킷을 구성하는 슬롯이 여러 개일 때는 Collision은 발생해도 Overflow는 발생하지 않을 수 있음)

#43_순차 파일(Sequential File) =  순서 파일

• 입력되는 데이터들을 논리적인 순서에 따라 물리적 연속 공간에 순차적으로 기록하는 방식

• 급여 관리 등과 같이 변동 사항이 크지 않고 기간 별로 일괄 처리를 주로 하는 경우에 적합함

• 주로 순차 접근이 가능한 자기 테이프에서 사용됨

• 순차 파일의 장점

ㆍ기록 밀도가 높아 기억 공간을 효율적으로 사용할 수 있음

ㆍ매체 변환이 쉬워 어떠한 매체에도 적용할 수 있음

ㆍ레코드를 기록할 때 사용한 키 순서대로 레코드를 처리하는 경우, 다른 편성법보다 처리 속도가 빠름

• 순차 파일의 단점

ㆍ파일에 새로운 레코드를 삽입, 삭제하는 경우 파일 전체를 복사해야하므로 시간이 많이 소요됨

ㆍ데이터 검색 시 처음부터 순차적으로 하기 때문에 검색 효율이 낮음

#44_색인 순차 파일(Indexed Sequential File)

• 순차 처리와 랜덤 처리가 모두 가능하도록 레코드들을 키 값순으로 정렬(Sort)시켜 기록하고, 레코드의 키 항목만을 모든 색인을 구성하여 편성하는 방식

• 색인을 이용한 순차적인 접근 방법을 제공하여 ISAM(Index Sequential Access Method)라고도 함

• 레코드를 참조하는 경우 색인을 탐색한 후 색인이 가리키는 포인터(주소)를 사용하여 직접 참조할 수 있음

• 일반적으로 자기 디스크에 많이 사용되며, 자기 테이프에서는 사용할 수 없음

• 색인 순차 파일의 구성

ㆍ기본 구역(Prime Area) : 실제 레코드들을 기록하는 부분으로, 각 레코드는 키 값 순으로 저장됨

ㆍ색인 구역(Index Area) : 기본 구역이 있는 레코드들의 위치를 찾아가는 색인이 기록되는 부분으로, 트랙 색인 구역, 실린더 색인 구억, 마스터 색인 구역으로 구분할 수 있음

ㆍ오버플로우 구역(Overflow Area) : 기본 구억에 빈 공간이 없어서 새로운 레코드의 삽입이 불가능할 때를 대비하여 예비적으로 확보해둔 부분

① 실린더 오버플로우 구역 : 각 실린더마다 만들어지는 오버플로우 구역으로, 해당 실린더의 기본 구역에서 오버플로우된 데이터를 기록함

② 독립 오버플로우 구역 : 실린더 오버플로우 구역에 더 이상 오버플로우된 데이터를 기록할 수 없을 때 사용할 수 있는 예비 공간으로, 실린더 오버플로우 구역과는 별도로 만들어짐

#45_VSAM 파일

• 동적 인덱스 방버블 이용한 색인 순차 파일

• 제어 구간, 제어 구역, 순차 세트, 인덱스 세트로 구성됨

ㆍ제어 구간(Control Interval) : 데이터 레코드가 저장되는 부분

ㆍ제어 구역(Control Area) : 몇 개의 제어 구간을 모아놓은 것

ㆍ순차 세트(Sequence Set) : 제어 구역에 대한 인덱스를 저장한 것

ㆍ인덱스 세트(Index Set) : 순차 세트의 상위 인덱스

• 기본 구역과 오버플로우 구역을 구분하지 않음

• 레코드를 삭제하면 그 공간을 재사용할 수 있음

• 제어 구간에 가변 길이 레코드를 쉽게 수용할 수 있음