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

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

1. Class TextIndex

인덱스 파일을 구현하기에 앞서, TextIndex라는 인덱스를 저장하는 자료구조를 정의한다. TextIndex는 일정 수의 인덱스들을 저장하는 자료구조로써, 인덱스의 추가, 제거, 검색 등의 연산을 갖는다. TextIndex의 class 정의는 아래와 같다.

class TextIndex { public: TextIndex(int maxKeys = 100, bool unique = true); ~TextIndex(); int Insert(const char *key, int recAddr); int Remove(const char *key); int Search(const char *key) const; protected: int maxKeys; int numKeys; char **keys; int *recAddrs; int Find(const char *key) const; int Init(int maxKeys, bool unique); bool unique; };

2. Insert 함수

TextIndex의 insert 함수는 인덱스를 구성하는 키 값과 레코드 주소를 인자로 받아 인덱스를 메모리에 저장한다. 그러나 TextIndex의 insert 함수는 원하는 위치에 데이터를 저장하는 것이 아니라, 정렬된 순서를 유지하기 위해 키 값에 따라 데이터를 특정 위치에 추가한다.

int TextIndex::Insert(const char *key, const int recAddr) { int i; int index = Find(key); if (unique && index >= 0) { return FALSE; } if (numKeys == maxKeys) { return FALSE; } for (i = numKeys - 1; i >= 0; i--) { if (strcmp(key, keys[i]) > 0) { break; } keys[i + 1] = keys[i]; recAddrs[i + 1] = recAddrs[i]; } keys[i + 1] = strdup(key); recAddrs[i + 1] = recAddr; numKeys++; return TRUE; }

위의 insert 함수는 인덱스를 키 값에 따라 인덱스를 오름차순으로 보관한다. 함수의 구현에 사용된 strdup는 소스 문자열의 크기만큼 메모리를 동적할당한 후에 할당된 공간에 소스의 값을 넣은 후, 첫 주소를 반환하는 함수이다.

3. Remove 함수

TextIndex의 remove 함수는 인자로 전달받은 키 값에 해당하는 인덱스를 TextIndex에서 제거하는 동작을 한다. 제거하려는 인덱스를 발견하면 해당 인덱스의 다음 위치부터 한 칸씩 shift-left한다.

int TextIndex::Remove(const char *key) { int index = Find(key); if (index < 0) { return FALSE; } for (int i = index; i < numKeys; i++) { keys[i] = keys[i + 1]; recAddrs[i] = recAddrs[i + 1]; } numKeys--; return TRUE; }

3. Search 함수

TextIndex의 search 함수는 구현이 매우 간단하다. Search 함수는 TextIndex의 private 멤버 함수인 find를 호출하여 인자로 전달받은 key 값에 해당하는 인덱스에 저장된 레코드 주소를 반환한다.

int TextIndex::Search(const char *key) const { int index = Find(key); if (index < 0) { return index; } return recAddrs[index]; }

4. Find 함수

TextIndex의 find 함수는 인자로 전달받은 키 값에 해당하는 인덱스의 위치를 반환하는 함수로써, TextIndex의 모든 연산에서 이용된다. TextIndex의 find 함수는 순차 탐색으로도 구현할 수 있지만, TextIndex는 고정 길이 데이터를 정렬된 상태로 저장하기 때문에 이진 탐색으로 구현하였다.

int TextIndex::Find(const char * key) const { int low = 0; int high = numKeys - 1; int mid = -1; while (low <= high) { mid = (low + high) / 2; if (strcmp(keys[mid], key) > 0) { high = mid - 1; } else if (strcmp(keys[mid], key) < 0) { low = mid + 1; } else { return mid; } } return -1; }