1과목 데이터베이스 강사 이 민 욱

4. 정렬 알고리즘 예 삽입 정렬 20, 19, 14, 16, 18 오름차순으로 삽입 정렬 하시오. pass1 : 19, 20, 14, 16, 18 pass2 : 14, 19, 20, 16, 18 pass3 : 14, 16, 19, 20, 18 pass4 : 14, 16, 18, 19, 20 2) 버블 정렬 10, 7, 8, 3, 5 버블정렬로 정렬 하시오. pass1 : 7, 10, 8, 3, 5 > 7, 8, 10, 3, 5 > 7, 8, 3, 10, 5 > 7, 8, 3, 5,10 pass2 : 7, 8, 3, 5, 10 > 7, 3, 8, 5, 10 > 7, 3, 5, 8, 10 pass3 : 3, 7, 5, 8, 10 > 3, 5, 7, 8, 10 pass4 : 3, 5, 7, 8, 10

3) 선택 정렬 10, 7, 8, 3, 5 선택 정렬 하시오. pass1 : 7, 10, 8, 3, 5 > 7, 10, 8, , 3, 5 > 3, 10, 8, 7, 5 > 3, 10, 8, 7, 5 pass2 : 3, 8, 10, 7, 5 > 3, 7, 10, 8, 5 > 3, 5, 10, 8, 7 pass3 : 3, 5, 8, 10, 7 > 3, 5, 7, 10, 8 pass4 : 3, 5, 7, 8, 10 4) 2-way 합병 정렬 11, 2, 8, 10, 20, 15, 6, 9, 7, 18을 2-way 합병 정렬로 정렬하시오. pass1 : (11,2) (8,10) (20,15) (6,9) (7,18) > (2,11) (8,10) (15,20) (6,9) (7,18) pass2 : ((2,11) (8,10)) ((15,20) (6,9)) (7,18) > (2,8,10,11)(6,9,15,20)(7,18) pass3 : ((2,8,10,11)(6,9,15,20))(7,18) > (2,6,8,9,10,11,15,20) (7, 18) pass4 : ((2,6,8,9,10,11,15,20) (7, 18)) > (2, 6, 7, 8, 9, 10, 11, 15, 18, 20)

검색(search) 1. 선형 검색(Linener search) = 순차 검색(Sequential search) 대상 자료를 순서대로 하나씩 비교해서 원하는 자료를 찾는 검색 방식으로 자료가 정렬되어 있지 않고 대상범위를 알 수 없을 때 사용 2. 제어 검색(Controlled search) 대상 자료 정렬되어 있고 대상 자료에 대한 범위를 알고 있을 때 정렬할 수 있다. ① 이분검색(Binary search) = 이진 검색     대상 범위를 절반씩 축소시키면서 찾고자 하는 값을 대상 자료의 중간 값과 비교하여 원하는 데이터를 검색하는 방식이다. 중간 값 M = ( F + L ) / 2 (F : 처음 값, L : 마지막 값) 사용 예 1~50까지의 숫자 중 15를 찾는데 걸리는 횟수는? M = (1+50)/2 = 25.5 >> 정수 값만 취한다. 25 25는 찾는 값보다 크므로 1~24사이에 찾는 값 존재한다. M = (1+24)/2 = 12.5 >> 정수 값만 취한다. 12 12는 찾는 값보다 작으므로 13~23사이에 찾는 값 존재한다. M = (13+23)/2 = 18 >> 정수 값만 취한다. 18 18은 찾는 값보다 크므로 13~17사이에 찾는 값 존재한다. M = (13+17)/2 = 15 >> 찾는 값을 4번째 비교하여 찾는 값과 일치

② 피보나치 검색(Fibonacci search)     피보나치 수열을 이용하여 검색하는 방식으로 앞에 있는 자료일수록 오버헤드가 심하고 더하기 빼기만 가지고도 검색 가능한 방식이다. ③ 보간 검색(Interpolation search)     데이터가 있음직한 부분을 보간해서 검색하는 방식으로 사전식 검색이라고도 한다.                    3. 블록 검색(Block search) 데이터를 블록을 묶어 구성하고 블록을 결정할 때는 인덱스를 사용하고 해당 블록 내 부에서는 선형 검색을 사용하여 검색하는 방식 4. 이진 트리 검색(Binary tree search) 데이터를 입력되는 순서에 따라 첫 번째 데이터는 근노드, 다음 데이터부터는 근노드와 비교하여 근노드보다 작으면 좌측에 연결하고, 크면 우측에 연결하여 2진트리로 구성한 다음 같은 방식으로 검색하는 방식

해싱(hashing)은 어떤 키 변환에 의하여 원하는 레코드에 직접 접근할 수 있도록 구성하는 것 1)특징 ▪ DAM(직접접근) 파일을 구성할 때 해싱이 사용된다. ▪ 접근 속도는 빠르나 기억공간이 많이 요구됨 ▪ 검색 속도가 가장 빠름 ▪ 삽입, 삭제 작업의 빈도가 많을 때 유리한 방식 2)해싱(hashing) 이용시 고려 사항 ⓛ 오버플로우 처리                   ② 키 변환 속도                     ③ 버킷 크기 3) 해싱에서 사용하는 용어 ① 해싱 함수(hashing function) : 레코드의 키값을 이용해서 레코드를 저장할 주소를 산출해내는 어떠한 수학식 ② 버킷(bucket) : 하나의 주소를 가지면서 한 개 이상의 레코드를 저장할 수 있는 공간 ③ 충돌(collision) : 해싱 함수에 의해서 계산된 홈 주소가 같은 경우에 벌어지는 충돌 현상 ④ 시노님(synonyms) : 같은 홈 주소를 갖는 레코드의 집합(동거자) ⑤ 슬롯(slot) : 슬롯이란 한 개의 레코드를 저장할 수 있는 공간으로 N개의 슬롯이 모여 버킷(bucket)을 형성한다. ⑥ 오버플로우(overflow) 해당 버킷에 더 이상의 레코드 키 값을 기억시킬 수 없어서 넘쳐나는 현상

