[파일구조] - 레코드 검색

1. 순차 탐색(Sequential Search)과 이진 탐색(Binary Search)

검색은 파일에서 가장 빈번하게 발생하는 연산이다. 따라서, 파일구조를 설계할 때는 파일 검색 연산을 신중히 구현해야 한다. 파일을 검색하기 위한 방법에는 크게 순차 탐색(sequential search)과 이진 탐색(binary search)이 있다. 순차 탐색의 시간 복잡도는 $O(n)$이며, 이진 탐색 트리에서 이진 탐색을 수행할 때의 시간 복잡도는 $log_2(n)$이다.

일반적으로 순차 탐색보다 이진 탐색의 효율이 더 좋지만 이진 탐색은 데이터가 정렬되어 있어야 한다는 제약 조건이 존재한다. 또한, 가변 길이 레코드 파일에서 이진 탐색을 수행하기 위해서는 파일의 중간 지점을 찾는 방법에 대한 구현도 필요하다.

2. 데이터 정렬

이진 탐색을 이용하기 위해서는 반드시 데이터를 정렬해야한다. 파일의 경우에는 일반적으로 메모리에서 다루어지는 자료보다 데이터의 양이 많기 때문에 효율적인 정렬 알고리즘이 매우 중요하다.

파일은 데이터의 양이 매우 많기 때문에 메모리에 데이터를 모두 적재할 수 없는 경우가 존재한다. 이러한 경우에는 external sorting을 수행해야 하는데, external sorting은 전체 데이터 중에서 일부만 메모리에 적재하여 정렬하고 정렬이 끝나면 디스크에 접근하여 다시 데이터를 메모리에 적재하여 정렬을 수행하기 때문에 메모리에서 정렬을 수행하는 internal sorting에 비해 속도가 매우 떨어진다. 파일 정렬 시, 정렬을 위해 필요한 데이터의 양을 최소화하여 internal sorting을 수행하는 방법으로 key sorting이 있다.

3. Key Sorting과 인덱스 파일(Index File)

Key sorting의 기본 개념은 데이터 파일 자체를 정렬하는 것이 아니라, 데이터 파일에 대해 키-상대 레코드 번호(RRN)으로 구성된 KEYNODE array를 정렬하는 것이다. 일반적으로 데이터 파일에 대한 KEYNODE array는 모든 데이터가 충분히 메모리에 적재될 수 있기 때문에 external sorting 대신 internal sorting을 이용할 수 있다. Key sorting의 구현은 아래와 같다.

int keySort(FixedRecordFile & inFile, char *outFileName) { int numRecs = inFile.numRecs(); RecType obj; KeyRRN *KEYNODES = new KeyRRN[numRecs]; for(int i = 0; i < numRecs; i++) { inFile.readByRRN(obj, i); KEYNODES[i] = keyRRN(obj.key(), i); } sortByKey(KEYNODES); FixedRecordFile outFile(outFileName); for(int i = 0; i < numRecs; i++) { inFile.readByRRN(obj, KEYNODES[i].RRN); outFile.append(obj); } return TRUE; }

위의 코드에서 알 수 있듯이 key sorting을 위해서는 입력 파일을 두 번 읽어야 한다. 하나의 입력 파일을 읽기 위해 디스크에 두 번 접근하는 것은 바람직하지 않다. 또한, 정렬된 KENODE를 참조하여 파일을 정렬된 형태로 다시 쓸 때 입력 파일을 임의 접근(random access) 하기 때문에 정렬 알고리즘의 성능이 떨어지는 단점이 있다.

Key sorting의 이러한 단점을 극복하기 위한 방법으로는 인덱스 파일(index file)을 이용하는 방법이 있다. 인덱스 파일을 이용하여 key sorting의 단점을 극복하는 방법은 매우 단순하다. 바로 인덱스 파일만 정렬하고 원래 데이터 파일은 정렬되지 않은 그대로 놔두는 것이다.