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

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.     직접 파일

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

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

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