목차
[Ⅰ.데이터베이스 시스템]
[Ⅱ. 데이터 모델링]
[Ⅲ. 관계 데이터 모델]
[Ⅳ.관계데이터베이스 언어]
[Ⅴ. 데이터 베이스 설계]
[Ⅵ. 고급 데이터 베이스]
[Ⅶ. 자료구조]
[Ⅷ. 파일 구조]
[Ⅱ. 데이터 모델링]
[Ⅲ. 관계 데이터 모델]
[Ⅳ.관계데이터베이스 언어]
[Ⅴ. 데이터 베이스 설계]
[Ⅵ. 고급 데이터 베이스]
[Ⅶ. 자료구조]
[Ⅷ. 파일 구조]
본문내용
됩니다. E는 D보다 커서 D오른쪽에있습니다.
(3회)D의 오른쪽이고 H의 왼쪽인 블럭 [E F G] 에거 가운데값은 F이고, E는 F의 왼쪽에 있습니다.
(4회)F의 왼쪽에 남은 블럭은 E만 있습니다. E를 찾았습니다.
2) 아래보기의 자료에서 이진탐색을 적용할 때 14를 찾기 위한 비교횟수는?
(보기) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
(답)3회
(풀이) (1회) 전체 개수가 15개이고 양쪽을 똑같이 나누어주는 값(가운데값)은 6입니다. 찾고있는 14는 8의 오른쪽입니다.
(2회) 8의 오른쪽 나머지들 [9 10 11 12 13 14 15] 에서 가운데 값은 12 입니다. 14는 12의 오른쪽에 있습니다.
(3회) 12의 오른쪽 나머지 블럭 [13 14 15] 에거 가운데 값은 14이고 찾고있는 14과 같습니다. 찾았습니다.
3) 다음 자료들 중 58을 찾기 위해 이진탐색을 할 경우 비교 횟수는 ?
(보기) 25, 29, 34, 37, 41, 43, 54, 58, 62, 70, 83
(답) 4회 (풀이) (1회) 가운데 값은 43, (2회) 가운데값은 62
(3회) 54, 58의 두수중 작은 값을 찾아 비교한다. (4회) 58을 찾음
4) 이진탐색 알고리즘에서 데이터가 (1,2,3,4,5,6,7,8,9,10,11)로 구성되어 있을 때 찾고자 하는 key 값이 2일 때 데이터와 찾고자하는 key값의 비교횟수는 ? (답)4회
(풀이) (1회) 가운데 값은 6 (2회) 1,2,3,4,5 중 가운데값은 3,
(3회) 1,2 중 작은 값인 1을 비교함 (4회) 2를 찾음
(2) 스레드 이진 트리(threaded binary tree) : 이진트리(binary tree)에서 발생하는 널(null) 링크를 트리 운행에 필요한 다른 노드의 포인터로 사용하도록 고안된 트리
(3) B 트리 :
1) 정의
- 한 노드 안에 있는 킷값은 오름차순을 유지한다.
- 모든 리프(leaf) 노드는 같은 레벨에 있다.
- 루트(root) 노드는 리프가 아닌 이상 적어도 두 개의 서브트리를 갖는다.
- 리프가 아닌 노드의 킷값의 수는 그 노드의 서브트리수보다 하나 적으며, 각 리프 노드는 최소한 "m/2-1", 최대 "m-1"개의 킷값을 갖는다.
(아닌 것 : 킷값의. 삽입이나 삭제시 트리의 총 노드수는 변함이 없다.)
(4) 트라이(Trie) : 키 탐색을 위해 킷값을 직접 표현하지 않고 키를 구성하는 문자나 숫자의 순서로 킷값을 표현한 자료구조
- 트라이의 차수는 킷값을 표현하기 위해 사용하는 문자의 수(radix)에 의해 결정된다.
- 킷값의 분포를 미리 예측할 수 있다면 기억장소를 절약할 수 있다.
- 트라이의 크기는 나타내려고 하는 킷값의 기수와 키 필드 길이에 의해 결정된다.
2. 파일 구조
(1) 저장장치
(2) 직접파일(Direct file)
1) 해싱(Hashing)
① 직접 파일을 구성하는 방법은 저장하고자 하는 데이터의 키값을 저장 공간의 물리적 주소(home address)로 변환할 수 있는 어떤 관계(relationship)를 정의해 두었다가 이를 활용하는 방법
이 관계를 사상함수(mapping function)또는 해싱함수 라고 하고 주소변환 프로그램을 의미한다.
해싱함수를 통하여 레코드키를 디스크의 물리적 주소로 변환하여 그 주소에 레코드를 저장하는 과정을 hashing이라고 한다.
② 해싱을 사용하여 파일을 만들 때 고려할 필수 요소는 버킷크기, 적재율, 해싱함수, 오버플로 해결기법이다.
- 버킷(bucket) : 하나의 주소를 갖는 파일의 한 구역. 버킷의 크기는 같은 주소에 포함될 수 있는 레코드의 수
- 슬롯(slot) : 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 보여 하나의 버킷을 형성한다.
- 충돌(collision) : 레코드를 삽입할 때 2개의 상이한 레코드가 똑같은 버킷으로 해싱되는 것
(아닌 것 : 해싱은 충돌이 발생하면 항상 오버플로우가 발생한다)
③ 해싱함수의 종류
ⅰ. 제산 잔여 해싱(제산(division) 방법) : 키값을 적당한 수로 나누어 이 나눗셈의 나머지를 레코드에 대한 물리적 주소로 사용하는 방법
ⅱ. 중간 제곱(mid-square)해싱 : 킷값을 제곱한 수의 중앙 위치에서 미리 정해진 위치의 숫자를 뽑아내어 주소를 만든다.
ⅲ. 중첩(folding) 해싱 : 키 값을 주소와 같은 자릿수를 갖는 몇 개의 부분으로 나누어 이 부분들을 접어서 그 합을 구한 다음, 그 합에서 주소와 같은 자리수만을 취하는 방법
ⅳ. 숫자 이동 변환해싱( 숫자분석(digit analysis)) : 키를 중앙으로 양분한 뒤에 주소 길이만큼 겹치도록 안쪽으로 각각 이동시켜 이들을 더하는 방법
ⅴ. 진수 변환 해싱 : 키 숫자의 진수를 다른 진수(11진수)로 변환시켜 주소 크기를 초과한 높은 자릿수는 절단시키고 이를 다시 주소 범위에 맞게 조정한다.
(3) 인덱스된 순차 파일(ISAM : Indexed Sequential Access-Method : Indexed Sequential File)
- 인덱스를 저장하기 위한 공간과 오버플로우 처리를 위한 별도의 공간이 필요하다.
- 실제 데이터 처리 외에 인덱스를 처리하는 추가적인 시간이 소모되므로 파일 처리 속도가 느리다.
- 순차 처리와 직접처리가 모두 가능하다.
1) 정적(static) 인덱스 방법
- ISAM파일의 인덱스 : master index, cylinder index, track index (섹터 인덱스는 없다.)
고정길리 레코드만 수용,
2) 동적 인덱스 방법
- VSAM 파일 : 기본 데이터 영역과 오버플로우 영역을 구분하지 않는다.
레코드를 삭제하면 그 공간을 재사용할 수 있다.
제어 구간에 가변 길이 레코드를 쉽게 수용할 수 있다.
(아닌 것 : 특정 레코드에 대해 빠르고 직접적인 접근을 지원할 수 있기 때문에 대화형 처리에 많이 이용된다.)
(아닌 것 : VSAM(virtual storage accdess method file) : 검색속도를 빠르게 하기 위하여 기본 데이터 구역과 오버플로우 구역을 구분하여 갖추어야한다.)
(3회)D의 오른쪽이고 H의 왼쪽인 블럭 [E F G] 에거 가운데값은 F이고, E는 F의 왼쪽에 있습니다.
(4회)F의 왼쪽에 남은 블럭은 E만 있습니다. E를 찾았습니다.
2) 아래보기의 자료에서 이진탐색을 적용할 때 14를 찾기 위한 비교횟수는?
(보기) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
(답)3회
(풀이) (1회) 전체 개수가 15개이고 양쪽을 똑같이 나누어주는 값(가운데값)은 6입니다. 찾고있는 14는 8의 오른쪽입니다.
(2회) 8의 오른쪽 나머지들 [9 10 11 12 13 14 15] 에서 가운데 값은 12 입니다. 14는 12의 오른쪽에 있습니다.
(3회) 12의 오른쪽 나머지 블럭 [13 14 15] 에거 가운데 값은 14이고 찾고있는 14과 같습니다. 찾았습니다.
3) 다음 자료들 중 58을 찾기 위해 이진탐색을 할 경우 비교 횟수는 ?
(보기) 25, 29, 34, 37, 41, 43, 54, 58, 62, 70, 83
(답) 4회 (풀이) (1회) 가운데 값은 43, (2회) 가운데값은 62
(3회) 54, 58의 두수중 작은 값을 찾아 비교한다. (4회) 58을 찾음
4) 이진탐색 알고리즘에서 데이터가 (1,2,3,4,5,6,7,8,9,10,11)로 구성되어 있을 때 찾고자 하는 key 값이 2일 때 데이터와 찾고자하는 key값의 비교횟수는 ? (답)4회
(풀이) (1회) 가운데 값은 6 (2회) 1,2,3,4,5 중 가운데값은 3,
(3회) 1,2 중 작은 값인 1을 비교함 (4회) 2를 찾음
(2) 스레드 이진 트리(threaded binary tree) : 이진트리(binary tree)에서 발생하는 널(null) 링크를 트리 운행에 필요한 다른 노드의 포인터로 사용하도록 고안된 트리
(3) B 트리 :
1) 정의
- 한 노드 안에 있는 킷값은 오름차순을 유지한다.
- 모든 리프(leaf) 노드는 같은 레벨에 있다.
- 루트(root) 노드는 리프가 아닌 이상 적어도 두 개의 서브트리를 갖는다.
- 리프가 아닌 노드의 킷값의 수는 그 노드의 서브트리수보다 하나 적으며, 각 리프 노드는 최소한 "m/2-1", 최대 "m-1"개의 킷값을 갖는다.
(아닌 것 : 킷값의. 삽입이나 삭제시 트리의 총 노드수는 변함이 없다.)
(4) 트라이(Trie) : 키 탐색을 위해 킷값을 직접 표현하지 않고 키를 구성하는 문자나 숫자의 순서로 킷값을 표현한 자료구조
- 트라이의 차수는 킷값을 표현하기 위해 사용하는 문자의 수(radix)에 의해 결정된다.
- 킷값의 분포를 미리 예측할 수 있다면 기억장소를 절약할 수 있다.
- 트라이의 크기는 나타내려고 하는 킷값의 기수와 키 필드 길이에 의해 결정된다.
2. 파일 구조
(1) 저장장치
(2) 직접파일(Direct file)
1) 해싱(Hashing)
① 직접 파일을 구성하는 방법은 저장하고자 하는 데이터의 키값을 저장 공간의 물리적 주소(home address)로 변환할 수 있는 어떤 관계(relationship)를 정의해 두었다가 이를 활용하는 방법
이 관계를 사상함수(mapping function)또는 해싱함수 라고 하고 주소변환 프로그램을 의미한다.
해싱함수를 통하여 레코드키를 디스크의 물리적 주소로 변환하여 그 주소에 레코드를 저장하는 과정을 hashing이라고 한다.
② 해싱을 사용하여 파일을 만들 때 고려할 필수 요소는 버킷크기, 적재율, 해싱함수, 오버플로 해결기법이다.
- 버킷(bucket) : 하나의 주소를 갖는 파일의 한 구역. 버킷의 크기는 같은 주소에 포함될 수 있는 레코드의 수
- 슬롯(slot) : 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 보여 하나의 버킷을 형성한다.
- 충돌(collision) : 레코드를 삽입할 때 2개의 상이한 레코드가 똑같은 버킷으로 해싱되는 것
(아닌 것 : 해싱은 충돌이 발생하면 항상 오버플로우가 발생한다)
③ 해싱함수의 종류
ⅰ. 제산 잔여 해싱(제산(division) 방법) : 키값을 적당한 수로 나누어 이 나눗셈의 나머지를 레코드에 대한 물리적 주소로 사용하는 방법
ⅱ. 중간 제곱(mid-square)해싱 : 킷값을 제곱한 수의 중앙 위치에서 미리 정해진 위치의 숫자를 뽑아내어 주소를 만든다.
ⅲ. 중첩(folding) 해싱 : 키 값을 주소와 같은 자릿수를 갖는 몇 개의 부분으로 나누어 이 부분들을 접어서 그 합을 구한 다음, 그 합에서 주소와 같은 자리수만을 취하는 방법
ⅳ. 숫자 이동 변환해싱( 숫자분석(digit analysis)) : 키를 중앙으로 양분한 뒤에 주소 길이만큼 겹치도록 안쪽으로 각각 이동시켜 이들을 더하는 방법
ⅴ. 진수 변환 해싱 : 키 숫자의 진수를 다른 진수(11진수)로 변환시켜 주소 크기를 초과한 높은 자릿수는 절단시키고 이를 다시 주소 범위에 맞게 조정한다.
(3) 인덱스된 순차 파일(ISAM : Indexed Sequential Access-Method : Indexed Sequential File)
- 인덱스를 저장하기 위한 공간과 오버플로우 처리를 위한 별도의 공간이 필요하다.
- 실제 데이터 처리 외에 인덱스를 처리하는 추가적인 시간이 소모되므로 파일 처리 속도가 느리다.
- 순차 처리와 직접처리가 모두 가능하다.
1) 정적(static) 인덱스 방법
- ISAM파일의 인덱스 : master index, cylinder index, track index (섹터 인덱스는 없다.)
고정길리 레코드만 수용,
2) 동적 인덱스 방법
- VSAM 파일 : 기본 데이터 영역과 오버플로우 영역을 구분하지 않는다.
레코드를 삭제하면 그 공간을 재사용할 수 있다.
제어 구간에 가변 길이 레코드를 쉽게 수용할 수 있다.
(아닌 것 : 특정 레코드에 대해 빠르고 직접적인 접근을 지원할 수 있기 때문에 대화형 처리에 많이 이용된다.)
(아닌 것 : VSAM(virtual storage accdess method file) : 검색속도를 빠르게 하기 위하여 기본 데이터 구역과 오버플로우 구역을 구분하여 갖추어야한다.)
추천자료
관여도에 따라 소비자의 태도형성이 어떻게 달라지는가를 이론에 근거하여 논하시오and2) 소...
유아의 학습에 대한 인지적 관점에 대한 모든것PPT(인지주의학습이론,정보처리이론)
THE SUIT 갤럭시(GALAXY) 기업광고 소개 및 소비자 정보처리 과정과 광고분석
대인 지각과 귀인 (지각, 대인지각 인상형성, 대인지각 정보처리, 귀인).PPT자료
[문자메시지]문자메시지(문자메세지)와 광고문자, 문자메시지(문자메세지)와 심상처리정보, ...
[아동발달] 인지발달이론 - 피아제(Piaget)의 인지발달이론, 정보처리이론, 비고츠키(Vygotsk...
영아기 인지발달 - 인지발달, 피아제(Piaget)의 접근법, 정보처리접근, 언어의 구성요소, 언...
휴리스틱과 바이어스 (잉그리치의 실험, 이중 프로세스 이론, 운동선수의 휴리스틱, 정보처리...
영유아 수학 교육의 이론적 배경들 중 브루너(Bruner)의 정보처리이론과 가드너(Gardner)의 ...
기초 학습 기능 검사 _ 기초 학습 기능 검사의 구성, 소검사의 측정 내용(정보처리, 셈하기, ...
조직구조, 조직구조 설계의 응용, 조직구조의 형태,공식적보고체계,조직구조에 대한 정보처리...
인지이론(認知理論) : 인지학습이론에서의 인지이론 인지적접근론 {인지이론의 배경, 통찰성,...
인지주의 학습이론 중 하나를 선택하고 선택한 이유와 함께 선택한 인지주의 학습이론에 대해...
[유아발달] 인지발달의 지능에 대한 관점을 심리측정적 관점, 정보처리적 관점, 다중지능 ...
소개글