5장 자료 구조의 기본

정보처리기사 필기 - 1과목 데이터베이스

5장 자료 구조의 기본

030 자료 구조의 개념

① 자료 구조의 정의

- 효율적인 프로그램을 작성할 때 가장 우선적인 고려사항은 저장공간의 효율성과 실행시간의 신속성

- 자료구조는 프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법과 저장된 그룹 내에 존재하는 자료 간의 관계, 처리 방법 등을 연구 분석하는 것

· 자료 구조는 자료의 표현과 그것과 관련된 연산

· 자료 구조는 일련의 자료들을 조직하고 구조화하는 것

· 어떠한 자료 구조에서도 필요한 모든 연산들을 처리하는 것이 가능

· 자료 구조에 따라 프로그램 실행시간이 달라짐

② 자료 구조의 분류

[그림 1] 자료 구조 분류

③ 자료 구조의 이용

· 정렬(Sort) : 기억장치 내의 자료를 일정한 순서에 의해 나열하는 것

· 검색(Search) : 기억장치 내의 자료를 찾는 것 

· 파일 편성 : 자료를 기억 매체에 저장할 때의 파일 구조

· 인덱스 : 파일에서 특정 자료를 빠르게 찾기 위한 색인표

031 리스트

① 선형 리스트(Linear List)

· 선형 리스트는 배열과 같이 연속되는 기억장소에 저장되는 리스트

· 연접 리스트 또는 축자구조라고도 함

· 선형 리스트의 대표적인 구조 : 배열(Array)

특징

· 가장 간단한 자료 구조

· 접근 속도 빠름

· 중간에 자료를 삽입하기 위해서는 연속된 빈 공간 있어야 함

· 기억장소를 연속적으로 배정받기 때문에 기억장소 이용 효율은 밀도가 1로서 가장 좋음

· 자료의 개수가 n개일 때 삽입 시의 평균 이동 횟수는 (n+1)/2이고, 삭제 시에는 (n-1)/2

· 삽입, 삭제 시 자료의 이동이 필요하기 때문에 작업이 번거로움

② 연결 리스트(Linked List)

연결 리스트는 자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조

연결 리스트의 특징

· 노드의 삽입, 삭제 작업이 용이

· 기억공간이 연속적으로 놓여 있지 않아도 저장이 가능

· 연결을 위한 링크(포인터)부분이 필요하기 때문에 순차 리스트에 비해 기억공간 이용 효율이 좋지 않음

· 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도 느림

· 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘듦

· 희소 행렬을 링크드 리스트로 표현하면 기억장소가 절약됨

· 트리를 표현할 때 가장 적합한 자료 구조

※ 노드(Node)

Data 부분

Link 부분

자료를 저장하는 데이터 부분과 다음 노드를 가리키는 포인터인 링크 부분으로 구성된 기억공간

※ 포인터(Pointer)

현재의 위치에서 다음 노드의 위치를 알려주는 요소

· 프런트 포인터 : 리스트를 구성하는 최초의 노드 위치를 가리키는 요소

· 널 포인터 : 0또는 ∧, ＼0으로 표시하며, 마지막 노드의 링크 부분에 일반적으로 사용하는 것으로, 다음 노드가 없음을 나타내는 포인터

※ 희소 행렬

희소 행렬은 행렬의 요소 중 많은 항들이 0으로 되어 있는 형태로, 기억장소를 절약하기 위해 링크드 리스트를 이용하여 저장

연결 리스트의 종류

· 단순 연결 리스트

· 단순 환상 연결 리스트

· 이중 연결 리스트

· 이중 환상 연결 리스트

032 스택(Stack)

① 스택의 개념

· 스택은 리스트 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조

· 스택은 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO; Last In First Out) 방식으로 자료 처리

· TOP

- Stack으로 할당된 기억공간에서 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소

- 스택 포인터(SP, Stack Pointer)라고도 함

·Bottom : 스택의 가장 밑바닥

② 자료의 삽입(Push)

Top = Top +1  If Top > M Then Overflow  Else X(Top) ← Item

스택 포인터(Top)를 1 증가시킴  스택 포인터가 스택의 크기보다 크면 Overflow    그렇지 않으면 Item이 가지고 있는 값을 스택의  Top위치에 삽입

· M : 스택의 크기

· Top : 스택 포인터

· X : 스택의 이름

· Overflow : 스택으로 할당받은 메모리 부분의 마지막 주소가 M번지라고 할 때, Top Pointer의 값이 M보다 커지만 스택의 모든 기억장소가 꽉 채워져 있는 상태이므로 더 이상 자료를 삽입할 수 없어 Overflow 발생시킴

③ 자료의 삭제(Pop Up)

If Top = 0 Then Underflow  Else Item ← X(Top) Top = Top - 1

스택 포인터가 0이면 스택의 바닥이므로 더 이상 삭제할 자료가 없으므로  Underflow를 처리함  그렇지 않으면  Top 위치에 있는 값을 Item으로 옮기고  스택 포인터를 1 감소시킴

