DB - 자료 구조의 기본

자료구조의 분류 ☆☆☆☆☆

* 선형구조와 비선형 구조의 구분은 매우 중요

선형 구조 : 스택(stack), 큐(Queue), 데크(Deque), 배열(Array), 연결리스트(Linked List)

비선형 구조 : 트리(Tree), 그래프(Graph)

 

선형구조 : 데이터를 저장시키는데 있어 데이터와 데이터를 1:1 대응 구조로 관계 맺어 저장시키는 형태의 구조를 선형 구조라 한다.

 

스택(Stack) ☆☆☆☆☆

스택의 특징

1. 스택은 포인터를 한 개 두고 운용한다.

2. 처음 입력시킨 자료는 맨 마지막에 출력되고,

맨 마지막에 입력시킨 자료는 맨 처음에 출력되는 LIFO(Last In First Out)구조이다. 

3. 한쪽에서만 입출력하는 구조이다.

 

스택의 응용 분야

1. 함수 호출이나 부 프로그램 호출 시 복귀를 저장할 때

2. 인터럽트 분기 시 복귀 주소를 저장할 때

3. 되부름 시 복귀 주소를 저장할 때

4. 수식을 연산할 때

5. 0주소 명령어 형식의 자료 저장소

 

알고리즘

삽입 알고리즘 : 차례로 A. B라는 자료를 Stack에 삽입시킨다면 먼저 삽입시키고자 하는 위치로 top 포인터를 하나 증가시켜 위치시키고 데이터를 삽입시킨다.

 

삭제 알고리즘

삭제시킬 때는 Top 포인터가 위치한 곳의 내용을 먼저 삭제하고 나서 포인터 Top를 하나 감소시켜 다음 데이터에 위치시키는 것이다.

 

큐(Queue) ☆☆☆☆☆

큐의 특징

1. 큐는 삽입(rear, tail)과 삭제(front, head) 포인터 두 개를 두고 운용한다.

2. 큐는 한쪽 방향에서는 입력만 하고, 다른 한쪽 방향에서는 출력만 하는 구조이다.

3. 큐는 먼저 입력된 자료가 먼저 출력되는 FIFO(First In First Out) 구조이다.

 

큐의 응용 분야

1. 스풀(Spool) 운용 처리에 사용된다

2. 운영체제의 스케쥴링(Scheduling) 작업에 사용된다. // 스케쥴링이란 처리한 일들의 진행 순서를 정하는 작업이다.

 

데크(Deque) ☆☆☆☆☆

데크의 특징

1. 포인터를 두 개 두고 운영한다(left, right).

2. 가장 일반적인 구조이다.

3. 양쪽 끝에서 입출력이 일어나는 구조이다.

4. 입력 제한 데크는 스크롤(Scroll), 출력 제한 데크는 셸프(Shelf)라 한다.

Scroll : 출력은 양쪽에서 모두 일어나지만, 입력은 한쪽으로만 제한한 구조를 말한다.

Shelf : 입력은 양쪽에서 모두 일어나지만, 출력은 한쪽으로만 제한한 구조를 말한다.

5. 데크는 Double Ended Queue의 약어이다.

 

배열(Array)의 구조

선형 리스트(Linear List), 순서 리스트(Ordered List), 순차 리스트(Sequential List), 연접 리스트(Denese List), 밀집 리스트라고도 하며 같은 크기의 기억 장소를 연속된 공간에 모아놓고 원하는 데이터를 기록하거나 액세스하는 것을 의미한다.

 

배열 구조의 장단점

장점

1. 액세스 속도가 빠르다. / 2. 기록 밀도가 1이다. / 3. 가장 간단한 구조이다.

단점

1. 삽입, 삭제가 어렵다. / 2. 메모리에 종속적이다.

 

연결 리스트(Linked List)

링크 리스트 또는 연결 리스트라고 하며 자료를 구성할 때 포인터 자료를 포함해서 하나의 자료를 구성하는 형태로, 이 포인터를 이용해서 현 자료와 관계있는 자료를 연결하는 형식으로 구성하여 저장시키는 경우이다.

 

장점

1. 노드의 삽입, 삭제가 쉽다 / 2. 메모리에 대해 독립적이다 / 3. 메모리 단편화를 방지하여 기억 장소를 절약할 수 있다.

