데이터베이스: 자료구조(선형/비선형, 정렬, 검색, 인덱스, 파일편성)
자료구조 (Data Structure)
1. 선형 구조: List, Stack, Queue, Deque
2. 비선형 구조: Tree, Graph
1. 선형구조 (Linked List는 순차적 아님)
Linear List: 선형, 연접, 축차 구조 리스트. Array, 빠름, 효율 좋음
Linked List: 연결, 선형 구조이지만 순차적 아님, 노드 삽입삭제 용이, 희소행렬에서 기억장소 절약, 트리 표현에 가장 적합, 느림/효율 나쁨
Stack: 복귀주소, LIFO, 재귀프로그램, Recursive, 자기자신호출, 0주소 지정방식, 후위표기법(Postfix)
Queue: 작업 스케줄링, FIFO, Front 삭제/Rear 삽입
Deque: Stack+Queue, 입력제한데크 Scroll/출력제한데크 Shef 1:1
2. 비선형구조
Tree: 단말노드 Terminal=Leaf(Degree가 0), 비단말노드 Non-Terminal, 형제노드 Sibiling
이진트리 : 자식이 2 이하인 노드로만 구성된 트리.
정이진트리(Full Binary Tree) : 전체 노드수는 2^n - 1
전이진트리(Complete Binary Tree) : 정이진트리 만드는 과정
트리의 운행법 : Preorder(루트-L-R), Inorder(L-루트-R), Postorder(L-R-루트)
이진트리 수식의 표기법
전위표기법(prefix) = X - + A x + B / C D E F
중위표기법(infix) X = A + (B + C / D) x E - F
후위표기법(postfix) X A B C D / + E x + F - =
Graph: 정점(Vertex)와 간선(Edge) 집합. Tree는 사이클이 없는 Graph
인접행렬(Adjacency Matrix)을 이용한 그래프의 표현 방법 체크할 것
최소비용 신장트리(MST, Minimum Cost Spanning Tree) : 가중치가 가장 작은 간선들을 사이클을 이루지 않도록 연결시켜 만든 그래프
정렬 Sort
1. 내부정렬: 메모리(Insertion Sort, Shell Sort,...2Way Merge), 영어단어 쉬움
2. 외부정렬: 보조장치 이용. Merge 합병, 영어단어 복잡
내부정렬
삽입 정렬(Insertion Sort) : 이미 순서화된 파일에 새로운 하나의 레코드를 삽입, 2번째 값부터 차례로 비교
선택 정렬(Selection Sort) : 최소값을 찾아 첫번째 위치에 놓음. 왼쪽 끝 최소값부터 완성
버블 정렬(Bubble Sort) : 인접한 두개의 레코드 비교하여 교환. 오른쪽 끝 최대값부터 완성
퀵 정렬 : 작은 값은 왼쪽에, 큰 값은 오른쪽에 모이도록 함. 가장 빠름, 스택 필요
힙 정렬 : 전이진트리를 이용
2-Way 합병 정렬 : 이미 정렬된 두 개의 파일을 한개의 파일로
기수 정렬(Radix Sort) = Bucket Sort
정렬 알고리즘 선택시 고려사항 : 데이터양, 초기데이터 배열 상태, 키 값들의 분포 상태, 소요공간 및 작업시간, 사용컴퓨터 시스템의 특성
검색 Search
선형 검색(Linear Search) : 순차 검색(Sequential Search). 프로그램 쉽다.
제어 검색(Control Search) : 반드시 순서화된 파일만 검색 가능.
- 이진검색(Binary Seatch) : 중간 레코드 번호 M = (첫번째 레코드 번호 + 마지막 레코드 번호)/2
피보나치 검색, 보간 검색, 블록 검색, 이진트리 검색 등
해싱(Hashing) 검색 : 해싱은 Hash Tabel이라는 기억 공간을 할당하고, 해시 함수를 이용하여 레코드 키에 대한 Hash Table 내의 Home Address를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행하는 방식.
- DAM(직접접근) 파일을 구성할 때 사용. 접근 속도는 빠르나 기억 공간이 많이 요구
- 검색 속도 가장 빠름, 삽입/삭제 많을 때 유리, 키-주소 변환 방법
해시테이블(Hash Table)
버킷(Bucket) : 하나의 주소를 갖는 파일의 한 구역. 버킷크기 = 같은 주소에 포함될 수 있는 레코드 수
슬롯(Slot) : 한 개의 레코드를 저장할 수 있는 공간. n개의 슬롯이 모여 하나의 버킷
Collision(컬리젼:충돌현상) : 서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상
Synonym(시노늄:동의어) : 같은 주소값을 갖는 레코드들의 집합
Overflow : Bucket 내에 저장할 기억공간이 없는 상태.
Bucket을 구성하는 Slot이 여러개일 때 Collision은 발생해도 Overflow는 발생하지 않을 수 있다.
해싱함수(Hashing Function)
제산(Division)함수 : 레코드 키를 해시테이블 크기보다 큰 수 중 가장 작은 소수로 나눈 나머지를 홈주소로
제곱(Mid-Square)함수 : 레코드 키 값을 제곱한 후 중간부분 값을 홈주소로
접지(Folding)함수=폴딩 : XOR(배타적논리합) 값을 홈주소로 삼는 방식
기수변환(Radix) : 어떤 진법 레코드 키 값을 다른 진법으로 간주하고 키 값을 변환
대수적 코딩(Algobraic Coding)
계수분석(숫자분석법) : 키 값 중에서 키를 구성하는 자릿수들의 분포를 조사
인덱스 INDEX
데이터 레코드를 빠르게 접근하기 위해 구성하는 것
- 인덱스는 데이터 베이스의 물리적 구조와 관계
- 인덱스는 하나 이상의 필드로 만들어도 된다.
- 삽입과 삭제가 수시로 일어나는 경우 인덱스는 최소로 하는 것이 좋다.
- 인덱스를 통해 테이블의 레코드에 대한 액세스를 빠르게 수행할 수 있다.
B-트리 : index를 구성하는 방법 중 가장 많이 사용하는 균형된 m원 검색 트리.
- 한 노드 안에 있는 키 값은 오름차순을 유지한다.
- 모든 Leaf 노드는 같은 레벨에 있다
- 루트 노드는 리프가 아닌 적어도 두 개의 서브트리를 갖느다.
- 키 값의 삽입/삭제시 노드의 분할/병합이 일어나므로 노드수가 변한다.
- 탐색/추가/삭제는 루트로부터 시작한다.
- 루트와 리프를 제외한 모든 노드는 최소 m/2
B+-트리
B트리의 추가/삭제시 발생하는 노드의 분열과 합병 연산과정을 줄일 수 있는 트리 구조
B+-는 인덱스 세트와 리프노드로만 구성된 순차 데이터 세트로 구성된다.
- 인덱스 세트에 있는 키 값은 리프 노드에 있는 키 값을 찾아갈 수 있는 경로로만 제공된다.
파일 편성 : SAM, ISAM, VSAM, DAM
1. 순차 파일(Sequential Access Method File: SAM) = 순서 파일
- 입력 데이터들을 물리적 연속 공간에 순차적으로 기록. 자기 테이프 등
- 장점 : 기억공간 효율적, 매체 변환 용이, 레코드가 키 순서라 취급 용이, 레코드를 사용키 순서대로 처리할 때 처리 속도 빠름
- 단점 : 파일에 새 레코드 삽입/삭제시 파일 재구성을 위해 전체 복사하므로 시간 소요, 데이터 검색시 처음부터 순차검색하므로 검색 효율이 낮고 시간 및 응답 시간이 느리다
2. 색인 순차 파일(Indexed Sequential Access Method File: ISAM)
- 순차 처리와 랜덤 처리가 모두 가능하도록 키 값 순으로 정렬 시키고 레코드 키 항목만을 모은 색인을 구성하여 편성. 자기 디스크 등에 사용(자기 테이프 불가)
- 색인 순차 파일의 구성 : 기본 구역(Prime), 색인 구역(Index), 오버 플로 구역(Overflow)
- 기본 구역(Prime Area) : 실제 레코드를 기록하는 부분. 각 레코드는 키 값 순으로 정렬
- 색인 구역(Index Area) : 트랙(Track)-실린더(Cylinder)-마스터(Master)
- 오버 플로 구역(Over Flow Area) : 빈 공간이 없어 새로운 레코드 삽입 불가능할 때의 예비 공간
- 장점 : 순차처리/랜덤처리 모두 가능, 효율적 검색 가능, 레코드 삽입/삭제/갱신 용이, 레코드 추가시 파일 전체를 복사할 필요가 없다
- 단점 : 색인 구역과 오버플로 구역 추가 기억 공간 필요, 오버플로 레코드가 많아지면 파일 재편성 필요, 파일이 정렬되어 있어야 하므로 추가/삭제가 많으면 효율 떨어짐, 색인을 이용하므로 액세스 시간이 랜덤 편성보다 떨어짐
3. VSAM 파일(Vertual Storage Access Method File: VSAM)
제어 구간, 제어 구역, 순차 세트, 인덱스 세트로 구성
4. 직접 파일(Direct Access Method : DAM) = Random File, Direct File
- 파일을 구성하는 레코드를 특정 순서없이 임의의 물리적 저장공간에 기록
- 키가 할당, 해시함수를 이용하여 보조기억장치의 물리적 상대 레코드 주소를 계산
- 임의 접근이 가능한 자기 디스크, 자기 드럼에 사용
- 장점 : DASD(직접접근기억장치)의 물리적 주소를 통해 파일 각 레코드에 직접 접근하거나 기록, 접근 및 기록 순서에 제약 없다, 접근 시간 빠르고 레코드 삽입/삭제/갱신이 용이, 어떤 레코드라도 평균 접근시간 내에 검색 가능
- 단점 : 레코드 주소 변환 과정 필요, 주소 변환 시간 소요, 기억공간 효율 저하될 수 있다, 기억장치의 물리적 구조 지식 필요, 프로그래밍 작업 복잡, 충돌이 발생할 염려가 있으며 이를 위한 기억공간 확보 필요
5. 역 파일(Inverted File) : 다중 키 파일
6. 다중 리스트 파일, 다중 링 파일 등