[파일처리] Ch7 Indexing

Index

우선 아래의 그림은 기본 인덱스 구조이다.

 

• 데이터 파일은 입력 순서에 따라 기록이 파일에 입력되는 순서에 따라 발생하는 것을 의미한다.
• 인덱스 파일은 고정 길이 레코드로 구성되며 데이터 파일보다 훨씬 작다.

 

그러나 이런 구조는 다음과 같은 문제를 야기한다.

 

단점

1) 인덱스를 이진 탐색하려면 여러 디스크 검색이 필요하지만 성능이 좋지 않다.
2) 레코드 추가 또는 삭제로 인한 인덱스 재배치는 secondary storage의 레코드를 이동하거나 정렬해야 하므로 비용이 많이 든다.

 

 

이런 문제를 해결하기 위한 방법으로 인덱스의 계층 구조를 형성하는 것이 있다.

 

이때 secondary key는 primary key와 다르게 중복을 허용한다.

결합 중인 목록이 정렬된 순서대로 있으면 일치가 훨씬 쉬워진다.

 

장점

1) 주소가 바뀌었을 때 primary key만 바꿔주면 되기 때문에 수정하기 편하다

 

단점

1) 파일에 새 레코드를 추가할 때마다 인덱스 파일의 재정렬이 필요하다.
2) secondary key 필드가 반복되어 공간이 낭비된다.

 

그래서 이를 또 해결할 두 가지 방법이 있다.

 

1️⃣ 배열을 이용한 구조
각 secondary key 에 대한 primary key 참조 배열을 사용하는 것이다.

이렇게 배열을 사용하게 된다면 레코드가 추가되었을 때 해당하는 secondary key값의 reference field만 재배치하면 된다.

 

그러나, 배열 특성상 배열의 크기에 해당하는 수만큼만 저장할 수 있기 때문에 추가 레이블 ID를 저장할 수 없다. 또한 reference field가 적은 secondary key의 경우, 내부 단편화로 인한 공간이 낭비된다.

 

2️⃣Linked-list를 이용한 구조

 

장점

1) primary key를 쉽게 재정렬할 수 있다.
2) 레코드 수가 적고 레코드 크기가 작기 때문에 재배열이 더 빠르다.

3) 라벨 ID 목록 파일은 entry-sequenced 처리되므로 정렬할 필요가 없다.
4) 삭제된 레코드의 공간을 재사용하기 위한 메커니즘 구현이 용이하다.

단점
1) Label ID 그룹의 경우 물리적으로 그룹화할 수 없다.