※ Stack에 기억되어 있는 자료를 삭제시킬 때는 제일 먼저 삭제할 자료가 있는지 앖는지부터 확인해야 함

· Underflow : Top Pointer가 주소 0을 가지고 있다면 스택에는 삭제할 자료가 없으므로 Underflow를 발생시킴

※ Overflow : 꽉 채워져 있는 상태로 더 이상 자료를 삽입할 수 없는 상태

   Underflow : 자료가 없어서 자료를 제거할 수 없는 상태

④ Stack의 응용 분야

· 부 프로그램 호출 시 복귀주소를 저장할 때

· 함수 호출의 순서 제어

· 인터럽트가 발생하여 복귀주소를 저장할 때

· 후위 표기법(Postfix Notation)으로 표현된 수식을 연산할 때

· 0 주소지정방식 명령어의 자료 저장소

· 재귀(Recursive) 프로그램의 순서 제어

· 컴파일러를 이용한 언어 변역 시

033 큐(Queue)와 데크(Deque)

① 큐(Queue)

· 선형 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료 구조

· 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO; First In First Out) 방식으로 처리

· 시작과 끝을 표시하는 두 개의 포인터 있음

· 프런트(F, Front) 포인터

- 가장 먼저 삽입된 자료의 기억 공간을 가리키는 포인터

- 삭제 작업할 때 사용

· 리어(R, Rear) 포인터

- 가장 마지막에 삽입된 자료가 위치한 기억장소를 가리키는 포인터

- 삽입 작업할 때 사용

· Queue의 응용분야

- 청구 업무나 택시 정거장처럼 서비스 순서를 기다리는 등의 대기 행렬의 처리에 사용

- 운영체제의 작업 스케줄리에 사용

② 데크(Deque)

· 삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료 구조

· Double Ended Queue

· Stack과 Queue의 장점만 따서 구성한 것

· 입력이 한쪽에서만 발생하고 출력은 양쪽에서 일어날 수 있는 입력 제한과, 입력은 양쪽에서 일어나고 출력은 한 곳에서만 이루어지는 출련 제한있음

· 입력 제한 데크 : Scroll

· 출력 제한 데크 : Shelf

034 트리(Tree)

① 트리의 정의

· 트리는 정점(노드)과 선분을 이용하여 사이클을 이루지 않도록 구성한 Graph의 특수한 형태

· 가족 계보(족보), 연산 수식, 회사 조직 구조도, 히프(Heap) 등을 표현하기에 적합

② 트리 관련 용어

[그림 2] 트리

· 노드(Node) : 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지를 합친 것

· 근 노드(Root Node) : 트리의 맨 위에 있는 노드

· 디그리(Degree) : 각 노드에서 뻗어나온 가지의 수

· 단말 노드(Terminal Node) = 잎 노드(Leaf Node) : 자식이 하나도 없는 노드, 즉 Degree가 0인 노드

· 비단말 노드(Non-Terminal Node) :자식이 하나라도 있는 노드, 즉 Degree가 0이 아닌 노드

· 조상 노드(Ancestors Node) : 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들

· 자식 노드(Son Node) : 어떤 노드에 연결된 다음 레벨의 노드

· 부모 노드(Parent Node) : 어떤 노드 연결된 이전 레벨의 노드

· 형제 노드(Brother Node, Sibling) : 동일한 부모를 갖는 노드들

· Level : 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1

· 깊이(Depth, Height) : Tree에서 노드가 가질 수 있는 최대의 레벨

· 숲(Forest) : 여러 개의 트리가 모여 있는 것

· 트리의 디그리 : 노드들의 디그리 중에서 가장 많은 수

035 이진 트리

이진 트리는 차수(Degree)가 2 이하인 노드들로 구성된 트리, 즉 자식이 둘 이하인 노드들로만 구성된 트리

① 이진트리의 특성

· 이진 트리의 레벨 i에서 최대 노드의 수 :  2n-1

· 이진 트리에서 Terminal Node수가 n0, 차수가 2인 노드 수가 n2라 할 때 n0= n2 + 1

② 이진 트리의 종류

정이진 트리(Full Binary Tree)

- 정이진 트리는 깊이(Depth)가 k일 때 전체 노드의 수가 2k-1개의 노드이고, 레벨 i마다 2i-1개의 노드들로 꽉 찬 트리를 말함

전이진 트리(Complete Binary Tree)

· 전이진 트리는 노드의 개수가 n개일 때, 정이진 트리의 각 노드에 붙인 1~n의 일련번호와 1:1 대응되는 트리를 말함

· 중간에 빈 부분이 있으면 전이진 트리 될 수 없음

사향 이진 트리(Skewed Binary Tree)

· 사향 이진 트리는 루트 노드로부터 왼쪽 또는 오른쪽으로만 기울어진 트리, 즉 왼쪽 또는 오른쪽 자식이 없는 노드들로만 구성된 트리를 말함

