[파일구조] - 인덱스 파일의 구현 II

이 글의 소스 코드는 File Structures: An Object-Oriented Approach with C++ 3rd Edition의 내용을 수정하여 작성한 것 입니다.

1. 인덱스 파일의 구조

인덱스 파일은 앞에서 정의한 TextIndex를 저장하는 파일이다. 인덱스 파일은 고정 길이 필드, 고정 길이 레코드로 구성된다. 인덱스 파일은 파일은 파일 자체를 나타내는 BufferFile과 메모리 상에 인덱스를 저장하고 있는 TextIndex, 그리고 TextIndex를 버퍼 단위로 파일입출력하기 위한 TextIndexBuffer로 구성된다.

2. Class TextIndexedFile

TexIndexedFile은 데이터 파일만 하드디스크에 저장하는 것이 아니라, 인덱스 파일도 같이 저장한다. TextIndexedFile의 정의는 아래와 같다.

template <class RecType> class TextIndexedFile { public: int Read(RecType & record); int Read(char *key, RecType & record); int Append(const RecType & record); int Update(char *oldKey, const RecType & record); int Create(char *name, int mode = ios::in | ios::out); int Open(char *name, int mode = ios::in | ios::out); int Close(); void DisplayDataFile(); void DisplayIndexes(); TextIndexedFile(IOBuffer & buffer, int keySize, int maxKeys = 100); ~TextIndexedFile(); protected: TextIndex index; BufferFile indexFile; TextIndexBuffer indexBuffer; RecordFile<RecType> dataFile; char *fileName; int maxKeys; int SetFileName(char * fileName, char *& dataFileName, char *& indexFileName); };

TextIndexedFile에는 두 가지 단점이 존재한다.

• 키 값은 언제나 문자열 형태이어야만 한다.
• 하나의 TextIndexedFile에는 하나의 TextIndex만 존재할 수 있다.

위의 두 가지 단점을 제거하기 위해서는 C++의 템플릿을 이용하여 키 값의 타입을 인자로 받는 새로운 TextIndex를 정의하고, TextIndexedFile의 Insert, Remove, Search 함수를 TextIndex가 아닌 TextIndex의 배열을 대상으로 동작하게 수정하면 된다.

3.TextIndex의 문제점 및 인덱스 계층 구조

TextIndex에 저장된 인덱스의 양이 많아질수록 TextIndex에는 두 가지 문제점이 발생한다.

• TextIndex의 크기가 메모리에 유지할 수 없을 정도로 커지면 이진 탐색의 효율이 급격히 감소한다.
• Insert, Remove 연산 수행 시, 인덱스를 shift하는 비용이 크게 증가한다. 

위의 문제를 완화하기 위한 가장 단순한 방법은 인덱스의 계층 구조를 형성하는 것이다. 인덱스의 계층 구조는 도서관에서 "File Structures: An Object-Oriented Approach with C++"라는 책을 찾고자 할 때 책의 제목으로 바로 위치를 찾는 것이 아니라, "공학"이라는 분야의 위치를 찾고 그 곳에서 다시 책의 제목으로 위치를 찾는 것과 같다.

이러한 인덱스의 계층 구조는 primary key를 저장하는 인덱스와 secondary key를 저장하는 두 개의 인덱스를 정의하여 구현이 가능하다. 두 개의 계층을 갖는 인덱스의 구조는 아래와 같이 표현된다.

Secondary key를 저장하는 인덱스는 primary key를 저장하는 인덱스와 다르게 중복을 허용한다.

4. Secondary Key

앞에서 서술한 바와 같이 secondary key는 중복이 허용하는 또 다른 key이다. 그러나 secondary key를 이용하면 공학 분야의 위치를 찾고, 그 다음 책을 찾는 것 처럼 두 번의 인덱스를 참조해야 한다. 이러한 문제를 해결하기 위해서는 secondary key가 별도의 저장 공간에 위치한 primary key를 참조하도록 구현하는 것이 아니라, secondary key에 primary key와 레코드의 위치까지 저장하도록 구현하는 방법이 있을 수 있다. 그러나 이러한 구현은 데이터 파일의 레코드가 수정되면 primary key를 저장하는 인덱스뿐만 아니라 secondary key를 저장하는 인덱스까지 수정되어야 하기 때문에 좋은 방법이 아니다.

Secondary key를 이용하는 것은 인덱스 파일의 크기가 큰 경우, 인덱스를 분할하여 메모리에 적재할 수 있다는 장점 이외에도 레코드 검색의 효율성이라는 측면에서 많은 이점이 존재한다. 다음과 같은 쿼리를 실행한다고 가정하면,

group = 'Asia' AND population > 1000000000

primary key 하나만 이용하는 인덱스 체계에서는 데이터 파일의 모든 레코드를 읽어서 하나씩 비교해야 한다. 그러나 group과 population, 두 개를 secondary key로 이용하는 인덱스 체계에서는 group이 Asia에 해당하는 레코드만 읽은 다음, population 필드를 비교하여 AND 연산만 수행하면 된다. 비록 secondary key를 이용하는 방법이 더 복잡하지만, primary key만 이용하는 것에 비하면 하드디스크 접근이 막대하게 감소한다. 파일 시스템을 설계할 때, 하드디스크에 접근하는 것은 메모리 작업과 비교할 수 없을 정도로 막대한 비용이 소모된다는 점을 잊으면 안 된다.