4. Garbage Collection을 할 수 있다. // 사용하지 못하는 기억공간은 모으는 작업 / 5. 희소 행렬을 연결리스트로 표현하면 기억 장소가 절약된다.

 

단점

1. 액세스 속도가 느리다. / 2. 포인터를 위한 추가 공간이 필요하다. / 3. 중간에 단절되면 다음 노드를 찾기 어렵다.

 

트리(Tree) ☆☆☆☆☆

트리의 용어

1. 근노드(Root Node) : 트리의 뿌리가 되는 노드를 의미한다. 

2. 단노드(Terminal Node, Leaf) : 노드의 차수(Degree)가 0인 노드 또는 자식이 없는 노드를 의미한다.

3. 간노드(Nonterminal Node) : 노드의 차수(Degree)가 0이 아닌 노드 또는 자식을 가지고 있는 노드를 의미한다.

4. 차수(Degree) : 각 노드의 가지 수, 또는 각 노드가 가지고 있는 자식 노드의 수를 의미한다.

5. 트리의 차수(Tree Degree) : 트리 전체에서 노드의 차수가 가장 큰 것을 트리의 차수라고 한다.

6. 레벨 : 근노드를 1레벨로 하여 차례로 2,3레벨로 증가시켜서 표시한다.

7. 높이(Height) : 트리의 총 높이를 의미한다. 

8. 자노드(Child Node) : 각 노드에 연결되어 있는 다음 레벨의 노드를 의미한다.

9. 부노드(Parent Node) : 각 노드의 바로 상위 레벨에 있는 노드를 의미한다.

10. 제노드(Sibling Node, Brother Node) : 같은 부노드에 연결되어 있는 노드를 의미한다.

11. 숲(Forest) : 트리가 모여서 이루어진 집할을 의미한다.

12. 서브 트리(Sub Tree) : 임의의 노드를 제거했을 때 생길 수 있는 트리의 집합을 의미한다.

 

트리의 운행(Tree Traversal)

중위 운행(Inoerder Traversal) :

<좌측, 근, 우측> 순서로 운행하는 방법으로 먼저 근노드를 중심으로 좌측 서브 트리를 모두 운행한 다음 근노드를 운행하고 우측 서브 트리를 운행하는 방법이다.

 

전위 운행(Preorder Traversal) :

<근, 좌측, 우측> 순서로 운행하는 방법으로 먼저 근노드를 운행하고 좌측 서브 트리를 운행한 다음 우측 서브 트리를 운행하는 방법이다.

 

후위 운행(Postorder Traversal) : 

<좌측, 우측, 근> 순서로 운행하는 방법으로 먼저 좌측 서브 트리를 운행하고 우측 서브 트리를 운행항 다음 마지막으로 근노드를 운행하는 방법이다.

 

폴리쉬 표기법(Polish Notation) ☆☆☆☆☆

우리가 수학식을 표기할 때는 중위식(Infix)으로 표기해 왔다. 이 표기법을 컴퓨터 명령어로 만들면 동작(연산자)이 가운데 있어 구성이 불편할 뿐 아니라 괄호가 있어 연산의 우선순위 부여도 어렵다. 따라서 전위식(Prefix)이나 후위식(Postfix)으로 바꾸어 사용하게 된다.

 

그래프(Graph)

그래프의 정의 및 용어

데이터 사이의 임의 관계가 비선형적으로 나타나는 구조를 말하는 것으로 최단거리 탐색, 연구 계획 분석, 공정 계획 분석, 전자 회로 분석, 통계학 등의 응용 분야에 쓰이고 있는 구조이다.

 

그래프의 표현

그래프 표현은 정점의 내용을 저장시키는 개념이 아니라 정점과 정점의 관계, 즉 간선의 관계를 표현하는데 목적이 있다.

 

그래프의 응용

신장 트리라는 것은 임의로 연결된 그래프 G(V,E)가 있을 때 이 그래프의 모든 정점을 통과하면서 사이클이 형성되지 않는 트리를 의미한다.

 

검색(Search)

내부 검색과 외부 검색으로 나누는데 내부 검색은 찾기 대상이 되는 자료 모두를 주 메모리에 놓고 검색하는 것을 말하고, 외부 검색은 찾기 대상이 되는 자료가 너무 많아 주 메모리에 모두 가져올 수 없는 경우 일부 자료를 주 기억장치에다 가져다놓고 검색하는 방식을 말함.

 