· 왼쪽 사향 이진 트리 : 오른쪽 자식이 없는 노드들로만 구성된 트리

· 오른쪽 사향 이진 트리 : 왼쪽 자식이 없는 노드들로만 구성된 트리

036 이진 트리의 운행법(Traversal)

· 트리를 구성하는 각 노드들을 찾아가는 방법 :  운행법

· 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성 가짐

① 트리의 운행법

· Preorder 운행 : Root → Left → Right 순으로 운행

· Inorder 운행 : Left → Root → Right 순으로 운행

· Postorder 운행 : Left → Right → Root 순으로 운행

② 수식의 표기법

산술식을 계산하기 위해 기억공간에 기억시키는 방법으로 이진 트리를 많이 사용함

이진 트리로 만들어진 수식을 인오더, 프리오더, 포스트오더로 운행하면 각각 중위(Infix), 전위(Prefix), 후위(Postfix) 표기법이 됨

· 전위 표기법(PreFix) : 연산자 → Left → Right, +AB

· 중위 표기법(InFix) : Left → 연산자 → Right, A+B

· 후위 표기법(PostFix) : Left → Right → 연산자, AB+

Infix 표기를 Postfix나 Prefix로 바꾸기

· Postfix나 Prefix는 스택을 이용하여 처리하므로 Infix는 Postfix나 Prefix로 바꾸어 처리

Postfix나 Prefix로 표기된 수식을 Infix로 바꾸기

· Postfix는 Infix 표기법에서 연산자를 해당 피연산자 두 개의 뒤로 이동한 것이므로 연산자를 다시 해당 피연산자 두 개의 가운데로 옮기면 됨

· Prefix는 Infix 표기법에서 연산자를 해당 피연산자 두 개의 앞으로 이동한 것이므로 연산자를 다시 해당 피연산자 두 개의 가운데로 옮기면 됨

③ 스레드 이진 트리(Threaded Binary Tree)

· 스레드 이진 트리는 이진 트리에서 발생하는 널 링크를 트리 운행에 필요한 다른 노드의 포인터로 사용하도록 고안된 트리

· 이진 트리를 이중 연결 리스트로 표현할 때 임의의 노드에 대한 자식 노드가 없는 부분의 링크 포인터로 Nil Pointer를 기억시키게 됨

· 스레드 이진 트리 표현 방법

- 어떤 노드의 왼쪽 링크 포인터가 Nil이면 그 노드의 직전에 검사된 노드를 가리키는 포인터로 사용하고, 오른쪽 링크 포인터가 Nil이면 그 노드의 직후에 검사될 노드를 가리키는 포인터로 사용

- 해당 노드의 직전, 직후 노드는 트리 운행법에 따라 방문한 노드의 순서대로 결정

037 그래프

① 그래프의 정의

· 그래프 G는 정점 V와 간선 E의 두 집합으로 이루어짐

· 통신망(Network), 교통망, 이항관계, 연립방정식, 유기화학 구조식, 무향선분 해법등에 응용됨

· Tree는 사이클이 없는 Graph

② 용어 정리

Loop : 한 정점에서 그 자신에 이어지는 간선 Loop

차수(Degree)

· 무방향 그래프 : 한 정점에 연결된 간선의 수

· 방향 그래프

- 진입 차수(Indegree) : 한 정점에 도착하는 방향 간선의 수

- 진출 차수(Outdegree) : 한 정점에서 출발하는 방향 간선의 수

- 차수(Degree) : 진입 차수 + 진출 차수

경로 : 임의의 정점에서 다른 정점으로 이르는 길

· 경로 길이(Path Length) : 경로상에 있는 간선들의 수

· 단순 경로 : 한 경로상에 있는 모든 간선이 서로 다를 떄의 경로, 즉 같은 간선을 두 번 이상 지나지 않는 경로

· 기본 경로 : 한 경로상에 있는 모든 정점이 유일할 때의 경로, 즉 같은 정점을 두 번 이상 지나지 않는 경로

· 사이클 : 같은 정점에서 시작과 끝이 이루어지는 경로

· 최대 사이클 : 사이클을 이루는 경로 중 최대 경로 길이

연결 요소 : 무방향 그래프에서의 최대 연결 서브 그래프

강력 연결 요소 : 방향 그래프에서 두 정점 사이의 간선이 양방향으로 서로 강력하게 연결되어 있는 요소, 즉 두 정점 사이에 방향 사이클이 이루어지는 요소

③ 인접행렬을 이용한 그래프의 표현 방법

④ 특수 그래프

최소 비용 신장 트리

· 최소 비용 신장 트리는 가중치가 가장 작은 간선들을 사이클을 이루지 않도록 연결시켜 만든 그래프

간선 작업 네트워크

· 간선 작업 네트워크는 프로젝트를 해결하기 위해 수행되는 작업 순서를 나타내는 방향 그래프

· 간선은 작업과 작업시간을 나타내고, 정점이 공정을 나타냄

