류프리

제1항 관계데이터언어(관계대수, 관계해석)

관계 데이터베이스의 릴레이션을 조작하기 위한 기본연산에는 관계대수(relational algebra)와 관계해석(relational calculus)이 있다. 이 연산은 사용자의 입장에서 볼 때 데이터를 처리하는 데이터 언어가 되며 관계대수는 절차적 언어이며 관계해석은 비절차적 언어이다.

(１) 관계대수(relational algebra)

1) 대수

① 수 대신 문자를 사용해서 문제를 쉽게 하고, 수학적인 법칙을 간단하고 명확하게 표현하는 것

2) 관계대수 정의

① 관계대수는 E.F. Codd가 관계 데이터 모델을 처음 제안할 때 정의

② 관계 대수(relational algebra)는 관계 해석(relational calculus)과 함께 관계 데이터 모델에서 릴레이션을 처리하기 위한 정형적인 데이터 언어이다. 이 관계 대수는 원하는 데이터를 얻기 위해서 어떻게(how) 질의를 수행할 것인지 일련의 연산을 순서대로 명시해야 하는 절차적 언어이다.

③ 데이터베이스에 저장된 데이터를 문자와 연산을 통해 요청한 데이터를 정보화하여 얻을 수 있는데 그 원리가 산술 연산자와 유사

④ 관계 데이터베이스의 관계(relation), 즉 테이블을 조작하는 언어

⑤ 하나 또는 그 이상의 테이블을 피연산자로 하여 결과로 하나의 테이블을 만들어내는 연산을 말한다.

⑥ 관계대수는 질의에 대한 결과를 생성하기 위해 수행해야 할 연산의 순서를 명시하는 절차적 언어이다.

⑦ 연산자의 종류

3) 순수 관계 연산자

① 디비전(division)

ü 나누어지는 릴레이션인 A는 릴레이션 B의 모든 튜플에 연관되어 있는 A의 튜플을 선택한다.

ü X⊃Y인 2개의 릴레이션에서 R(X)와 S(Y)가 있을 때, R의 속성이 S의 속성값을 모두 가진 튜플에서 S가 가진 속성을 제외한 속성만을 구함

ü R[속성r ÷ 속성s]S

② 프로젝트(project, P)

ü 릴레이션에서 주어진 조건에 만족하는 속성(attribute)만을 검색하는 연산

ü 형식 : P속성리스트(R)

ü 릴레이션의 열(세로)에 해당하는 속성들을 추출하는 연산자로써 수직 연산을 수행

③ 조인(join, ⋈)

ü 릴레이션에서 조건에 만족하는 레코드를 분리해 내는 연산을 의미하는 것으로 하나의 릴레이션에서 수평적인 부분 집합을 취하는 것이다.

ü 두개의 릴레이션으로부터 연관된 튜플들을 결합하는 연산자

ü 공통 속성을 중심으로 두개의 릴레이션을 하나로 합쳐서 새로운 릴레이션을 만듦

• Natural join(자연 조인)

- 동등 조인의 결과 릴레이션에서 조인 속성을 한 개 제외한 조인

- 여러가지 조인 연산자들 중에서 가장 자주 사용됨

• Equi join(동등 조인)

- 동등 조인의 결과 릴레이션에서 조인 속성을 모두 나타낸다.

ü 학생[학번⋈학번]성적

④ 셀렉트(selection, σ)

ü 릴레이션에서 주어진 조건을 만족하는 튜플들을 선택하는 연산자

ü σ조건(R)

ü 튜플 단위로 조건에 만족하는 튜플들을 가져오는 수평 연산을 수행

ü 학생 릴레이션에 대한 셀렉션 연산

4) 일반 집합연산자

① 집합 연산자

ü 릴레이션이 튜플들의 집합이기 때문에 기존의 집합 연산이 릴레이션에 적용

ü 집합 연산자의 입력으로 사용되는 두개의 릴레이션은 합집합 호환(union compatible)이어야 함

② 합집합(union)

ü 합병 가능한 두 릴레이션 A 또는 B에 속하는 튜플들로 구성된 릴레이션이다.

ü 두 릴레이션 R과 S의 합집합 R∪S는 R 또는 S에 있거나 R과 S 모두에 속한 튜플들로 이루어진 릴레이션

ü 결과 릴레이션에서 중복된 튜플들은 제외됨

