빠른 검색

보조기억장치에 대한 접근비용이 매우 크기 때문에, 이를 최소화할 수 있는 정렬 및 검색 방법이 필요하다.

1. 단순 필드와 레코드 파일에서의 조회

• RRN이나 Byte offset을 알지 못할때, 현재까지 키를 사용한 접근은 순차 탐색을 의미

2. 추측에 의한 검색 : 이진 탐색

• 1000개의 고정길이 레코드를 가지고 있고 키를 사용하여 오름차순으로 정렬된 파일
• Jane Kelly라는 레코드를 이진탐색으로 찾는 방법: 최대 10번 비교

int BinarySearch(FixedRecordFile &file, RecType &obj, KeyType &key)
// 키에 대한 이진 탐색
// 키가 발견되어 진다면, obj는 해당하는 레코드를 포함하고 1을 되돌려 준다.
{
	int low = 0; int high = file.NumRecs() – 1;
	while(low <= high)
	{
	int guess = (high+low)/2;
	file.ReadByRRN(obj.guess);
	if(obj.Key() == key) return 1; // 레코드를 찾은 경우
	if(obj.Key() > key) high = guess –1; // guess 앞부분을 검색
	else low = guess + 1; // guess 뒷부분을 검색
	}
return 0; // 키를 발견하지 못하고 루프를 끝나는 경우
}

이진탐색 vs 순차탐색

• 이진탐색 : 최대 └log2^n┘+1 번 비교, O(log2^n)의 복잡도

• 순차탐색 : 최대 n번 비교, 평균 n/2번 비교
  : O(n)의 복잡도

키정렬

• 메모레엇는 파일로부터 키만을 읽어 이를 정렬하고, 이 키에 대한 새로운 순서에 따라 파일 내 레코드를 재정리(tag sort라고도 함)

키정렬 방법 설명

• 가정 : 고정길이 레코드파일, 헤더 레코드에 전체 레코드 유지
• 알고리즘 :
  ① 디스크에서 키 RRN 쌍을 읽어 keyRRN 객체의 배열(KEYNODES[])에 저장
  ② 메모리상에서 KEYNODES[] 를 정렬한다.
  ③ KEYNODES[] 의 배열 순서대로 입력화일의 레코드를 읽어서 새로운 화일에 기록한다.

void KeySort(FixedRecordFile & inFile, char * outFileName)
{
RecType obj;
KeyRRN * KEYNODEs = new KeyRRN[inFile.NumRecs()];
// 화일을 읽어서 키를 적재
  for(int i=0; i<inFile.NumRecs(); i++)
  {
  inFile.ReadByRRN(obj, i); // 레코드 I를 읽는다 // fread
  KEYNODES[i] = KeyRRN(obj.Key(), i); // 키와 RRN을 키 배열에 넣는다
  }
Sort(KEYNODES, inFile.NumRecs()); // 키 배열을 정렬한다
FixedRecordFile outFile; // 정렬된 키순서로 레코드를 지니게 될 화일
outFile.Create(outFileName); // 새로운 화일을 생성한다
// 정렬된 키 순서로 새로운 화일에 기록한다
  for(int j=0; j<inFile.NumRecs(); j++)
  {
  inFile.ReadByRRN(obj, KEYNODES[j].RRN); // 키 순서로 읽기 / fseek
  outFile.Append(obj); // 키순서로 기록 // fwrite
  }
  
}

키정렬의 한계

1. 새로운 정렬파일을 기록하기 위해 레코드를 두번 읽어야함.
2. 정렬된 키 순서로 파일에 기록할때, 입력파일에 대한 임의탐색이 필요한데, 이는 순차탐색에 비해 많은 시간이 소요

그 밖의 해결책

• 인덱스 파일 : 원본 파일과의 결합에 사용되는 두번째 종류의 파일
• 탐색 : 인덱스파일에서 이진탐색을 수행하고, 인덱스 파일 레코드에 있는 RRN을 사용