· 임계 경로 : 최장 길이를 갖는 경로

038 정렬(Sort)의 개요

정렬은 파일을 구성하는 각 레코드를 특정 키 항목을 기준으로 오름차순 또는 내림차순으로 재배열하는 작엄

① 정렬 방식

    정렬은 크게 주기억장치에서 이루어지는 내부 정렬과 보조기억장치에서 이루어지는 외부 정렬로 구분됨

내부정렬

· 선택법 : 히프 정렬

· 삽입법 : 삽입 정렬, 쉘 정렬

· 교환법 : 버블 정렬, 선택 정렬, 퀵 정렬

· 병합법(합병법) : 2-Way Merge Sort

· 분배법(분산법) : 기수 정렬(Radix Sort)

외부 정렬

· 밸런스 병합 정렬

· 캐스케이드 병합 정렬

· 폴리파즈 병합 정렬

· 오실레이팅 병합 정렬

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

· 데이터의 양

· 초기 데이터의 배열 상태

· 키 값들의 분포 상태

· 소용공간 및 작업 시간

· 사용 컴퓨터 시스템의 특성

039 내부 정렬

① 삽입 정렬(Insert Sort)

삽입 정렬은 가장 간단한 정렬 방식으로 이미 순서화된 파이렝 샐운 하나의 레코드를 순서에 맞게 삽입시켜 정렬

· 두 번째 키와 첫 번째 키를 비교해 순서대로 나열(1회전)하고, 이어서 세 번째 키를 첫 번째, 두 번째 키와 비교해 순서대로 나열(2회전)하고, 계속해서 n번째 키를 앞의 n-1개의 키와 비교하여 알맞은 순서에 삽입하여 정렬하는 방식

② 쉘 정렬(Shell Sort)

쉘 정렬은 삽입 정렬을 확장한 개념

· 입력 파일을 어떤 매개변수(h)의 값으로 서브파일을 구성하고, 각 서브파일을 Insertion 정렬 방식으로 순서 배열하는 과정을 반복하는 정렬 방식, 즉 임의의 레코드 키와 h만큼 떨어진 곳의 레코드를 비교하여 순서화되어 있지 않으면 서로 교환하는 것을 반복하는 정렬 방식

· 입력 파일이 부분적으로 정렬되어 있는 경우에 유리한 방식

③ 선택 정렬(Selection Sort)

선택 정렬은 n개의 레코드 중에서 최소값을 찾아 첫 번재 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식

④ 버블 정렬(Bubble Sort)

· 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식

· 계속 정렬 여부를 플래그 비트(f)로 결정

⑤ 퀵 정렬(Quick Sort)

퀵 정렬은 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법으로 키를 기준으로 작은 값은 왼쪽에, 큰 값은 오른쪽 서브파일로 분해시키는 방식

· 정렬 방식 중에서 가장 빠른 방식이며, 프로그램에서 되부름을 이용하기 때문에 스택(Stack) 필요

⑥ 힙 정렬(Heap Sort)

힙 정렬은 전이진 트리를 이용한 정렬 방식

· 구성된 전이진 트리를 Heap Tree로 변환하여 정렬

⑦ 2-Way 합병 정렬(Merge Sort)

2-Way Merge Sort는 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬방식

· 두 개의 키들을 한 쌍으로 하여 각 싸엥 대하여 순서 정함

· 순서대로 정렬된 각 쌍의 키들을 합병하여 하나의 정렬된 서브리스트로 만듦

· 위 과정에서 정렬된 서브리스트들을 하나의 정렬된 파일이 될 때가지 반복

⑧ 기수 정렬(Radix Sort) = Bucket Sort

기수 정렬은 Queue를 이용하여 자릿수별로 정렬하는 방식

· 레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬

040 검색(Search)

검색은 컴퓨터를 이용해서 기억공간에 보관중인 특정 레코드를 찾아내는 작업

① 선형 검색(Linear Search)

·  선형 검색은 순서화되어 있지 않은 파일에서 순차적으로 검색하는 방식으로, 찾고자 하는 Key 값을 첫 번재 레코드 Key 값부터 차례로 비교하여 검색하는 방식

· 순차 검색

· 프로그램 작성이 가장 쉬움

② 제어 검색(Control Search)

· 제어 검색은 반드시 순서화된 파일이어야 검색 가능

· 한 번의 비교 동작이 끝난 후 비교 대상이 된 레코드를 다음에 비교할 대상을 선택하는 기준으로 이용하여 검색하는 방식

이분 검색(이진 검색, Binary Search)

· 이분 검색은 전체 파일을 두 개의 서브파일로 분리해 가면서 Key 레코드를 검색하는 방식

· 찾고자 하는 Key 값을 파일의 중간 레코드 Key 값과 비교하면서 검색하는 방식

· 비교 회수를 거듭할 대마다 검색 대상이 되는 데이터 수가 절반으로 줄어듦으로 탐색 효율이 좋고 탐색 시간이 적게 소요됨