③ 교집합(intersection)

ü 합병 가능한 두 릴레이션 A와 B에 공통적으로 속하는 튜플들로 구성된 릴레이션이다.

ü 두 릴레이션 R과 S의 교집합 R∩S는 R과 S 무두에 속한 튜플들로 이루어진 릴레이션

④ 차집합(difference)

ü 합병 가능한 두 릴레이션 A에만 있고 B에는 없는 튜플들로 구성된 릴레이션이다.

ü 두 릴레이션 R과 S의 차집합 R – S는 R에는 속하지만 S에는 속하지 않은 튜플들로 이루어진 릴레이션

⑤ 카티션 곱(cartesian product)

ü A에 속한 각 튜플 a에 대하여 B에 속한 튜플 b를 모두 접속시킨 튜플들(a, b)로 구성된 릴레이션이다.

5) 관계 대수의 한계

① 관계 대수는 산술 연산을 할 수 없음

② 집단 함수(aggregate function)를 지원하지 않음

③ 정렬을 나타낼 수 없음

④ 데이터베이스를 수정할 수 없음

⑤ 프로젝션 연산의 결과에 중복된 튜플을 나타내는 것이 필요할 때가 있는데 이를 명시하지 못함.

6) 추가된 관계 대수 연산자

① 집단함수(aggregate function)

ü 모든 사원들의 급여 평균은 얼마인가?

② 그룹화

ü 각 부서별 사원들의 급여 평균은 얼마인가?

③ 외부조인

ü 상대 릴레이션에서 대응되는 튜플을 갖지 못하는 튜플이나 조인 속성에 널값이 들어 있는 튜플들을 다루기 위해서 조인 연산을 확장한 조인

ü 두 릴레이션에서 대응되는 튜플들을 결합하면서, 대응되는 튜플을 갖지 않는 튜플과 조인 애트리뷰트에 널값을 갖는 튜플도 결과에 포함시킴

ü 왼쪽 외부 조인(LEFT OUTER JOIN), 오른쪽 외부 조인(RIGHT OUTER JOIN), 완전 외부 조인(FULL OUTER JOIN)

④ 왼쪽 외부조인

ü 릴레이션 R과 S의 왼쪽 외부 조인 연산은 R의 모든 튜플들을 결과에 포함시키고, 만일 릴레이션 S에 관련된 튜플이 없으면 결과 릴레이션에서 릴레이션 S의 속성값을 널값으로 채움

⑤ 오른쪽 외부조인

ü 릴레이션 R과 S의 오른쪽 외부 조인 연산은 S의 모든 튜플들을 결과에 포함시키고, 만일 릴레이션 R에 관련된 튜플이 없으면 결과 릴레이션에서 릴레이션 R의 속성값을 널값으로 채움

⑥ 완전 외부조인

ü 릴레이션 R과 S의 완전 외부 조인 연산은 R과 S의 모든 튜플들을 결과에 포함시키고, 만일 상대 릴레이션에 관련된 튜플이 없으면 결과 릴레이션에서 상대 릴레이션의 속성값을 널값으로 채움

(２) 관계해석(relational calculus)

1) 정의

① 원하는 데이터만 명시하고 질의를 어떻게 수행할 것인가는 명시하지 않는 선언적인 언어

2) 관계해석의 특징

① 비절차 언어

② 튜플 관계 해석과 도메인 관계 해석이 있다.

③ 기본적으로 관계해석과 관계대수는 관계 데이터베이스를 처리하는 기능과 능력면에서 동등함

④ 수학의 predicate calculus에 기반을 두고 있음

⑤ 관계해석으로 질의어를 표현

⑥ 원하는 릴레이션을 정의하는 방법을 제공, 즉 원하는 정보가 무엇이라는것만 정의하는 비절차적인 언어

⑦ 연산들의 절차(sequence)를 사용하여 데이터를 가져옴

⑧ 기본적인 연산자로 union, intersection, difference를 사용함

⑨ 전체관계를 조작하는데 사용되는 연산들의 집합

제1항 관계데이터모델

(１) 정의

1) 열과(column)과 행(row)으로 이루어진 테이블(릴레이션, relation)과 수학적으로 정의된 연산들로 구성된 것

2) 논리적인 데이터 모델에서 데이터간의 관계를 기본키(primary key)와 이를 참조하는 외래키(foreign key)로 표현하는 데이터 모델

