2. 정렬, 해싱 - 38. 인덱스, 파일편성
38. 인덱스, 파일편성
1. 색인 순차파일
인덱스
- 인덱스를 통하여 레코드를 빠르게 접근할 수 있다.
- 데이터베이스의 물리적 구조와 밀접한 관계가 있다.
- 레코드의 삽입/삭제가 자주 발생 시 인덱스의 개수를 최소화하는 것이 효율적이다.
key, data, ...
데이터베이스의 물리적 구조
0x02, 0x03, 0x04
인덱스를 갖는다. 클러스터들 그룹으로 지어져 있다.
0x01
클러스터 그룹을 총괄하는 최상의 포인터
인덱스 방법 예 ) 7번 key를 찾겠다.
1. 0x01에서 시작한다. 4 Index ~ 8 Index 사이로 간다. 위쪽이 작고, 밑쪽이 크다.
그렇다면 7 기준에서는 4보다 7은 크고 8보다는 작으므로 중간 클러스터 그룹으로 간다.
2. 0x03으로 간다. 7 Index가 있으므로 해당하는 데이터베이스의 물리적 구조에서 값을 찾아낸다.
90도로 그림을 돌려보면 트리모형이다.
B 트리라고 한다.
B 트리 (Balanced Tree)
인덱스를 표현할 때는 B트리 또는 B+트리를 쓴다.
B 트리는 Balanced트리라 (균형) 해당하는 레벨이 딱 정해져 있다.
m차 B 트리는 근노드와 단말 노드를 제외한 모든 노드가 최소 m/2, 최대 m개의 서브 트리를 가지는 구조이다.
- 한 노드에 있는 키값은 오름차순을 유지한다.
- 근노드로부터 탐색, 추가, 삭제가 이루어진다.
B+ 트리
가장 널리 사용되는 인덱스 구조이고 레코드 삽입, 삭제 시에도 성능이 보장된다.
- B 트리의 추가, 삭제 시 발생하는 노드의 분열과 합병 연산 과정을 줄일 수 있는 구조이다.
- 검색 효율이나 삽입, 삭제 시에 속도를 높이기 위해서 사용한다.
Binary(2진법의) 트리처럼 값을 하나만 갖는 게 아닌
여러 개의 값을 가질 수 있다.
트라이(Trie) 색인
키 탐색을 위해 키값을 직접 표현하는 것이 아니라 키를 구성하는 문자나 숫자 자체의 순서로 키값을 구성하는 구조이다.
- 삽입, 삭제 시 노드의 분열, 병합이 발생하지 않는다.
- 문자의 함수로 티라이 차수의 키 값을 표현한다.
순차 파일(Sequential File)
입력되는 데이터의 논리적 순서에 따라, 물리적으로 연속된 위치에 순차적으로 기록하는 방식이다.
- 처리 속도가 빠르고, 연속적인 레코드의 저장에 의해 레코드 사이에 빈 공간이 존재하지 않으므로 기억 장치의 효율적인 이용이 가능하다.
- 어떤 형태의 입 출력 매체에서도 처리가 가능하다.
검색 효율이 낮고 대화식 처리보다 일괄 처리에 적합한 구조이다.
중간에 데이터를 추가 삽입하기에는 불편하다.
순차적 기록 순차 파일 예 )
카세트테이프, 비디오테이프, CD룸
1. 색인 순차 파일(ISAM : Indexed Sequential Access-Method)
순차 파일의 중간 삽입이 불편해 나온 방법
키 값에 따라 순차적으로 정렬된 데이터를 저장하는 데이터 지역과 이 지역에 대한 포인터를 가진 색인 지역으로
즉 두 가지로 구성된 파일이다.
- 데이터를 자유롭게 추가 삭제할 수 있다.
- 순차 및 직접 접근 형태 모두 가능하도록 레코드들을 키값 순으로 정렬시켜 기록하고, 레코드의 키 항목만으로 모든 색인을 구성하는 방식이다.
- 레코드를 참조할 때 색인을 탐색한 후 색인이 가리키는 포인터를 사용하여 직접 참조할 수 있다.
- 레코드를 추가 및 삽입하는 경우, 파일 전체를 복사할 필요가 없다.
인덱스를 저장하기 위한 공간과 오버플로우 처리를 위한 별도의 공간이 꼭 필요하다. ☆
색인 순차 파일의 구성
1. 기본 영역
데이터 레코드를 지정하는 부분이다.
2. 색인 (Index) 영역
기본 영역에 인덱스가 저장되는 부분이다.
* 구성 (자기 디스크로 생각하면 된다.)
1. 트랙 인덱스
CD룸이나, 레코드를 보면 줄이 있다. 운동장 트랙처럼 되어있는 것을 트랙 인덱스라고 한다.
헤드가 왔다 갔다 하면서 검색해나간다.
디스크가 빙글빙글 돌면서 자료를 갖고 오게 된다.
2. 실린더 인덱스
디스크가 여러 장이 있을 경우에 여러 장의 트랙의 전체 개수가 아니라 한 면의 트랙의 개수를 실린더라고 한다.
3. 마스터 인덱스
마스터는 애내를 다 총괄하는 것이다.
3. 오버플로 영역
한 블록 내에 레코드들이 모두 영역을 차지하여 추가적인 레코드 입력을 처리할 수 없을 때 블록을 할당받아 이를 연결시키는 부분이며 실린더 오버플로 영역과 독립 오버플로 영역으로 구성된다.
VSAM 파일(Virtual Storage Access Method File)
동적 인덱스 방법을 이용한 색인 순차 파일이다.
기본 영역과 오버플로 영역을 구분하지 않는다.
레코드를 삭제하면 그 공간을 재사용할 수 있다.
레코드 저장은 제어 구간에서 이루어진다.
제어 구간 단위별 그룹을 제어 영역이라 한다.
제어 영역에 대한 인덱스 저장은 순차 세트, 순차 세트의 상위 인덱스, 인데스 세트등이 있다.
직접 파일(Direct File)
해싱 함수를 계산하여 물리적 주소에 집적 접근하는 방식으로 레코드를 임의 물리적 기억 공간에 기록한다.
특정 레코드에 접근하기 위해서 디스크의 물리적 주소로 변환할 수 있는 해싱 함수를 사용하는 방식이다.
속도가 빠르고, 랜덤 처리에 적합하다.
기억 공간 효율이 떨어진다.
역파일(Inverted File)
특정 파일을 여러 개의 색인으로 만들고 항목별 특성에 맞게 작업하도록 구성한 구조이다.
파일 또는 데이터베이스에서 레코드를 빨리 검색하기 위해 별도 인덱스 파일을 만들어 두며 인덱스 파일에는 키 필드의 값과 그 키값을 가지는 레코드에 대한 포인터들이 저장된다.
검색 속도가 빠르다.
- 데이터 파일에 접근하지 않아 질의응답 시간이 줄어들고, 처리가 비교적 쉽다.
- 질의를 만족하는 레코드 검색 시 한 번씩만 접근하면 된다.
정적 인덱싱과 동적 인덱싱
색인 순차 파일 방식 : 정적 인덱싱 대표 방식
- 데이터 파일에 레코드가 삽입, 삭제되면 인덱스 내용은 변하지만 인덱스 구조는 정적으로 변하지 않는 구조를 말한다.
- 인덱스 부분과 데이터 부분을 별개의 파일로 구성한다.
가상 기억 접근 방식 : 동적 인덱싱 대표 방식
- 데이터 파일에 레코드가 삽입되면서 삽입될 레코드를 위해 미리 빈 공간을 준비하는 방법을 말한다.
- 레코드가 블록에 가득 차면 동적으로 분열된다.
- 인덱스 부분과 데이터 부분을 별개의 파일로 구성한다.
문제 풀이
1. 해싱 등의 사상 함수를 사용하여 레코드 키(Record Key)에 의한 주소 계산을 통해 레코드에 접근할 수 있도록 구성한 파일은?
직접 파일
2. 자료와 부가적인 정보를 조직하고 저장하는 방법이 파일 구조이다. 파일을 조작할 때 또는 오버플로를 위한 공간이 필요하고 파일을 사용하던 중에 오버플로 레코드가 많아지면 재편성해야 하는 것은?
색인 순차 파일
3. 파일 구성 방식 중 ISAM(Indexed Sequential Access-Method)의 물리적인 색인(Index) 구성은 디스크의 물리적 특성에 따라 색인을 구성하는데, 다음 중 3단계 색인에 해당되지 않는 것은?
① Cylinder index
② Track index
③ Master index
④ Volume index
4번
4. 색인 순차 파일에 대한 설명으로 옳지 않은 것은?
① 레코드를 참조할 때 색인을 탐색한 후 색인이 가리키는 포인터를 사용하여 직접 참조할 수 있다.
② 레코드를 추가 및 삽입하는 경우, 파일 전체를 복사할 필요가 없다.
③ 인덱스를 저장하기 위한 공간이 오버플로우 처리를 위한 별도의 공간이 필요 없다.
④ 색인 구역은 트랙 색인 구역, 실린더 색인 구역, 마스터 색인 구역으로 구성된다.
3번