· 중간 레코드 번호 M=(F+L)/2(단, F:첫 번째 레코드 번호, L:마지막 레코드 번호)

피보나치 검색(Fibonacci Search)

· 피보나치 검색은 피보나치 수열에 따라 다음에 비교할 대상을 선정하여 검색하는 방식

· 이분 검색에는 중간 레코드 번호를 계산하기 위해서 나눗셈이 필요하지만 피보나치 검색은 가감산만을 이용하기 때문에 효율이 우수

보간 검색(Interpolation Search)

· 보간 검색은 찾으려는 레코드가 있음직한 부분의 키를 택하여 거맥하는 방식

· 선정 레코드 번호 = (찾으려는 키 값(추측)-최소키 값) / (최대키 값 - 최소키 값) × 레코드 수

· 찾으려는 레코드 근처에서부터 찾아가기 때문에 검색시간이 빠르지만, 예측을 해야하므로 실제로는 프로그래밍이 불가능함

블록 검색(Block Search)

· 블록 검색을 위해서는 파일을 구성하는 레코드들을 다음과 같이 구성해 놓아야 함

-파일을 구성하는 레코드들을 여러 개의 Block으로 분할하여 Block 단위는 순서화시키고, Block 내의 자료는 순서화와 관계없이 저장시킴

- Index 부분을 두어, 각 Block마다 최대 레코드 키 값을 가지는 레코드 번호를 저장시킴

· 인덱스를 이용하여 찾고자 하는 레코드가 어느 Block에 속하는지 검색한 후, 해당 Block 내에서는 선형 검색을 함

이진 트리 검색(Binary Tree Search)

· 이진 트리 검색은 파일을 이진 검색 트리로 구성하여 검색하는 방식

· 검색 과정

① 찾고자 하는 레코드 Key 값 X가 이진 검색 트리에 존재하는지 조사하려면 먼저 Root Node와 비교

② 만약 X가 Root Node의 Key 값보다 작으면 왼쪽 Subtree로 검색을 계속하고, 크면 오른쪽 Subtree로 검색을 계속하고, 같으면 검색종료

③ i가 0인 경우 검색에 실패한 경우. 즉, X가 임의의 노드 값과 같지 않아서 왼쪽 또는 오른쪽 자식을 찾아가기 위해 그 노드의 L.L 또는 R.L 포인터를 i에 기억시켰을 때, i에 기억시킨 포인터 값이 Nill Pointer인 경우 찾고자 하는 레코드가 없기 대문

041 검색 - 해싱(Hashing)

① 해싱의 개요

해싱은 Hash Table이라는 기억공간을 할당하고, 해시 함수를 이용하여 레코드 키에 대한 Hash Table 내의 Home Address를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행하는 방식

· 해싱은 DAM(직접 접근) 파일을 구성할 때 사용되며, 접근 속도는 빠르나 기억공간이 많이 요구됨

· 다른 방식에 비해 검색 속도가 가장 빠름

· 삽입, 삭제 작업의 빈도가 많을 때 유리한 방식

· 키-주소 변환 방법이라고도 부름

해시 테이블(Hash Table, 해시표)

· 해시 테이블은 레코드를 한 개 이상 보관할 수 있는 Bucket들로 구성된 기억공간으로, 보조기억장치에 구성할 수도 있고 주기억장치에 구성할 수도 있음

[그림 3] 해시 테이블  * n크기의 3개의 슬롯으로 구성된 버킷을 가진 해시표

· 버킷(Bucket) : 하나의 주소를 갖는 파일의 한 구역을 의미하며, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수

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

· Collision(충돌 현상) : 서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상

· Synonym : 충돌로 인해 같은 Home Address를 갖는 레코드들의 집합

· Overflow : 계산된 Home Address의 Bucket 내에 저장할 기억공간이 없는 상태로, Bucket을 구성하는 Slot이 여러 개일 때 Collision은 발생해도 Overflow는 발생하지 않을 수 있음

② 해싱 함수(Hashing Function)

제산법

제산(Division)법은 레코드 키(K)를 해시표의 크기보다 큰 수 중에서 가장 작은 소수(Prime, Q)로 나눈 나머지를 홈 주소로 삼는 방식

h(K) = K mod Q

제곱법

제곱(Mid-Square)법은 레코드 키 값(K)을 제곱한 후 그 중간 부분의 값을 홈 주소로 삼는 방식

폴딩법

폴딩(Folding)법은 레코드 키 값(K)을 여러 부분으로 나눈 후 각 부분의 값을 더하거나 XOR(배타적 논리합)한 값을 홈 주소로 삼는 방식

· Shift Folding : 각 부분의 값들을 왼쪽 또는 오른쪽 끝자리에 맞추어서 계산

· Fold Boundary : 경계 지점을 접었을 때 마주치는 자리 그대로 계산

기수(Radix) 변환법

기수 변환법은 키 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수는 절단하고, 이를 다시 주소 범위에 맞게 조정하는 방법

대수적 코딩법