3) 개체 집합에 대한 속성 관계를 표현하기 위해 개체를 테이블(table)로 사용하고 개체 집합들 사이의 관계를 공통 속성으로 연결하는 독립된 형태의 데이터 모델

4) 1970년 E.F.Codd의 논문에서 언급된 개념이다.

5) 관계 데이터 모델의 핵심은 릴레이션(relation) 이다.

① 릴레이션(relation)

ü 정의

• 열(column)과 행(row)으로 이루어진 테이블을 말한다.

• 릴레시션 스킴(relation scheme)과 릴레이션 인스턴스(relation instance)로 구성된다.

ü 특성

• 한 릴레이션에는 중복된 투플이 존재하지 않음.

• 한 릴레이션에 저장된 투플들 간에는 순서가 없음.

• 한 릴레이션을 구성하는 속송들간에는 순서가 없음.

• 모든 속성값은 원자값(atomic value) 이다.

그림 42. relation database schema

(２) 특징

1) 데이터와 데이터간의 관계가 테이블로 표현된다.

2) 테이블(table) = 릴레이션(relation)

3) 구조가 간단해서 이해하기 쉬우며, 데이터 조작면에서도 명확하다.

(３) 관계형 모델용어 vs DBMS 용어

1) 릴레이션(relation)

① 열과 행을 가지는 테이블

② 테이블(table), 개체(entity), 파일(file)과 같은 개념

※ 속성(attribute)의 원자값

모든 속성값은 원자값(atomic value) 이다. 이 성질이 뚯하는 것은 더 이상 분해할 수 없는 원자값을 의미한다.

2) 속성(attributes)

① 개체의 성질, 분류, 식별, 수량, 상태 등을 나타내는 세부 정보의 관리 요소로서 개체를 구성하는 항목

② 열(column), 필드(field), 항목(item)과 같은 개념

3) 튜플(tuple)

① 릴레이션의 행을 구성하는 속성(attribute) 값들의 집합

② 행(row), 레코드(record)와 같은 개념

4) 차수(degree)

① 속성(attribute)들의 수

5) 카디날리티(cardinality)

① 튜플(tuple)들의 수

6) 도메인(domain)

① 하나의 속성(attribute)가 취할 수 있는 같은 타입의 원자(atomic) 값들의 집합

② 표현되는 속성 값의 범위를 나타냄

③ 예) 성별의 도메인은 ‘남’, ‘여’ 만이 가능.

7) 릴레이션 인스턴스(relation instance)

① 릴레이션의 어느 시점에 들어 있는 튜플들의 집합 (동적인 성질)

② 튜플들의 집합으로 현재 들어가 있는 실제 데이터를 지칭한다

(４) 키(key)

1) 정의

① 데이터베이스에서 조건에 만족하는 튜플(tuple)을 찾거나 순서대로 정렬할 때 튜플들을 서로 구분할 수 있는 기준이 되는 속성(attribute)들을 말한다.

2) 특성

① Not null

ü 속성의 값은 null이 될수 없다. (null = undefined)

• 기본키의 속성값은 not null이다.

ü Null

• 데이터베이스에서 아직 알려지지 않거나 모르는 값으로서 해당 없음등의 이유로 정보 부재를 나타내기 위해 사용하는 특수한 데이터 값이다. 즉, 공백(space)도, 영(zero)도 아닌 부재정보(missing information)를 나타냄

② 유일성(uniqueness)

ü 하나의 키 값으로 하나의 튜플만을 유일하게 식별할 수 있어야 함

ü 속성의 집합인 키의 내용이 릴레이션 내에서 유일하다는 특성임

ü 즉, 릴레이션 내에서는 중복되는 튜플이 존재하지 않는 것을 말함

ü 유일성을 만족하는 키의 종류

• 기본키(primary key) : 후보키중에서 선택된 키이므로 유일성과 최소성 모두 만족한다.

• 후보키(candidate key) : 유일성과 최소성 모두 만족

• 슈퍼키(super key): 유일성만 만족

③ 최소성(minimality)

ü 속성의 집합인 키가 릴레이션의 모든 튜플을 유일하게 식별하기 위해 꼭 필요한 속성들로 구성된 것을 의미한다.