선형 검색(Linear Search) = 순차 검색(Sequential Search)

이 검색은 대상 자료를 순서대로 하나씩 비교해서 원하는 자료를 찾는 검색 방식이다.

 

선형 검색의 특징

1. 대상 자료의 범위를 몰라도 검색 가능하다.

2. 대상 자료가 정렬되어 있지 않아도 검색 가능하다.

3. 검색 속도가 다른 검색에 비해 느리다.

 

제어 검색

1. 대상 자료는 어떤 키 값에 따라서 정렬되어 있어야 한다.

2. 대상 자료에 대한 범위를 알고 있어야 한다.

 

이분 검색(Binary Search)

이분 검색은 찾고자 하는 값을 대상 자료의 중간 값과 비교하여 그 대상 범위를 축소시키면서 원하는 데이터를 검색하는 방식으로 위와 같이 정렬되어 있는 자료가 있을 때, C라는 자료를 찾고자 한다면 다음과 같은 방법으로 검색한다.

 

정렬(Sort)의 개념

정렬(Sort)이라는 것은 대상이 되는 자료를 어떤 키 값에 따라 오름차순이나 내림차순으로 재배치하는 것을 의미한다.

1. 오름차순(Ascending) : 키 값이 작은 것에서 큰 것 순으로 나열하는 것이다.

2. 내림차순(Descending) : 키 값이 큰것에서 작은 것 순으로 나열하는 것이다.

 

정렬 방식

내부 정렬

1. 삽입법(Insertion, Shell)

2. 교환법(Selection, Bubble, Quick)

3. 선택법(heap)

4. 병합법(2-Way Merge)

5. 분배법(Radix, Bucket)

 

외부 정렬

1. Balanced Merge Sort(균형 합병 정렬)

2. Cascade Merge Sort(계단식 합병 정렬)

3. Polyphase Merge Sort(다상 합병 정렬)

4. Osciliating Merge Sort(진동 합병 정렬)

 

삽입 정렬(Internal Sort)

대상 자료가 일부 정렬되어 있을 때 유리한 정렬 방식으로 선택(기준)된 키 값을 앞쪽 자료들의 키 값과 비교하여 자신의 위치를 찾아 삽입하여 정렬시키는 방식이다.

 

선택 정렬(Selection Sort)

전체 자료 중 작은(혹은 큰 것) 키 값을 찾아 선택(기준)된 위치의 자료와 교환하여 정렬하는 방식이다.

 

버블 정렬(Bubble Sort)

인접키와 비교하면서 교환하여 정렬하되 단계별로 수행하면서 각 단계 수행 중 교환이 일어나지 않으면 정렬이 완료된 것이므로 더 이상의 단계를 수행하지 않고 종료시켜 정렬을 완료시키는 방법이다.

 

퀵 정렬(Quick Sort)

첫 번째 데이터를 중간 값으로 설정하고 그 중간 값을 대상 자료 중 적당한 위치에 위치시켜 대상 자료를 부분적으로 나누어 가면서 되부름 방식으로 반복 분류시켜 정렬하는 방식이다. 따라서 이 정렬 방식은 이미 정렬되어 있는 자료를 정렬할 때는 최악의 경우가 되어 복잡도가 된다.

 

정렬 알고리즘 선택 시 고려사항

1. 초기 입력 자료의 배열 상태

2. 입력 자료의 양

3. 키 값들의 분포 상태

4. 소요 공간 및 작업 시간

5. 정렬에 필요한 기억 공간의 크기

6. 자료에 대한 액세스 빈도

 

정렬(Sort)의 개념

정렬(Sort)이라는 것은 대상이 되는 자료를 어떤 키 값에 따라 오름차순이나 내림차순으로 재배치하는 것을 의미한다.

오름차순(Ascending) : 키 값이 작은 것에서 큰 것 순으로 나열하는 것이다.

내림차순(Descending) : 키 값이 큰 것에서 작은 것 순으로 나열하는 것이다.

 

정렬방식

 

내부 정렬(Internal Sort)

정렬하고자 하는 자료를 주 메모리에 모두 가져다 놓고 정렬하는 방식으로, 자료의 양이 적을 때 사용하며 정렬 속도가 빠르다.