대수적 코딩법은 키 값을 이루고 있는 각 자리의 비트 수를 한 다항식의 계수로 간주하고, 이 다항식을 해시표의 크기에 의해 정의된 다항식으로 나누어 얻은 나머지 다항식의 계수를 홈 주소로 삼는 방식

계수 분석법(숫자 분석법)

계수 분석법은 키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방식

무작위법

무작위법은 난수를 발생시켜 나온 값을 홈 주소로 삼는 방식

③ Overflow 해결 방법

Collision이 발생했을 때 그 버킷에 저장할 Slot이 없으면 Overflow가 되는데, 이것을 해결하기 위해서는 다음과 같은 방법 필요

개방 주소법(Open Addressing)

선형 방법이락도 하는데, Collision이 발생했을 때 순차적으로 그 다음 빈 버킷을 찾아 저장하는 방법

폐쇄 주소법(Close Addressing)

Overflow된 레코드들을 별도의 Overflow 영역에 저장하고 Chain(Pointer)으로 홈 버킷에 연결

· Direct Chaining : 해시표 내의 빈 자리에 Overflow 레코드 보관

· Indirect Chaining : 해시표와는 별도의 기억공간에 Overflow 레코드 보관

재해싱(Rehashing)

Collision이 발생하면 새로운 해싱 함수로 새로운 홈 주소를 구하는 방식 

042 인덱스 구조

① 인덱스의 개념

인덱스는 데이터 레코드를 빠르게 접근하기 위해서 구성하는 것으로 다음과 같은 특징이 있음

· 인덱스는 데이터가 저장된 물리적 구조와 밀접한 관계가 있음

· 인덱스는 레코드가 저장된 물리적 구조에 접근하는 방법을 제공

· 인덱스를 통해서 파일의 레코드에 대한 액세스를 빠르게 수행 가능

· 레코드의 삽입과 삭제가 수시로 일어나는 경우에는 인덱스의 개수를 최소로 하는 것이 효율적

② m-원 검색 트리(m-Way Search Tree)

· 이진 검색 트리에서는 한 노드가 한 개의 키와 두 개의 Subtree를 갖는 반면 m 원 검색 트리는 한 노드가 최대 m-1개의 키와 m개의 Subtree를 갖도록 구성됨

· m-원 트리 구조는 키 값의 일부분이 동일한 문자열이나 숫자로 구성된 자료를 표현하는 데 효율적

· 이진 검색 트리에 비해 트리 높이가 얕아져 특정 노드의 검색시간 감소

· 삽입, 삭제시 트리 균형을 유지하기 위항 복잡한 연산이 필요해지는 단점이 있음

③ B-트리

B-트리는 Index를 구성하는 방법으로 가장 많이 사용하는 균형된 m원 검색 트리

B-트리의 특징

· Root와 Leaf를 제외한 모든 노드는 최소 m/2, 최대 m개인 Subtree를 갖음

· Root는 Leaf가 아닌 이상 적어도 두 개의 Subtree를 가짐

· 모든 Leaf는 같은 Level에 있음

· Leaf가 아닌 노드의 키 값 수는 그 노드의 Subtree 수보다 한 개 적으며, 각 Leaf Node수는 최소 m/2-1개, 최대 m-1개의 키 값들을 갖음

· 한 노드 안에 있는 키 값들은 오름차순을 유지해야 함

· 탐색, 추가, 삭제는 루트로부터 시작함

· 삽입과 삭제를 하여도 데이터 구조의 균형을 유지해야 함

④ B+-트리

B+-트리는 B 트리의 변형으로 Leaf가 아닌 노드로 된 인덱스 세트와 리프 노드로만 구성된 순차 데이터 세트로 구성

· 인덱스 세트에 있는 키 값을 리프 노드에 있는 키 값을 찾아갈 수 있는 경로로만 제공됨

· 인덱스 세트에 있는 모든 키 값이 리프 노드에 다시 나타나므로 리프 노드만을 이용한 순차 처리가 가능

· B+-트리는 B-트리의 추가, 삭제 시 발생하는 노드의 분열과 합병 연산 과정을 줄일 수 있는 트리 구조

B+-트리의 특징

· 0, 2 또는 m/2에서 m개 사이의 Subtree를 갖음

· Root와 Leaf를 제외한 모든 노드는 최소 m/2, 최대 m개인 Subtree를 갖음

· 모든 Leaf는 같은 Level에 있음

· Leaf가 아닌 노드의 키 값 수는 그 노드의 Subtree 수보다 한 개 적으며, 각 Leaf Node수는 최소 m/2-1개, 최대 m-1개의 키 값들을 갖음

· 한 노드 안에 있는 키 값들은 오름차순을 유지해야 하며 리스트로 연결된 리프 노드는 데이터 파일의 순차 세트를 나타냄

⑤ 트라이(Tri) 색인

트라이 색인은 탐색을 위한 키 값을 직접 표현하지 않고 키를 구성하는 문자나 숫자 자체의 순서로 키 값을 구성하는 구조