ü 즉, 속성들의 집합에서 특정 속성 하나를 제거하면 튜플을 유일하게 식별할 수 없는 경우에 해당 함.

ü 최소성을 만족하는 키의 종류

• 후보키(candidate key) : 유일성과 최소성 모두 만족

• 기본키(primary key): 후보키에서 선택된 키이므로 유일성과 최소성 모두를 만족한다.

3) 종류

① 후보키(candidate key)

ü 릴레이션을 구성하는 속성들 중에서 튜플을 유일하게 식별할 수 있는 하나 또는 몇 개의 속성(attribute)의 집합

ü 유일성과 최소성을 모두 만족

② 기본키(primary key)

ü 릴레이션의 유일한 식별자

ü 릴레이션에서 기본키 지정된 속성(attribute)은 같은 값을 가질 수 없다.

ü 후보키 중에서 선정된 키로 중복값을 가질 수 없다.

ü 후보키의 성질을 가짐 (유일성, 최소성 모두 만족)

ü 기본키의 특성

• Not null

• Unique

• 외래키(foreign key)로 참조될 수 있다.

③ 대체키(alternate key)

ü 후보키가 둘 이상 되는 경우에 기본키로 선택되지 못한 후보키들을 대체키라고 한다.

ü 후보키 = 기본키 + 대체키

④ 슈퍼키(super key)

ü 유일성만 있고 최소성이 없는 속성(attribute)의 집합을 말한다.

⑤ 외래키(foreign key)

ü 한 테이블의 키 중 다른 테이블의 튜플을 식별할 수 있는 키를 말한다.

4) 키와 데이터 무결성

① 정의

ü 권한이 부여된 사용자에 의하여 발생할 수 있는 데이터베이스의 오류를 방지하기 위함

ü 데이터의 정확성, 일관성, 신뢰성을 위해 무효 갱신으로부터 데이터를 보호하여 관계 데이터베이스를 의미 있게 하는 제약조건

② 기본 데이터 무결성

제1항 정렬, 탐색기법

(１) 정렬

1) 정렬(sort)의 정의

① 레코드나 데이터에 담긴 키값에 따라 순서대로 나열하는 것

② 정렬은 정렬되지 않은 항목 또는 레코드의 리스트를 각 레코드의 값에 기초한 기준에 따라 순서 있게 나열하는 것이다.

③ 초기에 정렬되지 않은 레코드의 순서를 정렬될 때까지 재배치하는 과정

그림 37. 정렬의 종류

2) 정렬기법

① 내부정렬기법

ü 정의

• 데이터량이 적을 때 주기억장치 내에서 정렬하는 방법

ü 특징

• 속도는 빠르나, 정렬할 자료의 양이 많은 경우 부적합

ü 종류

• 히프 정렬(heap sort)

• 기수 정렬(radix sort)

• 선택 정렬(selection sort)

• 버블 정렬(bubble sort)

• 퀵 정렬(quick sort)

• 삽입 정렬(insertion sort)

• 쉘 정렬(shell sort)

② 외부정렬기법

ü 정의

• 대용량의 데이터를 몇 개의 서브 파일로 나누어 각각 내부 정렬을 한 후에 테이프나 디스크 내에서 각 서브 파일을 합병하는 방법

ü 특징

• 속도는 느리지만 정렬하고자 하는 자료의 양이 많을 경우 효과적 (주기억장치+보조기억장치)

ü 종류

• 진동 병합 정렬(oscillating merge sort)

• 밸런스 병합 정렬(balanced merge sort)

• 캐스캐이드 병합 정렬(cascade merge sort)

• 폴리파즈 병합 정렬(polyphase merge sort)

3) 정렬기법 종류

① 버블 정렬(bubble sort)

• 버블정렬은 인접한 두 키를 비교한 결과로 정렬하는데 만약 비교하였을 때 두 키의 순서가 다르다면 교환하고 그렇지 않다면 그대로 두는 방법이다.

• 정렬과정이 물속 깊은 곳에서 일어난 거품이 수면을 향해 올라오는 모습과 같다고 해서 붙여진 이름이다.

② 삽입 정렬(insertion sort)

• 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘

- 데이터 집합에서 정렬 대상이 되는 요소들을 선택합니다. 이 정렬 대상은 왼쪽부터 선택해 나가며, 그 범위가 처음에는 2개이지만 알고리즘 반복횟수가 늘어날 때마다 1개씩 커집니다. 정렬 대상의 최대 범위는 “데이터 집합의 크기 – 1” 이 됩니다.