5. Secondary Key의 문제점 및 해결방안

앞에서 논의한 secondary key는 두 개의 문제점을 갖고 있다.

• Secondary key 또한 정렬된 상태로 유지되어야 하기 때문에 데이터 파일에 레코드가 추가되면 primary key뿐만 아니라, secondary key도 재배치 해야 한다.
• 만약 중복된 secondary key가 존재한다면, secondary key를 저장하기 위한 메모리 또는 하드디스크의 저장 공간이 낭비된다.

Secondary key가 갖고 있는 이러한 문제점을 해결하기 위한 몇 가지 구조적 변형이 있다.

1) 배열을 이용한 구조

가장 단순한 해결책은 중복되는 secondary key는 하나만 유지하고, secondary key의 reference field를 배열로 선언하는 것이다. 아래의 그림은 배열을 이용한 구조의 secondary key 인덱스를 나타낸다.

배열을 이용한 구조는 데이터 파일에 레코드가 추가되어도 secondary key에 해당하는 reference field만 재배치하면 되기 때문에 secondary key 인덱스 전체를 재배치하는 것에 비해 비용이 크게 감소한다. 그러나 배열을 이용한 구조는 배열의 크기에 해당하는 수만큼만 reference field를 저장할 수 있고, reference field를 적게 사용하는 secondary key에 대해서는 내부 단편화가 발생할 수 있다. 

2) Inverted list를 이용한 구조

배열을 이용한 구조의 문제점은 공간 할당이 유연하지 않다는 것이다. 연결 리스트를 이용한 구조는 이러한 문제점을 해결하기에 적합하다. 연결 리스트를 이용한 구조에서 secondary key의 reference field는 inverted list라고 불리는 primary key의 집합으로 정의된다. 아래의 그림은 inverted list를 이용한 구조의 논리적 구조를 나타낸다.

연결 리스트를 이용한 구조는 배열을 이용한 구조 처럼 데이터 파일에 레코드가 추가되어도 해당하는 secondary key의 reference field만 재배치하면 된다. 또한, reference field에 원하는 만큼 primary key를 저장하기 위한 공간을 할당할 수 있기 때문에 저장 공간의 제약이나 저장 공간의 낭비가 발생하지 않는다.

Inverted list를 이용한 구조에서 inverted list는 일반적인 연결 리스트와 조금 다르게 구현된다. 아래의 그림은 inverted list를 이용한 secondary key 인덱스의 실제 구조를 나타낸다.

실제로 inverted list를 구현할 때는 포인터를 이용하는 것이 아니라, 각 항목의 상대적인 위치를 나타내는 RRN(Relative Record Number)를 이용한다. 예를 들어, secondary key가 'North America'인 항목의 reference field는 값으로 6을 갖는다. 이는 inverted list의 'Canada'를 가리키며, Canada에 해당하는 항목은 reference 값으로 0을 갖는다. 이는 inverted list 내에서 secondary key로 'North America'를 갖는 두 번째 항목인 'USA'의 위치를 나타낸다.

Inverted list를 이용한 구조는 다음과 같은 이점이 있다.

• Secondary key의 reference field에 원하는 데이터를 저장할 수 있다.

• 내부 단편화가 발생하지 않는다

• 데이터 파일에 레코드가 추가되거나 삭제되어도 secondary key를 수정할 필요가 없으며, inverted list만 수정하면 된다.

• Inverted list는 데이터가 추가되는 순서대로 기록되는 entry sequenced file의 형태로 구현되기 때문에 전체 리스트를 정렬할 필요가 없다. 오직 같은 secondary key를 갖는 항목에 대해서만 정렬을 수행하면 되고, 이러한 정렬 시에는 데이터의 위치를 실제로 바꾸는 것이 아니라, 다음 데이터의 위치를 나타내는 reference 값만 바꾸기 때문에 정렬하는데 드는 비용이 더욱 감소한다.
  

• Inverted list의 각 필드는 고정 길이 필드이기 때문에 구현이 쉽다. 

그러나 Inverted list는 entry sequenced file로 구현되기 때문에 같은 secondary key를 갖는 항목이 물리적으로 근접하게 위치하지 않는다. 이러한 특성은 하드디스크에서 특정 데이터의 위치를 찾는 seek 연산을 더욱 많이 발생하게 한다. 하드디스크에서 발생하는 seek 연산을 줄이기 위해 inverted list를 메모리에 적재하는 방법이 있지만, inverted list의 크기가 매우 클 경우에는 많은 비용이 발생하고 실용적이지 않다. Inverted list의 이러한 단점을 극복하기 위해 인덱스를 페이지 단위로 분리하여 저장하는 B-tree와 보조 저장장치에서 대용량의 인덱스를 관리하기 위한 여러 방법들이 고안되었다.