삽입법 : Insertion, Shell

교환법 : Selection, Bubble, Quick

선택법 : heap

병합법 : 2-Way Merge

분배법 : Radix, Bucket

 

삽입 정렬(Insertion Sort) ☆

대상 자료가 일부 정렬되어 있을 때 유리한 정렬 방식으로 선택(기준)된 키 값을 앞쪽 자료들의 키 값과 비교하여 자신의 위치를 찾아 삽입하여 정렬시키는 방식이다.

 

셸 정렬(Shell Sort)

매개 변수를 설정한 다음 데이터를 모아 매개 변수 간격만큼의 부파일을 만든 다음 그 매개변수의 간격을 감소시키면서 정렬하는 방식으로 삽입 정렬의 확장된 개념이다.

 

선택 정렬(Selection Sort) ☆

전체 자료 중 작은(혹은 큰 것) 키 값을 찾아 선택(기준)된 위치의 자료와 교환하여 정렬하는 방식이다.

 

버블 정렬(Bubble Sort) ☆

인접키와 비교하면서 교환하여 정렬하되 단계별로 수행하면서 각 단계 수행중 교환이 일어나지 않으면 정렬이 완료된 것이므로 더 이상의 단계를 수행하지 않고 종료시켜 정렬은 완료 시키는 방법이다.

 

퀵 정렬(Quick SorT)

첫 번째 데이터를 중간 값으로 설정하고 그 중간 값을 대상 자료 중 적당한 위치에 위치시켜 대상 자료를 부분적으로 나누어 가면서 되부름 방식으로 반복 분류시켜 정렬하는 방식이다. 따라서 이 정렬 방식은 이미 정렬되어 있는 자료를 정렬 할때는 최악의 경우가 되어 복잡도가 된다.

 

힙 정렬(Heap Sort)

완전 이진트리(Complete Binary Tree)인 오더드 트리(Ordered Tree)형태로 데이터를 저장하고 트리 액세스 알고리즘에 의해 부노드가 자노드보다 크게 되도록 구성하는데, 첫 번째 구성된 형태를 초기 Heap상태라고 한다. 이 초기 Heap상태에서 근노드를 맨 마지막으로 이동시켜 대상 개수를 하나씩 줄여가면서 정렬하는 방식이다.

 

이진 병합 정렬(2-Way Merge Sort)

두 개의 키들을 한 쌍으로 하여 각 쌍에 대하여 순서를 정하고 나서 순서대로 정렬된 각 쌍의 키들을 병합하여 하나의 정렬된 서브 리스트로 만들어 최종적으로 하나의 정렬된 파일이 될때까지 반복하여 정렬하는 방식이다.

 

버킷 정렬(Bucket Sort) 

기수 정렬(Radix Sort), 버킷 정렬(Bucket Sort)은 정렬한 데이터의 기수 값에 따라 분배하여 정렬하는 방식으로 여분의 기억 공간이 많이 필요하다.

 

 

 

외부정렬

정렬하고자 하는 자료를 보조 기억 공간에 두고 일부분씩 주 메모리로 가져가 병합하여 정렬하는 방식으로, 자료의 양이 많을 때 사용한다.

Balanced Merge Sort(균형 합병 정렬)

Casecade Merge Sort(계단식 합병 정렬)

Polyphase Merge Sort(다상 합병 정렬)

Oscillating Merge Sort(진동 합병 정렬)

정렬 알고리즘 선택 시 고려사항

초기 입력 자료의 배열 상태

입력 자료의 양

키 값들의 분포 상태

소요 공간 및 작업 시간

정렬에 필요한 기억 공간의 크기

자료에 대한 액세스 빈도

 

해싱

해싱이란 어떤 다른 레코드의 참조 없이 어떤 키 변환에 의하여 원하는 레코드에 직접 접근할 수 있도록 구성하는 것을 의미한다.

 

해싱의 특징(Hashing)

평균 조사(Probe)횟수가 작다.

최악의 경우에도 조사 횟수의 상한(Upper Bound)이 낮으므로 Realtime 응용에 적합하다.

컴파일러의 Symbol Table 처리에 이용된다.

레코드를 식별하는 키 값과 물리적 저장 장치에 있는 레코드의 주소 사이에 어떤 관계성이 있어야 한다.