- 정렬 대상의 가장 오른쪽에 있는 요소가 정렬 대상 중 가장 큰 값을 갖고 있는지 확인합니다. 만약 그렇지 않다면, 이 요소를 정렬 대상에서 뽑아내고, 이 요소가 위치할 적절한 곳을 정렬 대상 내에서 찾습니다. 여기서 적절한 곳이라 함은 데이터 집합의 가장 왼쪽을 기준으로 했을 때 자신보다 더 작은 요소가 없는 위치를 말합니다.

- 뽑아 든 요소를 삽입할 적절한 곳을 찾았다면, 정렬 대상 내에서 삽입할 값보다 큰값을 갖는 모든 요소를 한자리씩 오른쪽으로 이동시키고 새로 생긴 빈 자리에 삽입시킵니다.

- 전체 대이터 집합의 정렬이 완료될 때까지 1~3를 반복합니다.

• 이 정렬 알고리즘은 지급 완료 수표나 카드를 정렬된 채로 손에 쥐고서 그것들 사이에 적당한 위치에 정렬되지 않은 것을 한 개씩 삽입할 때 발생할 수 있다.

③ 선택 정렬(selection sort)

• 레코드의 최소값을 찾아 첫 번째 위치에 놓고 다음 최소값을 찾아 두 번째 위치에 놓는 방법을 반복하여 정렬함.

④ 히프 정렬(heap sort)

• 연산 시간이 최악과 평균의 경우, 모두 0(n logⁿ)으로 빠른 속도를 가짐

• 전이진 트리(complete tree)를 이용한 정렬 방식

• 이진 트리를 힙 정렬로 변환

- 주어진 레코드들을 순서대로 넣어 진이진 트리로 구성

- 전이진 트리의 노드의 역손으로 자식노드와 부모노드를 비교하여 큰값을 위로 올림

- 교환된 노드들을 다시 검토하여 위의 고정을 반복한다.

⑤ 퀵 정렬(quick sort)

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

⑥ 기수 정렬(radix sort)

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

⑦ 2-way 합병 정렬

• 주어진 입력 파일을 크기가 2인 서브 파일로 모두 나누어서 각 서브 파일들을 정렬하는 방법

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

① 키 값들의 분포상태

② 소요 공간 및 작업시간

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

④ 데이터의 양

⑤ 초기 데이터의 배열상태

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

(２) 탐색기법

1) 탐색기법의 종류

① 이진 검색(binary search)

ü 일정한 순서로 배열된 레코드를 2개 부분으로 되풀이하여 나누어서 한 부분은 버리고 남은 부분을 검색하는 방법

ü 자료가 반드시 정렬되어 있어야 함 (이진 검색의 선행 조건)

ü 정렬된 연접 리스트에서 특정 레코드가 있다고 알려진 리스트의 남겨진 반쪽 부분을 되풀이하여 보면서 특정 레코드를 찾는 빠른 방법

ü 다음과 같이 R={2,3,5,7,8,9,10} 일 때, 이진 검색 방법으로 8을 찾을 경우 비교 횟수는?

② 보간 검색(Interpolation search)

ü 찾고자 하는 레코드 키가 있음직한 위치를 추정하여 검색하는 방법

2) 해싱(hashing)

① 해싱의 정의

ü 키 값으로부터 레코드가 저장되어 있는 주소를 직접 계산하여, 산출된 주소로 바로 접근하는 방법, 키-주소 변환 방법이라고도 함

ü 검색 방법 중 속도는 가장 빠르지만 충돌현상 시 오버플로 해결의 부담이 과중되며 많은 기억공간을 요구하는 검색 방법

② 해시 테이블(hash table)

ü 자료가 저장되는 전체 저장소를 해시 테이블(hash table)이라고 한다.

ü 해시 테이블은 여러 개의 버킷(bucket)으로 나누어지는데 데이터를 삽입할 때 데이터의 값으로부터 적절한 버킷을 선택해서 삽입해야 한다.

ü 버킷은 여러 개의 슬롯(slot)으로 구성되는데 슬롯은 버킷에 데이터가 저장되는 단위이다. 예를 들면 주소록의 각 페이지별로 한 명만 적을 수 있는 것이 아니라 여러명을 적을 수 있어야 하는데 이때 한명의 주소를 적는 칸을 슬롯이라고 한다.

