クイック検索

セカンダリメモリへのアクセスコストが非常に高いため、並べ替えおよび取得方法が必要である。

1.単純フィールドとレコードファイルのクエリー

2.推測検索：バイナリ検索

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シーケンスナビゲーション

キーのソート

キーソートの説明

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
  }
  
}

キー・ソートの制限

その他のソリューション