정보처리기사 필기 무료강의 제1과목[DB-09강] 자료구조-정렬과 검색

[DB-09강] 자료구조-정렬과 검색

[DB-09강]자료구조-정렬과검색.pdf

0.15MB

 

학습내용
☞ 자료구조개론
 - 정렬과 검색
 - 파일조직기법(파일편성방법)
학습목표
☞ 자료구조 개론의 정렬과 검색을 이해 할 수 있다
 파일조직기법에 대해 이해 할 수 있다
학습내용
1. 정렬(Sort)의 정의와 기법

 

정렬 : 레코드나 데이터에 담긴 키 값에 따라 순서대로 나열하는 것
내부정렬
 - 주기억장치내, 소량의 데이터
외부정렬
 - 대량의 데이터, 보조기억장치, 병합정렬(Merge Sort)기법으로 처리

2. 버블정렬(Bubble sort) : 인접한 두 키를 비교하여 정렬하는 방식

3. 삽입정렬(Sort) : 새로운 하나의 레코드를 추가(삽입)하여 정렬하는 방식

 

4. 선택정렬(Sort) : 레코드의 최소값을 찾아 정렬하는 방식

 

5. 힙 정렬(Heap Sort) : 전이진 트리를 이용한 정렬방식
기출> 각 레코드 R= {88,74,63,55,37,25,33,19,26,14,9 }에 대해 힙 정렬을 
 만들때 37의 왼쪽과 오른쪽의 자식노드의 값은?

퀵, 기수, 2-WAY-MERGE정렬은 교재에서 정리합니다.

 

6. 검색(Search)
선형검색(Linear Search) : 순차검색으로 프로그램 작성이 가장 쉬움. 제어검색(Control Search) : 순서화된 파일이어야 검색가능
 (이분검색, 피보나치검색, 보간검색, 블록검색, 이진트리검색)
이진검색(Binary search) : 정렬이 되어있는 레코드를 2개부분으로 나누어 검색하는 방법

 

7. 해싱(Hashing)
해시함수(Hash Function)를 이용하여 Hash Table 내의 Home Address를 계산한 후 주어진 레코드를 해당 기
억장소에 저장하거나 검색을 수행하는 방식

[해시테이블]

 

버킷(Bucket) : 하나의 주소를 갖는 파일의 한 구역, 같은 주소에 포함될 수 있는 레코드 수를 의미
슬롯(Slot) : 한 개의 레크드를 저장할 수 있는 공간
Collision(충돌현상) : 레코드를 삽입할 때 2개의 상이한 레코드가 똑같은 주소로 해싱되는 것을 의미
Synonym(동의어) : 해싱 함수의 값이 같은 키들의 집합
Overflow : 계산된 홈주소의 버킷 내에 저장할 기억공간이 없는 상태온라인

 

8. 해싱(Hashing) 함수의 종류
제산법의 예 : 적어도 5000개의 레코드를 수용할 수 있는 해시표에 키값이 123456789인 레코드가 저장되는 홈 주소는?
 h(K)=123456789 mod 5003 = 2761
제곱법의 예 : 키값이 20140427인 레코드가 저장되는 홈 주소는? (단, 8~11번째 자리의 4자리 숫자를 홈 주소로 삼는다)
 20140427^2=405636799742329
따라서, h(K)=9974
폴딩법 : 주어진 키를 여러 부분으로 나누고 각 부분의 값을 더하거나 XOR연산을 통하여 나온 결과로 주소를 취하는 방법
 - Shift Folding : 왼쪽 또는 오른쪽 끝자리 맞춰 계산
 - Fold Boundary : 경계 지점을 접었을때 마주치는 자리 그대로 계산
기수 변환법
계수 분석법
숫자 분석법
9. 인덱스(Index)
데이터 튜플을 빠르게 검색하고 접근하기 위한 것이다.
 - 인덱스가 없으면 TABLE SCAN(전체를 다 뒤지는)을 해야 함
 - INDEX SCAN : 자격이 있는 모든 테이블이 행을 검색(INDEX가 없을때도 검색) - INDEX SEEK : INDEX가 있는 테이블을 검색할때 사용
인덱스의 종류
 - m-원 검색 트리 : 2진 검색트리를 일반화한 트리, 복잡한 연산이 수반되어야 하는 단점이 있음. 
 - B-트리 : 규형 잡힌 m-원 검색 트리
 - B*-트리 : B-트리의 문제점인 빈번한 노드의 분할을 해소하는 목적
 - B+-트리 : 인덱스 셋(Index set)과 순차 셋(Sequence Set)으로 구분(B-트리의 변형)
 트라이(trie)
 - 검색을 위한 키 값을 직접 표현하지 않고 
 키를 구성하는 문자나 숫자 자체의 순서로 키 값을 구성하는 구조
10. 파일조직 기법( 파일편성법)
* 순차 파일(Sequential file)
* 직접 파일(Direct file)
* 색인 순차 파일(ISAM ; Indexed sequential access-method)
* VSAM(Virtual Storage Access Method)

* 다중 키 파일(Multi key file)
 역파일(Inverted File)
 다중 링 파일(Multi-Ring File)
 다중 리스트 파일(Multi-List File)
요점정리
1. 자료구조 개론
 정렬의 개념과 종류를 정리해 둡니다.
 검색기법에 대해 정리합니다.
 파일편성법에 대해 정리합니다. 다음차시예고
수고하셨습니다. 다음 10주차에서는 “[DB-10강] 데이터베이스의 과거, 현재 그리고 미래”에 대해서 학습하도록 
하겠습니다