07. Placement Strategies and Binary Search

 

7. 1. Placement Strategies

 

- Placement Strategies(배치 전략들): 어떤 Record에 데이터를 넣을까? 결정하는 알고리즘.

 

 

1) First-Fit Placement Strategy(최초 적합) 

 

    : 빈 공간(Available List)을 보면서 충분히 큰 공간을 찾아,

 

    처음부터 탐색하여 가능한 한 최대한 앞에 Record를 삽입.

 

2) Best-Fit Placement Strategy(최적 적합)

 

    : 빈 공간(Available List)을 크기에 따라 Ascending Order로 정리하고,

 

    삽입할 Record를 포함할 정도로 큰 것 중에서 제일 작은 Record Slot에 삽입.

 

3) Worst-Fit Placement Startegy(최악 적합)

 

    : 빈 공간(Available List)을 크기에 따라 Descending Order로 정리하고,

 

    삽입할 Record를 항상 가장 큰 Record Slot에 삽입.

 

---

7. 2. Binary Search

 

- Record Search에서 Sequential Search, Direct Access 외에도 Binary Search를 사용할 수 있습니다.

 

- Binary Search -> O(log2 n)

 

- Definition: 각 Record에 비교를 할 수 있는 Key가 존재하고,

 

  각 Key를 Ascending Order로 정리한 뒤, Binary Search Algorithm을 적용합니다.

 

- Algorithm.

int BinarySearch(FixedRecordFile &file, RecType &obj, KeyType &key)

{

             int low = 0; int high = file.NumRecs() – 1;

             while(low <= high)

             {

                           a) int guess = (high+low)/2;

                           b) file.ReadByRRN(obj.guess);

                           c) if(obj.Key() == key) return 1; // Key O.

                           d) if(obj.Key() > key) high = guess –1;

                           e) else low = guess + 1;

             }

             return 0; // Key X.

}

 

 

1) low는 검색하는 레코드 묶음에서 가장 낮은 RRN값을,

 

  high는 검색하는 레코드 묶음에서 가장 높은 RRN을 의미합니다.

 

  초기값은 low = 0, high는 레코드 전체 개수 – 1 입니다.

 

2) low <= high일 때, 알고리즘이 동작하게 되며,

 

   Key를 찾으면 해당하는 레코드와 1을, Key를 찾지 못하면 0을 반환합니다.

 

3) a)에서 guess로 low, high의 중간값을 찾고,

 

   b)와 c)로 읽어온 Key값과 찾고자 하는 Key 값이 같은지 확인합니다.

 

   같다면, obj.guess로 찾고자하는 Record를 반환하고, 알고리즘을 종료합니다.

 

4) 만약 같지 않고 guess 값이 Key 값보다 크면 d)를 적용시켜 guess값을 감소시키고,

 

   Key 값보다 작다면 e)를 적용시켜 guess 값을 증가시킵니다.

 

- Binary Seach는 데이터를 정렬해서 가져야 하는 문제점을 가지고 있습니다.

 

---