· 키 값이 문자열 또는 숫자일 경우 일련의 키 값드렝 대해 일부분이 같은 문자나 숫자로 구성되었을 때 적합

· 가변 길이의 키 값을 효과적으로 나타낼 수 있음

· 삽입 및 삭제 시 노드의 분열과 병합이 없음

· 트라이의 차수는 키 값을 표현하기 위해 사용하는 문자의 수에 의해 결정됨

· 키 값의 분포를 미리 예측할 수 있다면 기억장소 절약 가능

· 트라이의 크기는 나타내려고 하는 키 값의 기수와 키 필드 길이에 의해 결정됨

043 파일 편성

① 순차 파일(Sequential File) = 순서 파일

순차 파일은 입력되는 데이터들을 논리적인 순서에 따라 물리적 연속 공간에 순차적으로 기록하는 방식

· 급여 관리 등과 같이 변동 사항이 크지 않고 기간별로 일괄 처리르 주로 하는 경우에 적합

· 주로 순차 접근이 가능한 자기 테이프에서 사용

순차 파일의 장점

· 기록 밀도가 높아 기억공간을 효율적으로 사용 가능

· 매체 변환이 쉬워 어떠한 매체에도 적용 가능

· 레코드가 키 순서대로 편성되어 취급이 용이

· 레코드를 기록할 때 사용한 키 순서대로 레코드를 처리하는 경우, 다른 편성법보다 처리 속도가 빠름

순차 파일의 단점

· 파일에 새로운 레코드를 삽입하거나 삭제하는 경우 파일 재구성을 위해 전체를 복사해야 하므로 시간이 많이 소요됨

· 데이터 검색 시 처음부터 순차적으로 검색하기 때문에 검색 효율이 낮고, 시간 및 응답 시간이 느림

② 색인 순차 파일(Indexed Sequential File)

색인 순차 파일은 순차 처리와 랜덤 처리가 모두 가능핟록 레코드들을 키 값 순으로 정렬시켜 기록하고, 레코드의 키 항목만을 모은 색인을 구성하여 편성하는 방식

· 색인을 이용한 순차적인 접근 방법을 제공하여 ISAM이라고 함

· 레코드를 참조할 때 색인을 탐색한 후 색인이 가리키는 포인터(주소)를 사용하여 직접 참조할 수 있음

· 일반적으로 자기 디스크에 많이 사용되며, 자기 테이프에서는 사용할 수 없음

색인 순차 파일의 구성

색인 순차 파일은 기본 구역, 색인 구역, 오버플로 구역으로 구성됨

· 기본 구역(Prime Area) : 실제 레코드들을 기록하는 부분으로 각 레코드는 키 값순으로 저장됨

· 색인 구역(Index Area) : 기본 구역에 있는 레코드들의 위치를 찾아가는 색인이 기록되는 부분

- 트랙 색인 구역

· 기본 구역의 한 트랙 상에 기록되어 있는 데이터 레코드 중의 최대키 값과 주소가 기록되는 색인으로, 한 실린더당 하나씩 만들어짐

· 처리할 레코드가 실제로 어느 트랙에 기록되어 있는지를 판별할 수 있게 함

- 실린더 색인 구역

· 각 트랙 색인의 최대키 값과 해당 레코드가 기록된 실린더의 정보가 기록되는 색인으로, 한 파일당 하나씩 만들어짐

- 마스터 색인 구역

· 실린더 색인 구역의 정보가 많으 경우 그것을 일정한 크기의 블록으로 구성하는데, 이대 해당 레코드가 어느 실린더 색인 구역에 기록되어 있는지를 기록하는 색인

· 오버플로 구역(Overflow Area) : 기본 구역에 빈 공간이 없어서 새로운 레코드의 사빕이 불가능할 때를 대비하여 예비적으로 확보해 둔 부분

- 실린더 오버플로 구역

· 각 실린더마다 만들어지는 오버플로 구역으로, 해당 실린더의 기본 구역에서 오버플로된 데이터를 기록

- 독립 오버플로 구역

· 실린더 오버플로 구역에 더 이상 오버플로된 데이터를 기록할 수 없을 때 사용하는 예비 공간으로, 시린더 오버플로 구역과는 별도로 만들어짐

색인 순차 파일의 장점

· 순차 처리와 랜덤 처리가 모두 간으하므로, 목적에 따라 융통성 있게 처리할 수 있음

· 효율적인 검색이 가능하고 레코드의 삽입, 삭제, 갱신이 용이

· 레코드를 추가 및 삽입하는 경우, 파일 전체를 복사할 필요가 없음

색인 순차 파일의 단점

· 색인 구역과 오버플로 구역을 구성하기 위한 추가 기억공간이 필요함

· 파일 사용중 오버플로 레코드가 많아지면 파일을 재편성해야 함

· 파일이 정렬되어 있어야 하므로 추가, 삭제가 많으면 효율이 떨어짐

