인덱스 구조와 파일 편성

인덱스

• 인덱스를 통하여 레코드를 빠르게 접근할 수 있음
• 데이터베이스의 물리적 구조와 밀접한 관계가 있음
• 레코드의 삽입/삭제가 자줒 발생 시 인덱스의 개수를 최소화하는 것이 효율적임

 

인덱스 구성 방법

B 트리(Balanced Tree)

• m차 B 트리는 근노드와 단말 노드를 제외한 모든 노드가 최소 m/2, 최대 m개의 서브 트리를 가지는 구조
• 한 노드에 있는 키값은 오름차순을 유지함
• 근노드로부터 탐색, 추가, 삭제가 이루어짐

B+ 트리

• B 트리의 추가, 삭제 시 발생하는 노드의 분열과 합병 연산 과정을 줄일 수 있는 구조
• 가장 널리 사용되는 인덱스 구조이고 레코드 삽입, 삭제 시에도 성능이 보장됨

트라이(Trie) 색인

• 키 탐색을 위해 키값을 직접 표현하는 것이 아니라 키를 구성하는 문자나 숫자 자체의 순서로 키값을 구성하는 구조
• 삽입, 삭제 시 노드의 부녕ㄹ, 병합이 발생하지 않음
• 문자의 함수로 트라이 차수의 키값을 표현함

 

파일 편성 방법

순차 파일(Sequential File)

• 입력되는 데이터의 논리적 순서에 따라 물리적으로 연속된 위치엥 순차적으로 기록하는 방식
• 처리 속도가 빠르고, 연속적인 레코드의 저장에 의해 레코드 사이에 빈 공간이 존재하지 않으므로 기억 장치의 효율적인 이용이 가능함
• 검색 효율이 낮고 대화식 처리보다 일괄 처리에 적합한 구조
• 어떤 형태의 입·출력 매체에서도 처리가 가능함

색인 순차 파일(ISAM : Indexed Sequential Access - Method)

• 키값에 따라 순차적으로 정렬된 데이터를 저장하는 데이터 지역과 이 지역에 대한 포인터를 가진 색인 지역으로 구성된 파일
• 순차 및 직접 접근 형태 모두 가능하도록 레코드들을 키값 순으로 정렬시켜 기록하고, 레코드의 키 항목만으로 모든 색인을 구성하는 방식
• 레코드를 참조할 때 색인을 탐색한 후 색인이 가리키는 포인터를 사용하여 직접 참조할 수 있음
• 레코드를 추가 및 삽입하는 경우, 파일 전체를 복사할 필요가 없음
• 인덱스를 저장하기 위한 공간과 오버플로우 처리를 위한 별도의 공간이 필요함

색인 순차 파일의 구성

기본 영역	데이터 레코드를 지정하는 부분
색인(Index) 영역	기본 영역에 인덱스가 저장되는 부분
오버플로 영역	한 블록 내에 레코드들이 모두 영역을 차지할여 추가적인 레코드 입력을 처리할 수 없을 때 블록을 할당받아 이를 연결시키는 부분이며 실린더 오버플로 영역과 독립 오버플로 영역으로 구성

VSAM 파일(Virtual Storage Access Method File)

• 동적 인덱스 방법을 이용한 색인 순차 파일
• 기본 영역과 오버플로 영역을 구분하지 않음
• 레코드를 삭제하면 그 공간을 재사용할 수 있음
• 레코드 저장한 제어 구간에서 이루어짐
• 제어 구간 단위별 그룹을 제어 영역이라 함
• 제어 영역에 대한 인덱스 저장은 순차 세트, 순차 세트의 상위 인덱스, 인덱스 세트 등이 있음

직접 파일(Direct File)

• 해싱 함수를 계산하여 물리적 주소에 직접 접근하는 방식으로 레코드를 임의 물리적 기억 공간에 기록함
• 특정 레코드에 접근하기 위해서 디스크의 물리적 주소로 변환할 수 있는 해싱 함수를 사용하는 방식
• 속도가 빠르고, 랜덤 처리에 적합함
• 기억 공간 효율이 떨어짐

역파일(Inverted File)

• 특정 파일을 여러 개의 색인으로 만들고 항목별 특성에 맞게 작업하도록 구성한 구조
• 파일 또는 데이터베이스에서 레코드를 빨리 검색하기 위해 별도 인덱스 파일을 만들어 두며 인덱스 파일에는 키 필드의 값과 그 키값을 가지는 레코드에 대한 포인터들이 저장됨
• 검색 속도가 빠름
• 데이터 파일에 접근하지 않아 질의응답 시간이 줄어들고, 처릭가 비교적 쉬움
• 질의를 만족하는 레코드 검색 시 한 번씩만 접근하면 됨

 

정적 인덱싱과 동적 인덱싱

정적 인덱싱 - 색인 순차 파일 방식이 대표적

• 데이터 파일에 레코드가 삽입, 삭제되면 인덱스 내용은 변하지만 인덱스 구조는 정적으로 변하지 않는 구조
• 인덱스 부분과 데이터 부분을 별개의 파일로 구성함

동적 인덱싱 - 가상 기억 접근 방식이 대표적

• 데이터 파일에 레코드가 삽입되면서 삽입될 레코드를 위해 미리 빈 공간을 준비하는 방법
• 레코드가 블록에 가득 차면 동적으로 분열됨
• 인덱스 부분과 데이터 부분을 별개의 파일로 구성함