[파일구조] - 인덱싱(Indexing)

1. Entry Sequenced File

Entry sequenced file은 레코드가 입력되는 순서대로 저장되는 파일이다. 레코드가 입력되는 순서대로 파일에 저장되기 때문에 파일에 저장된 레코드들은 정렬되어있지 않다. 파일에 저장된 레코드들이 정렬되어있지 않기 때문에 어떤 레코드를 찾기 위해서는 파일의 앞쪽부터 순차적으로 레코드를 읽어야한다. Entry sequenced file은 데이터를 관리한다는 측면에서는 매우 비효율적인 구조이다. Entry sequenced file의 이러한 문제점을 해결하기 위해 레코드가 입력될 때마다 레코드들을 정렬하는 sorted file을 생각할 수 있지만, sorted file에는 아래와 같은 치명적인 문제점이 존재한다.

• 레코드가 입력될 때 파일을 정렬한다면, 레코드가 입력될 때마다 하드디스크에 접근하여 레코드들을 shift해야 한다. 만약, 레코드의 크기가 512B이고, 파일의 크기가 1GB라면 최악의 경우에는 512B의 데이터를 쓰기 위해 1GB의 데이터를 하드디스크에 다시 써야한다.
• 파일에 입력하려는 레코드가 파일의 어느 위치에 입력되어야 하는지 찾는 것 또한 하드디스크의 데이터를 읽어야 하기 때문에 엄청난 오버헤드가 발생한다.

Entry sequenced file은 정렬되어 있지 않기 때문에 이진 탐색(binary search)을 이용할 수 없다. 심지어 sorted file 조차도 가변 길이 레코드를 이용하는 파일이라면 entry sequenced file과 같이 이진 탐색을 이용할 수 없다. 결국, 가변 길이 레코드를 이용하는 파일에서는 entry sequenced file과 sorted file 모두 $O(n)$의 시간복잡도를 갖는 순차 탐색(sequential search)을 이용해야 한다. 따라서, entry sequenced file의 반대인 sorted file 또한 완벽한 해결책이 되지 못한다.

2. 인덱스를 이용한 구조

앞에서 서술한 바와 같이 entry sequenced file과 sorted file 모두 데이터를 관리하는데 적합하지 않다. 그러나 인덱스를 이용함으로써 이러한 문제점을 아주 많은 부분 해결할 수 있다. 인덱스는 키(key)와 참조 필드(reference field)로 구성되는 데이터 구조로써, key 값에 따라 정렬되어있다. 인덱스와 데이터 파일간의 관계를 나타내면 아래의 그림과 같다.

인덱스는 실제 데이터보다 크기가 매우 작기 때문에 메모리에 유지할 수 있다. 따라서, 인덱스는 매번 하드디스크에 접근해야하는 레코드보다 정렬된 상태로 유지하는데 비용이 비교할 수 없을 정도로 적게 소모된다. 또한, 인덱스는 데이터와 다르게 크기가 대부분 일정하기 때문에 가변 길이가 아닌, 고정 길이로 구현하여도 심각한 내부 단편화(internal fragmentation)는 발생하지 않는다.

인덱스는 정렬되어 있고, 고정 길이로 구현되기 때문에 이진 탐색을 이용하여 탐색을 할 수 있으며, 참조 필드로 레코드의 위치를 저장하고 있기 때문에 레코드가 저장된 데이터 파일에 직접 접근(direct access)할 수 있다.

3. 인덱스 파일

파일의 데이터를 관리하는데 있어, 인덱스는 매우 효율적인 수단이다. 인덱스 파일은 데이터 파일에 대한 인덱스를 저장하기 위한 것이며, 아래와 같은 3가지 특징을 갖고 있다.

• 인덱스 파일의 한 레코드는 키와 참조 필드, 총 2개의 필드로 구성된다.
• 레코드의 각 필드는 고정 길이이며, 레코드 또한 고정 길이이다.
• 데이터 파일은 정렬되지 않은 상태로 저장되지만, 인덱스 파일은 정렬된 상태로 저장된다.