ü 버킷(bucket)

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

ü 슬롯(slot)

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

ü 충돌(collision)

• 레코드를 삽입할 때 2개의 상이한 레코드가 똑 같은 주소로 해싱 되는 것을 의미

ü 동의어(synonym)

• 해싱 함수의 값이 같은 키들의 집합

③ 해싱함수의 종류

ü 중간제곱(mid-square) 방법

• 레코드의 키를 제곱한 후 그 중간 부분의 값을 목적 주소로 사용하는 방법

ü 숫자분석(digit analysis) 방법

• 레코드 키를 구성하는 수들이 모든 키들 내에서 각 자리별로 어떤 분포인지를 조사하여 비교적 고른 분포를 나타내는 자릿수를 필요한 만큼 선택하여 목적 주소로 사용하는 방법

ü 제산(division) 방법

• 레코드의 키를 해시테이블의 크기보다 큰 소수로 나누는 방법

ü 중첩(접지) 방법(Folding method)

• 주어진 키를 여러 부분으로 나누고, 각 부분의 값을 더하거나 배타적 논리합(XOR, exclusive OR) 연산을 통하여 나온 결과로 주소를 취하는 방법

ü 기수(radix) 변환법

• 어떤 진법으로 표현된 주어진 레코드 키 값을 다른 진법으로 간주하고 키 값을 변환하여 홈 주소로 취하는 방식

④ 오버플로 처리방법

ü 충돌(collision)이 발생했을 때 버킷에 저장할 슬롯이 없다면 오버플로우가 발생한다.

ü 재해싱 방법(rehashing)

• 여러 개의 해싱함수를 준비하였다가 충돌 발생시 새로운 해싱함수를 적용하여 새로운 해시표를 생성하는 방법

ü 개방 주소법(open addressing)

• 충돌(collision)이 발생했을 때 순서대로 다음 버킷에 저장하는 방법

ü 체인방법

• 오버플로우 발생시 이를 별도의 기억 공간에 두고 링크로 연결하여 사용하는 방법

ü 폐쇄 주소법(close addression)

• 별도의 오버플로우 영역에 저장하고 체인(chain)으로 홈 버킷에 연결한다.

• Direct chaining: 해시 테이블 내의 빈 공간에 오버플로우 레코드를 보관한다.

• Indirect chaining: 해시 테이블과는 별도의 기억공간에 오버플로우 레코드를 보관한다.

제2항 인덱스구조

(１) 인덱스 (index)

1) 인덱스의 정의

① 검색을 빠르게 하기 위해 만든 보조적인 데이터 구조

② B트리, B+트리, 트라이 등의 자료구조를 사용하여 구현함

③ 인덱스 파일

ü 검색수를 줄이기 위해 다단계 인덱스를 사용

2) 인덱스의 특징

① 인덱스는 하나 이상의 필드로 만들어도 됨

② 인덱스를 통해서 테이블의 레코드에 대한 액세스를 빠르게 수행할 수 있음

3) 트라이 (trie)

① 검색을 위한 키값을 직접 표현하지 않고 키를 구성하는 문자나 숫자 자체의 순서로 키값을 구성하는 구조

② 트라이의 차수는 키 값을 표현하기 위해 사용하는 문자의 수(radix)에 의해 결정함

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

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

⑤ 키 값이 문자열 또는 숫자일 경우 일련의 키 값들에 대해 일부분이 같은 문자나 숫자로 구성되었을 때, 즉 전체 키 값의 길이보다 키 값들 사이에 별개의 전위(prefix) 수가 작을 때 적합함

⑥ 가변 길이의 키 값을 효과적으로 나타낼 수 있으며, 삽입 및 삭제 시 노드의 분열과 병합이 없음

4) 인덱스 구분

① 정적인덱스

ü 데이터 파일의 레코드가 삽입되거나 삭제됨에 따라 인덱스의 내용은 변하지만 구조자체는 변하지 않음

② 동적인덱스

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

ü 레코드의 삽입으로 인해 블록에 레코드가 가득 차면 동적으로 분열 됨

ü 레코드의 삭제로 인해 일정 수의 레코드가 블록에 유지되지 않으면 블록의 합병이 일어남