· 색인을 이용한 액세스를 하기 때문에 액세스 시간이 랜덤 편성 파일보다 느림

※ 정적 인덱스와 동적 인덱스

· 정적 인덱스 

- 정적 인덱스는 데이터 파일에 레코드가 삽입되거나 삭제되어도 인덱스의 구조가 변경하지 않고 내용만 변하는 구조로, 정적 인덱스를 사용하는 대표적인 파일 : ISAM

· 동적 인덱스

- 동적 인덱스는 인덱스 파일이나 데이터 파일을 블록으로 구성하고 각 블록에는 추가로 삽입될 레코드를 감안하여 빈 공간을 미리 예비해 두는 인덱스 방법으로, 동적 인덱스를 사용하는 대표적인 파일 :  VSAM

- 블록에 레코드가 가득차면 동적으로 분열되고, 일정 수의 레코드가 유지되지 않는 블록은 합병됨

③ VSAM 파일

VSAM(Virtual Storage Access Method) 파일은 동적 인덱스 방법을 이용한 색인 순차 파일

· VSAM 파일은 제어 구간, 제어 구역, 순차 세트, 인덱스 세트로 구성됨

- 제어 구간(Control Interval) : 데이터 레코드가 저장되는 부분

- 제어 구역(Control Area) : 몇 개의 제어 구간을 모아 놓은 것

- 순차 세트(Sequence Set) : 제어 구역에 대한 인덱스를 저장한 것

- 인덱스 세트(Index Set) : 순차 세트의 상위 인덱스

· VSAM 파일은 기본 구역과 오버플로 구역을 구분하지 않음

· 레코드를 삭제하면 그 공간을 재사용 가능

· 제어 구간에 가변 길이 레코드를 쉽게 수용 가능

④ 직접 파일(Direct File)

직접 파일은 파일을 구성하는 레코드를 특정 순서 없이 임의의 물리적 저장공간에 기록하는 것으로, 랜덤 파일, DAM 파일이라고도 함

· 레코드에 특정 기준으로 키가 할당되며, 해시 함수를 이용하여 이 키에 대한 보조기억장치의 물리적 상대 레코드 주소를 계산한 후 해당하는 주소에 레코드를 저장

· 레코드는 해시 함수에 의해 계산된 물리적 주소를 통해 접근 가능

· 임의 접근이 가능한 자기 디스크나 자기 드럼을 사용

직접 파일의 장점

· 직접 접근 기억장치(DASD)의 물리적 주소를 통하여 파일의 각 레코드에 직접 접근하거나 기록할 수 있으며, 접근 및 기록의 순서에는 제약이 없음

· 접근 시간이 바르고 레코드의 삽입, 삭제, 갱신이 용이

· 어떤 레코드라도 평균 접근 시간 내에 검색이 가능

직접 파일의 단점

· 레코드의 주소 변환 과정이 필요하며, 이 과정으로 인해 시간이 소요됨

· 기억공간의 효율이 저하될 수 있음

· 기억장치의 물리적 구조에 대한 지식이 필요하고, 프로그래밍 작업이 복잡함

· 충돌 발생할 염려 있으므로, 이를 위한 기억공간의 확보가 필요함

⑤ 역 파일(Inverted File)

역 파일은 특정 항목을 여러 개의 색인으로 만들어 항목별 특성에 맞게 작업할 수 있도록 한 파일로, 다중 키 파일에 속함

· 하나 또는 몇 개의 색인값을 결합하여 레코드의 주소 결정 가능

· 각 응용마다 적합한 색인을 별도로 구현 가능

· 새로운 레코드를 파일 중간에 삽입하기 쉽고, 검색 속도가 빠름

· 데이터 파일에 접근하지 않아 질의 응답 시간이 줄어들고, 처리가 비교적 쉬움

· 질의를 만족하는 레코드 검색 시 한 번씩만 접근하면 됨

· 색인의 각 항목들의 길이가 가변적

⑥ 다중 리스트 파일(Multi-List File)

다중 리스트 파일은 다중 키 파일의 한 종류로, 각 키에 대하여 색인을 만든 다음 각 데이터 레코드들 간에 다중 리스트를 구축하여 구성한 파일

· 색인은 동일한 키 값을 갖는 데이터 레코드 중 하나의 레코드에 대한 포인터만을 갖고, 후속 데이터는 포인터로 추적하도록 구성

· 색인의 각 항목들의 길이가 고정적이므로 관리가 용이하며 수정, 삭제, 전체 검색이 효율적 

⑦ 다중 링 파일(Multi-Ring File)

다음 링 파일은 같은 특성을 가질 레코드들을 일련의 포인터로 연결하여 구성한 것

· 같은 항목값을 가진 레코드들을 한꺼번에 처리하는 데 효ㅘ적

· 기억 장소가 절약되고, 자료의 중복성을 배제 할 수 있음

· 레코드 형식이 다른 경우에도 처리가 가능

출처 : 2017 시나공 정보처리기사 필기