038 정렬의 개요
1. 정렬 방식
- 주기억장치 : 내부 정렬
•선택법 : 히프 정렬
•삽입법 : 삽입 정렬, 쉘 정렬
•교환법 : 버블 정렬, 선택 정렬, 퀵 정렬
•병합법 : 2 - Way Merge Sort
•분배법 : 기수 정렬
- 보조기억장치 : 외부 정렬
•밸런스 병합 정렬
•캐스캐이드 병합 정렬
•폴리파즈 병합 정렬
•오실레이팅 병합 정렬
2. 정렬 알고리듬 선택 시 고려 사항
- 데이터의 양
- 초기 데이터의 배열 상태
- 키 값들의 분포 상태
- 소요공간 및 작업 시간
- 사용 컴퓨터 시스템의 특성
039 내부 정렬
1. 삽입 정렬
- 이미 순서화된 파일 -> 순서에 맞게 삽입
2. 쉘 정렬
- 매개 변수(h)로 입력파일을 서브파일로 구성
- 각 서브파일을 Insertion sort
- 입력 파일이 부분적으로 정렬되어 있는 경우 유리
3. 선택 정렬
- 최소값 찾기 -> 순서대로 놓기
4. 버블 정렬
- 인접한 두개 레코드끼리 비교, 정렬
5. 퀵 정렬
- 부분적으로 나눠가면서 정렬
- 키 기준 작은 값 왼쪽, 큰 값 오른쪽
- 정렬 방식 중 가장 빠름
- Recurrence -> 스택 필요
6. 힙 정렬
- 전이진 트리 이용
- 구성된 전이진 트리 -> Heap tree로 변환
7. 2-way 합병 정렬
- 이미 정렬된 두개 파일 -> 한개 파일로 합병
8. 기수 정렬
- Queue 이용 -> 자릿수 별로 정렬
- 키 값 분석, 같은 수, 문자끼리 버킷에 분배 -> 버킷 순서대로 레코드 정렬
040 검색
1. 선형 검색
- 순서화 되어 있지 않은 파일 -> 순차적으로 검색
- Key값 하나하나 비교
- 순차 검색
- 작성 쉬움
2. 제어 검색
- 순서화된 파일
- 비교 대상이 된 레코드를 다음 비교 대상 선택 기준으로 이용
- 이분 검색
•전체 파일을 두 개의 서브파일로 분리해 가면서 Key 레코드 검색
•Midpoint : M = (F + L)/2
- 피보나치 검색
•피보나치 수열에 따라 다음 비교 대상 선정
- 보간 검색
•있음직한 부분의 키 선택
•선정 레코드 = (추측값 - 최소키 값) / (최대키 값 - 최소키 값) * 레코드 수
- 블록 검색
•레코드들 여러 블록으로 분할, Block 단위 순서화, Block 내 자료 순서 관계 X
•Index : 각 블록 최대 레코드 키 값 저장
- 이진 트리 검색
•파일을 이진 검색 트리로 구성
•순서
- Root Node와 비교
- 작으면 왼쪽 서브트리 크면 오른쪽 서브트리
041 검색 - 해싱
1. 해싱의 개요
- Hash Table, Hash Function
- DAM(직접 접근) 파일 구성할 때 사용
- 접근 속도 빠름, 기억공간 많이 요구
- 검색 속도 가장 빠름
- 삽입, 삭제 빈도 많을 때 유리
- 키-주소 변환 방법
- Hash Table
•버킷 : 하나의 주소를 갖는 파일의 한 구역
•슬롯 : 한 개의 레코드를 저장 할 수 있는 공간
•Collision : 서로 다른 두 개의 레코드가 같은 주소
•Synonym : 같은 주소를 갖는 레코드들
•Overflow : 버킷 내에 레코드 저장공간이 없을 때
2. 해싱 함수
- 제산법 : Hash Table 크기보다 큰 수 중 가장 작은 소수로 Key 나눠 남은 나머지 = 주소
h(K) = K mod Q
- 제곱법 : K 제곱 -> 중간 부분 = 주소
- 폴딩법 : K 여러 부분 -> 더하거나 XOR = 주소 (Shift Folding, Fold Boundary)
- 기수 변환법 : 키숫자 진수 -> 다른 진수로 변환 -> 주소 크기 초과 자릿수 절단 = 주소
- 대수적 코딩법 : 키 값 각 자리의 비트 수 -> 한 다항식의 계수로 간주 ?
- 계수 분석법 : 키 값 숫자 분포 분석 -> 비교적 고른 자리 = 주소
- 무작위법 : 무작위 = 주소
3. Overflow 해결 방법
- 개방 주소법 : 선형 방법 -> 순차적으로 다음 빈 버킷
- 폐쇄 주소법 : 별로의 Overflow 영역 -> Chain(Pointer)으로 홈 버킷에 연결
•Direct Chaining : 해시표 내 빈 자리에 레코드 보관
•Indirect Chaining : 해시표와 별도로 기억공간에 레코드 보관
- 재해싱 : Collision 발생 시 새로운 해시 함수
042 인덱스 구조
1. 인덱스의 개념
- 데이터 레코드를 빠르게 접근하기 위해서 구성
- 데이터가 저장된 물리적 구조와 밀접한 관계
- 레코드가 저장된 물리적 구조에 접근하는 방법 제공
- 레코드에 대한 액세스 빠르게 수행
- 삽입 삭제 수시로 일어나는 경우 -> 인덱스 개수 최소화
2. m-원 검색 트리
- 이진 검색 트리 : 1개 키, 2개 subtree
- m-원 검색 트리 : m-1개 키, m개 subtree
- 키 값의 일부분이 동일 문자열, 숫자 -> 효율적
- 트리 높이가 얕아서 검색시간 단축
- 삽입 삭제시 : 트리 균형 유지 -> 연산 복잡
3. B-트리
- 균형 m-원 검색 트리
- Root, Leaf 제외 모든 노드 m/2 ~ m 사이 subtree
- Root는 적어도 두개의 subtree
- 모든 Leaf 같은 레벨
- Leaf 아닌 노드 키 값 수 : 그 노드 subtree 수보다 한개 적다
- 각 Leaf 노드 수 : m/2 -1 ~ m-1
- 한 노드 안에 있는 키 오름차순
- 탐색, 추가, 삭제 : 루트에서 시작
- 삽입 삭제 -> 데이터 구조 균형 유지해야함
4.B+-트리
- B 트리 변형
- 인덱스 세트 , 리프 노드
- 인덱스 세트 키 값 : 리프 노드 키 값 찾는 경로로만 제공
- 모든 인덱스 세트 키값 -> 리프 노드에 다시 나타남 : 리프 노드만을 이용한 순차 처리 가능
- 추가, 삭제 시 발생하는 노드 분열 합병 연산 과정 간소화
5. 트라이 색인
- 키 값 직접 표현 X : 구성 문자, 숫자 자체로 키 값 구성
- 숫자, 문자열 : 일부분이 같은 문자나 숫자일 때 적합
- 가변 길이 키 값 효과적 표현
- 삽입 삭제 시 노드 분열 병합 X
- 트라이 차수 : 사용하는 문자 수 (Radix)
- 키 값 분포 예측 -> 기억장소 절약
- 트라이 크기 : 나타내려는 키 값 기수, 키 필드 길이
043 파일 편성
1. 순차 파일
- 입력 데이터 -> 논리적 순서에 따라 물리적 연속 공간에 순차적으로 기록
- 일괄 처리(Batch)에 적합
- 자기 테이프
- 장점
•기록 밀도 높음 : 저장 효율 좋음
•매체 변환 용이
•키 숫서대로 편성 -> 취급 용이
- 단점
•삽입 삭제 -> 재구성을 위해 전체 복사 : 시간 소요
•검색 효율 낮음, 응답시간 느림
2. 색인 순차 파일
- 순차 처리, 랜덤 처리
- 키값 순으로 정렬, 키 항목만 모은 색인 구성
- ISAM (Index Sequential Access Method)
- 참조 시 직접 참조 가능
- 자기 디스크 (테이프 X)
- 구성
•기본 구역 : 실제 레코드 기록, 각 레코드 키 값순으로 저장
•색인 구역 : 기본구역에 있는 레코드 위치 찾아가는 색인 기록
- 트랙 색인 구역 : 트랙 내 레코드 중 최대 키값, 주소 기록 -> 한 실린더 당 하나씩
- 실린더 색인 구역 : 트랙 색인 최대 키값, 실린더 정보 기록 -> 한 파일 당 하나씩
- 마스터 색인 구역 : 실린더 색인 구역 정보 기록
•오버플로 구역 : 기본 구역 빈 공간 X -> 예비적으로 확보
- 실린더 오버플로 구역 : 각 실린더마다, 해당 실린더 기본구역 오버플로 데이터 보관
- 독립 오버플로 구역 : 실린더 오버플로 꽉 참 -> 독립 오버플로 구역
3. VSAM 파일
4. 직접 파일
5. 역 파일
6. 다중 리스트 파일
7. 다중 링 파일
