정보처리기사 데이터베이스 요약 12

자격증/정보처리기사

IT grow. 2019. 7. 19. 15:17

12장

1. 선형 검색 (Linear Search)

- 평균 검색 횟수 : ( n + 1 ) / 2

2. 이분 검색 (이진 검색)

- 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어듦으로 탐색 효율이 좋고 탐색 시간이 적게 소요

- 검색할 데이터가 정렬되어 있어야 함

- 중간 레코드 번호 = ( 첫 번째 레코드 번호 + 마지막 레코드 번호 ) / 2

3. 해싱

- DAM(직접 접근 방법) 파일을 구성할 때 해싱이 사용되며, 접근 속도는 빠르지만, 많은 기억공간을 요구

- 키 값으로부터 레코드가 저장되어 있는 주소를 직접 계산하여, 산출된 주소로 바로 접근하는 방법

- 버킷 : 해시 테이블을 구성하는 요소로서 하나의 주소를 갖는 파일의 한 구역을 의미하여 이것의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미

- Collision (충돌) : 서로 다른 키가 동일한 홈 주소를 가지는 경우

- Synonym : 동일한 홈 주소로 인하여 충돌이 일어난 레코드들의 집합

- Overflow : Bucket을 구성하는 Slot이 여러 개일 때는 Collision은 발생해도 Overflow는 발생하지 않을 수 있음

4. 해싱 함수의 종류

- 제산법, 제곱법, 숫자 분석법(=계수 분석법), 폴딩법(레코드 키를 여러 부분으로 나누고, 나눈 부분의 각 숫자를 더하거나 XOR한 값을 홈 주소로 삼는 방식 ) 등

5. Overflow 해결 방법

- 선형 개방 주소법 : 해상에서 충돌이 일어난 자리에서 그 다음 버킷들을 차례로 하나씩 검색하여 최초로 나오는 빈 버킷에 해당 데이터를 저장

- 폐쇄 주소법

- 재해싱

6. 순차 파일

- 자기 테이프에서 사용

- 레코드를 삽입/삭제하는 경우 파일을 재구성해야 하므로 파일 전체를 복사해야 함

- 공간 낭비가 없음

- 기억장치의 효율은 좋으나 순차적으로 검색해야하므로 검색 효율은 낮음

- 다음 레코드에 대한 접근이 빠름

- 파일 구성이 쉬움

- 어떤 기억매체에서도 실현이 가능

- 대화식 처리보다 일괄 처리에 적합한 구조

7. 색인 순차 파일 ( Indexed Sequential File )

- 순차 처리와 임의(랜덤) 처리가 모두 가능

- 효율적인 검색 가능

- 인덱스를 처리하는 추가적인 시간이 소모되므로 파일 처리 속도가 느림

- 오버플로우를 처리하기 위한 별도의 공간이 필요

- 오버플로우 레코드가 많아지면 재편성해야 함

- 색인 순차 파일은 기본 구역(Prime Area) , 색인 구역(Index Area) , 오버플로우 구역(Overflow Area)으로 구성

- 색인 구역은 트랙 색인 영역 <실린더 색인 영역 < 마스터 색인 영역으로 구성

8. 직접 파일

- 레코드는 해싱 함수에 의해 계산된 물리적 주소를 통해 직접 접근이 가능

- 직접 접근 기억장치의 물리적 구조에 대한 지식이 필요

- 판독이나 기록의 순서에 제약이 없음