데이터베이스

소개글

데이터베이스 에 대한 보고서 자료입니다.

본문내용

가정 먼저 삽입된 자료가 가장 먼저 FIFO 방식으로 처리된다.
(3) 비선형 구조 : 트리(Tree), 그래프(Graph)
(4) 이진 트리의 순회 : 전위(Preorder) 순회, 후위(Postorder) 순회, 주위(Inorder) 순회
(5) 그래프의 순회
- 깊이 우선 탐색(DFS; Depth First Search)
스택을 사용하며, 전위 순회 트리 탐색과 유사하다.
- 너비 우선 탐색(BFS; Breadth First Search)
큐(queue)를 사용하며, 레벨 순서 순회 트리 탐색과 유사하다.
2. 정렬과 탐색
(1) 정렬 알고리즘 선택시 고려사항
- 키 값들의 분포 상태,
- 소요 공간 및 작업 시간
- 정렬에 필요한 기억 공간의 크기
(2) 내부 정렬 : 주 기억장치 내에서 이루어지는 정렬
* 삽입 정렬(Insertion Sort)
* 셀렉션 정렬(Selection Sort)
* 셀 정렬(Shell Sort)
* 버블 정렬(Bubble Sort) 인접한 자료와 비교하면서 그 크기에 따라 데이터 위치를 바꾸어 정렬
* 기수 정렬(Radix Sort)
* 퀵 정렬(Quick Sort) : 스택이용
* 히프 정렬(Heap Sort) : 이진트리로 구성한 후에 정렬, 연산시간이 최악과 평균의 경우 모두 0으로 빠른 속도를 갖는 정렬방식
(3) 외부 정렬 : 보조기억장치를 이용한 정렬 방법
* 자연 합병 병렬(Natural Merge Sort)
* 균형 합병 정렬(Balanced Merge Sort)
* 계단식 합병 정렬(Cascade Merge Sort)
* 다단계 합병 정렬(Polyphase Merge Sort)
* 진동 합병 정렬(Oscillation Merge Sort)
(4) 탐색(Search)
* 선형 탐색(Linear Search, sequential Search)
* 이진 탐색(Binary Search)
* 이진 트리 탐색(Binary Tree Search)
* 피보나치 탐색(Fibonacci Search)
* 보간 탐색(Interpolation Search)
* 블록 탐색(Block Search)
3. 인덱스 구조
(1) 인덱스 응용 : B-트리
- B-트리가 가지는 성질
* 한 노드 안에 있는 키 값은 오름 차순을 유지한다.
* 모든 리프(Leaf) 노드는 같은 레벨에 있다.
* 루트(Root) 노드는 리프가 아닌 이상 적어도 두 개의 서브 트리를 갖는다.
- 색인
* B+ 트리는 B트리의 추가, 삭제 시 발생하는 노드의 분열과 합병 연산 과정을 줄일 수 있는 트리구조이다.
* m-원 트리 구조는 키 값의 일부분이 동일한 문자열이나 숫자로 구성된 자료를 표현하는데 효율적이다.
* 균형 트리는 실제 레코드까지의 탐색 길이가 동일하게 색인부를 완전 균형 트리로 구성한다.
(2) 인덱스 방법 : 정적(Static) 인덱스 방법, 동적(Dynamic) 인덱스 방법
4. 파일 구조
(1) 파일 조직 선택하는데 영향을 주는 요인
* 사용할 보조 기억 장치의 유형
* 응용이 필요로 하는 파일 연산의 유형
* 파일 활동 비율
* 트랜잭션이나 검색 요청에 대한 응답 시간
- 트랜잭션의 특징 (08년 1회 정보처리 기사출제)
* 트랜잭션의 연산은 데이터베이스에 모두 반영되든지, 아니면 전현 반영되지 않아야 한다.
* 트랜잭션이 그 실행을 성공적으로 완료하면 언제나 일관성 있는 데이터베이스 상태로 변환한다.
* 트랜잭션에 의해서 생성된 결과는 계속 유지되어야 한다.
(2) 순차 파일(Sequential File)
* 장점 : 기억 장소의 낭비가 없고 취급이 용이
* 단점 : 레코드 삽입, 삭제 시 낭비가 심하고 순서적 처리만 가능
(3) 색인 순차 파일(Indexed Sequential File)
- 구 성 : 기본데이터 영역, 인덱스 영역, 오버플로 영역
- 인덱스를 저장하기 위한 공간과 오버플로 처리를 위한 별도의 공간이 필요하다.
- 실제 데이터 처리 외에 인텍스를 처리하는 추가적인 시간이 소모되므로 파일 처리속도가 느리다.
- 순차처리와 직접 처리가 모두 가능하다.
* 장점 : 순서, 직접, 랜덤(Random) 처리가 가능하고 파일 중간에 레코드의 삽입과 삭제가 용이
* 단점 : 처리 속도가 느리고 주기적으로 재 편성
(4) 역 파일(Inverted File)
- 검색 속도가 빠르다.
- 데이터 파일에 접근하지 않아 질의 응답 시간이 줄어들고, 처리가 비교적 쉽다.
- 질의를 만족하는 레코드 검색 시 한 번씩만 접근하면 된다.
* 장점 : 특정 레코드의 처리가 빠르고, 파일 중간에 있는 레코드의 수정 가능
* 단점 : 기억 장소의 낭비가 가장 심하고, 가변 길이 레코드의 처리가 불가능
5. 해싱 기법
(1) 해싱(Hashing) (08년 1회 정보처리산업기사 출제)
* 버킷(bucket)이란 하나의 주소를 갖는 파일의 한 구역을 의미하며, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미한다.
* 슬롯(slot)이란 한 개의 레코드를 저장할 수 있는 공간으로 n 개의 슬롯이 모여 하나의 버킷을 형성한다.
* 충돌(collision)이란 레코드를 삽입할 때 2개의 상이한 레코드가 똑같은 버킷으로 해싱되는 것을 의미한다.
* 충돌이 발생하여도 버킷에 저장할 공간이 있으면 오버플로가 발생하지 않는다.
- 제산법 : 키 값을 양의 정수인 소수로 나누어 나머지를 홈 주소로 취하는 방법
(2) 해싱(Hashing) 함수
- 버킷(Bucket)
- 슬롯(Slot)
- 오버플로(Overflow)
- 충돌(Collision)
- 유사 레코드(Synonym Record)(08년 1회 정보처리산업기사 출제)
* 동일한 홈 주소로 인하여 충돌이 일어난 레코드들의 집합
(3) 해싱을 이용한 파일 구조(08년 1회 정보처리 기사출제)
* 순차파일
* 색인 순차 파일
* 다중 키 파일