4)해싱 함수(hashing function)의 종류 ① 제산법(Division method) : 소수로 나누어 그 나머지 값 이용 ② 기수 변환법(Radix conversion method) 다른 기수값으로 변환하여 그 값 이용 ③ 폴딩(접지)법(Folding method) 키값을 임의의 부분으로 나누어 접어서 더한 값을 이용      ④ 무작위법(Random method) : 무작위로 수를 발생시켜 이용 ⑤ 숫자(계수) 분석법(Digit analysis method) :  키 값의 분포 따라 이용 ⑥ 제곱법(Mid-square method):  키값을 제곱하여 결과 값 이용 5)해싱에서 오버플로우 처리 해당 버킷에 더 이상의 레코드를 기억시킬 수 없어서 넘쳐나는 현상으로 다음의 방법으로 해결한다. ① 선형 방식(Linear method) 오버플로우가 발생했을 때 발생한 버킷의 바로 다음 주소 저장 ② 재해싱 방법 여러 개의 해싱 함수를 준비하였다가 충돌 발생시 새로운 해싱 함수를 적용 ③ 체인 방식(Chaining method) 오버플로우가 발생했을 때 빈 버킷에 레코드를 저장하고 링크 리스트로 연결

인덱스(Index) 데이터 레코드를 빠르게 접군하고 검색하기 위해서 구성한 것 1. 인덱스(Index)의 특징 ① 물리적 구조와 관련       ② 물리적 구조의 접근 경로           ③ 빠른 접근 보장 2. M원 검색 트리 1) B- 트리 B- 트리는 균형된 M-원 탐색 트리로 모든 인덱스 값이 실제 데이터를 가리키도록 구성되어 있기 때문에 인덱스 탐색시 중위 순회(inorder)를 해야 하는 트리이다. ① 루트(root)와 리프(leaf)를 제외한 모든 노드는 반 수의 서브 트리를 갖음 ② 모든 리프는 같은 레벨이다. ③ 루트는 리프가 아닌 이상 적어도 두 개의 서브 트리를 갖는다. ④ 리프가 아닌 노드의 키 값의 수는 그 노드의 서브 트리의 수보다 하나 적다. ⑤ 한 노드 안에 있는 키 값은 오름차순 정렬되어 있다. 2) B+-트리 B+-트리는 B-트리의 추가 삭제시 발생하는 노드의 분열과 합병 연산과정을 줄일 수 있는 트리 구조이다. 3) 트라이(Trie) 탐색을 위한 키값을 직접 표현하지 않고 키를 구성하는 문자나 숫자 자체의 순서 에 의해서 키값을 표현하는 구조이다. - 삽입 삭제시 노드 분열과 병합이 없다.

파일구조 1. 파일 구조 결정시 고려 사항 2. 파일 종류의 구분 1) 순차 파일 ① 파일 저장에 사용될 매체의 특성              ② 매체의 액세스 형태 ③ 자료의 처리 주기                           ④ 자료의 갱신 형태          ⑤ 파일 매체에 대한 접근 특성                  ⑥ 자료의 처리 방식 2. 파일 종류의 구분 1) 순차 파일 입력되는 데이터의 논리적인 순서에 따라 물리적으로 연속된 위치에 기록한 파일 ① 기록 밀도가 좋다                            ② 매체 변환이 용이 ③ 액세스 속도가 빠름                         ④ 삽입과 삭제가 불편 2) 색인 순차 파일(ISAM : indexed sequential access method) 인덱스을 통한 랜덤 처리와 데이터의 순차 처리를 병행할 수 있는 파일 ① 인덱스 구역(index area) : 기본 데이터 영역에 대한 색인을 구성하는 부분 트랙 색인(track index) : 가장 작은 단위의 색인 실린더 색인(cylinder index) : 트랙 색인에 대한 색인 마스터 색인(master index) : 실린더 색인에 대한 색인 ② 기본 데이터 구역(prime data area) : 실제 데이터가 기록되는 부분 ③ 오버플로우 구역(overflow area) : 기본 데이터 구역에 기록되지 못하고 넘친 데이터를 기록하는 부분 실린더 오버플로우(cylinder overflow) : 하나의 실린더 색인 범위마다 두는 오버플로우 구역 독립 오버플로우(independent overflow) : 독립된 오버플로우 구역

3) VSAM(Virtual Storage Access method file) 파일 ISAM 파일에서 오버플로우 구역이 없는 파일, 즉 ISAM 파일은 정적인덱스 편성을 하는데 반해 VSAM 파일은 동적 인덱스 편성을 하여 오버플로우 구역을 두지 않고 미리 예비구역(Virtual Storage)을 두어 삽입이 일어나게 되면 예비구역(Virtual Storage)을 사용하는 방식이다.  4) 역파일(invert file)과 멀티 리스트(multi-list file) 파일 ① 역파일은 키 필드의 길이가 일정하지 않아 관리가 용이하지 않다. ② 멀티 리스트 파일은 필드의 길이가 고정 크기이므로 관리가 용이하다. ③ 역파일은 질의 처리에 대한 우수성을 가지며 검색 속도가 빠르다. (5) 직접 편성 파일(DAM) 레코드 내의 키 필드를 해싱 함수에 의해 물리적 저장 장치의 주소로 변환하여 레코드를 기록하는 방식으로 파일 내에서 일정한 순서 없이 임의 처리를 하고자 할 때 사용한다.