물리적 주소 산출 시 계산에 의해 산출하므로 주소 산출 시간이 오래 걸린다.

기억 장소의 낭비가 심하다.

주소 값이 같은 경우 오버플로 처리가 쉽지 않다.

 

해싱에서 사용하는 용어

해싱 함수(Hashing Function) : 레코드의 키 값을 이용해서 레코드를 저장할 주소를 산출해내는 일종의 수학식이다.

홈 주소(Home Address) : 해싱 함수에 의해 계산되어 나온 주소 값이다.

버킷(Bucket) : 하나의 주소를 가지면서 한개 이상의 레코드를 저장할 수 있는 공간이다.

슬롯(Slot) : 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷을 형성한다.

충돌(Collision) : 해싱 함수에 의해서 계산된 홈 주소가 같은 경우에 벌어지는 충돌 현상이다.

시노님(Synonyms) : 같은 홈 주소를 갖는 레코드의 집합이다.

오버플로(Overflow) : 해당 버킷에 더 이상의 레코드를 기억시킬 수 없어서 넘쳐나는 현상이다.

 

해싱 함수(Hashing Function)

해싱함수는 모든 버킷에 같은 수의 데이터가 들어갈 수 있도록 수학식을 구성해야 한다.

 

제산법(Division Method) :

레코드의 키 값을 임의의 소수로 나누어 그 나머지 값을 홈 주소로 이용하는 방법이다.

 

기수 변환법(Radix Conversion Method) :

레코드의 키 값을 임의의 다른 기수 값으로 변환하여 그 값을 홈 주소로 이용하는 방법이다.

 

접는법(Folding Method) :

레코드의 키 값을 여러 부분으로 나누고, 각 부분의 값을 더하거나 배타적 논리합(XOR : eXclusive OR) 연산을 통하여 나온 결과로 주소를 취하는 방법이다.

 

계수 분석법(Digit Analysis Method) :

주어진 모든 키 값들에서 그 키를 구성하는 자릿수들의 분포를 조사하여 비교적 고른 분포를 보이는 자릿수들을 필요한 만큼 택하는 방법이다.

 

제곱법(Mid-Square Method) :

값을 제곱하여, 결과 값 중 중간 자릿수를 선택하여 그 값을 홈 주소로 이용하는 방법이다.

 

파일구조의 기본

1) 파일 구조 결정 시 고려사항

파일 저장에 사용될 매체의 특성을 고려한다.

매체의 접근(Access) 형태를 고려한다.

자료의 처리 방식 및 주기를 고려한다.

파일의 연산 유형을 고려한다.

사용자의 응답 시간을 고려한다.

파일의 활동률 = 전체 레코드 수 / 실제 사용되는 레코드 수 를 고려한다.

 

순차 파일(SAM : Sequentail Access Method File)

입력되는 데이터의 논리적인 순서에 따라 물리적으로 연속된 위치에 기록된 파일이다.

 

장점

1. 기록 밀도다 좋다. / 2. 어떤 매체라도 용이하게 사용할 수 있다. / 3. 액세스 속도가 빠르며 비용이 저렴하다. / 4. 일괄 처리에 적합하다

 

단점

1. 파일 내에 새로운 레코드를 삽입하거나 삭제할 때 자료 이동이 많이 일어난다.

2. 검색할 때 순차 검색을 하여야 하기 때문에 검색 효율이 떨어진다.

 

색인 순차 파일(ISAM : Indexed Sequential Access Method File)

데이터를 논리적 순차에 따라 물리적 연속으로 구성하고 이 데이터에 대한 색인을 구성하여 색인을 통한 랜덤 처리와 데이터에 대한 순차 처리를 병핼할 수 있게 편성한 파일이다.

 

인덱스 구역(Index Area)

기본 데이터 영역에 대한 색인을 구성하는 부분으로 트랙 색인, 실린더 색인, 마스터 색인으로 구분하여 구성한다.

트랙색인 - 소 제목 / 실린더 색인 - 중 제목 / 마스터 색인 - 대 제목

 

직접 파일(DAM : Direct Access Method File)

레코드 내의 키 필드를 해싱 함수에 의해 물리적 저장 장치의 주소로 변화하여 레코드를 기록하는 방식으로 파일 내에서 일정한 순서 없이 임의 처리를 하고자 할 때 사용한다.