데이타베이스

목차

Ⅰ. 서론...................................................1

Ⅱ. 데이터 베이스 시스템...................................2

Ⅲ. 데이터 모델링..........................................7

Ⅳ. 관계형 데이터베이스 언어..............................12

Ⅴ. 데이터 베이스의 설계..................................16

Ⅵ. 고급 데이터 베이스....................................18

Ⅶ. 자료구조..............................................22

Ⅷ. 파일구조..............................................28

본문내용

색을 하고, 순차 탐색은 트리의 각 노드를 중위 순회하면서 검색하기 때문에 탐색 속도가 느리다.
B-트리에서의 노드 삽입과 삭제는 트리 구조의 균형을 항상 유지해야 하는데 어려움이 있다. 삽입시 해당 노드에 자유공간이 있는 경우는 킷값을 제 위치에 삽입하지만, 해당 노드에 자유공간이 없으면 삽입 후에 트리 레벨이 하나 증가하는 경우가 발생한다.
8.1.4 B+ 트리
-Knuth가 제안한 B+-트리는 리프가 아닌 노드로 된 인덱스 세트와 리프 노드로만 구성된 순차 세트로 구성되어 있다. B+-트리가 B-트리와 구조적으로 다른 점은 인덱스 세트는 검색 경로만 제공하는 킷값만 가지고 있고, 순차세트는 실제 데이터 값을 가지고 있으며 노드 간에는 링크드 리스트로 순차적으로 연결되어 있다. 따라서 인덱스 세트에는 순차 세트에 있는 킷값이 중복으로 나타난다.
-정의
차수가 m인 B+-트리는 다음 특성을 가지고 있다.
루트는 0, 2, 또는 m/2, m개의 서브트리를 갖는다.
루트와 리프를 제외한 모든 노드는 최소m/2, 최대 m개의 서브트리를 갖는다.
모든 리프는 같은 레벨에 있다. 즉, 루트로부터 같은 거리에 있다.
리프가 아닌 노드에 있는 킷값의 수는 그 노드의 서브트리 수보다 하나 적다.
리프 노드는 데이터 파일의 순차 세트를 나타내며 모두 리스트로 연결되어 있다.
-B+ 트리의 연산
직접 탐색은 루트 노드로부터 차례로 비교하면서 직접 검색을 하고, 순차 탐색은 순차 세트를 이용하여 순차 검색하기 때문에 탐색 속도가 매우 빠르다. 따라서 B-트리의 순차 탐색의 단점을 보완한 이진 트리이다. B+-트리에서의 노드 삽입은 B-트리와 거의 동일하지만, 노드 삭제는 리프 노드에서만 삭제하고 인덱스 부분에 있는 킷값은 삭제하지 않는다.
8.1.5 트라이(Trie)
1)트라이는 정보 검색의 reTRIEval에서 따온 이름으로 키 탐색을 위한 킷값을 직접 표현하지 않고 키를 구성하는 문자나 숫자의 순서로 킷값을 표현한 자료구조이다. 따라서 트라이는 m-진 트리가 된다. 그러나 m-원 탐색 트리는 아니다. 왜냐하면 각 노드에 있는 킷값의 배열 순서가 m-원 탐색 트리의 규칙과 다르기 때문이다.
2)트라이의 차수는 킷값을 표현하기 위해 사용하는 문자의 수에 의해 결정되고, 트라이의 높이는 키 필드의 길이와 같으며, 트라이의 크기는 나타내려고 하는 킷값의 기수와 키 필드 길이에 의해 결정된다.
3)트라이의 장점은 키가 4자리일 경우 4자리를 모두 찾지 않아도 해당 레코드가 없음을 미리 알 수 있으므로 탐색 속도가 빠른 반면에 기억 공간이 많이 소용되는 단점이 있다.
8.2 파일 구조
8.2.1 직접파일(Direct File)
1)직접 파일을 구성하는 방법은 저장하고자 하는 데이터의 킷값을 저장공간의 물리적 주소로 변환할 수 있는 어떤 관계를 정의해 두었다가 이를 활용하는 방법이다.
이 관계를 사상함수 또는 해싱함수(hashing function)라고 하며 주소 변환 프로그램을 의미한다. 해싱함수를 통하여 레코드의 키를 디스크의 물리적 주소로 변환하여 그 주소에 레코드를 저장하는 과정을 해싱이라고 한다.
2)해싱을 사용하여 파일을 만들 때 고려해야 할 필수적인 설계 요소는 버킷 크기, 적재율, 해싱함수, 오버플로 해결기법이다.
3)용어설명
버킷(bucket)이란 하나의 주소를 갖는 파일의 한 구역을 의미하며, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드의 수를 말한다.
슬롯(slot)이란 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷을 형성한다.
충돌(collision)이란 레코드를 삽입할 때 2개의 상이한 레코드가 똑같은 버킷으로 해싱되는 경우를 말하며, 동일한 주소로 해싱되는 이 두 키를 특히 동거자(synonyms)라고 한다.
8.2.2 인덱스된 순차 파일(Indexed Sequential File)
-이 파일은 순차 접근 방법을 지원하는 순차 파일과 직접 접근 방법을 지원하는 직접 파일을 결합한 형태의 파일을 말하며, 킷값에 따라 정렬된 레코드를 순차적으로 접근하거나 주어진 킷값에 따라 직접 접근하는 파일이다. 또 순차적으로 정렬된 순차 데이터 파일과 이 파일에 대한 포인터를 가지고 있는 인덱스로 구성된다. 여기에는 인덱스와 순차 데이터 파일을 구성하는 방법에 따라 정적 인덱스 방법과 동적 인덱스 방법으로 나눈다. 여기서, 다단계 인덱스를 사용하는 목적은 탐색수를 줄이기 위해서이다.
1)인덱스
-마스터 인덱스
-실린더 인덱스
-트랙 인덱스
2)데이터 파일
-기본 구역 : 데이터 레코드를 저장하는 구역
-오버플로 구역 : 기본 구역이 오버플로 되었을 때 레코드를 저장
8.2.3 다중 키 파일(Multi-Key File)
-이 파일 조직은 하나의 데이터 파일에 대해 서로 다른 키 필드를 이용하여 여러 개의 접근 경로, 즉 여러 개의 인덱스를 제공하여 데이터를 탐색하는 방법으로, 대표적인 것으로 역 파일과 다중 리스트가 있다.
1)역 파일(inverted file) 구조
-역 파일은 역 인덱스를 이용하는 구조로서, 역 인덱스 엔트리는 <키값, 동일 키의 모든 레코드 포인터들> 쌍으로 구성되며, 여기서, 역이란 인덱스 엔트리가 될 2개의 값들에 대해 데이터 레코드로부터 추출해서 해당 인덱스에 전도시키는 것을 의미한다. 따라서 데이터 파일은 키 필드에 대해 전도되었다고 한다.
-보조키로 기본키를 찾는 것을 역 인덱스라 한다. 이진 탐색 기법을 사용하면 연산 시간이 O(log2N)이 되므로 매우 호율적으로 검색할 수 있다.
2)다중 리스트 구조
-다중 리스트는 각 보조키(인덱스)마다 각각 링크드 리스트로 구성하는 다중 리스트 파일을 유지하는 구조로서, 인덱스 엔트리가(키값, 하나의 레코드에 대한 포인터) 쌍으로 구성되며, 각 킷값에 대한 엔트리로 그 킷값을 가지고 있는 데이터 레코드 중 하나의 레코드에 대한 포인터만 가지고 있다.
8.2.4 다중 링 파일(Multi-ring File)
-레코드들의 다중 관계를 표현한 파일로서, 같은 특성을 가진 레코드들의 집합을 체인(chain), 즉 링크드 리스트로 연결하여 레코드들을 신속하게 검색하기 위한 파일 구조이다.

키워드

데이타베이스,   정보처리,   it,   db,   정보처리기사