05. Record Search and Insert

 

5. 1. Record Search

 

- 저장된 레코드에서 필요한 레코드를 어떻게 찾을 수 있을까?

 

 

1) Sequential Search -> O(n)

 

- Definition: 원하는 레코드를 찾기 위해 처음부터 검색.

 

- 성능평가방법: Read 함수의 호출 수로 측정. (메모리 내에서 비교시간은 무시합니다.)

 

- Non Blocking과 Blocking 2가지 방법이 있습니다.

 

 

 

- Blocking이 Seek Time을 줄여서 성능개선을 가져오지만 두 방법 모두 검색에 소요되는 시간은 O(n)입니다.

 

- Pros: 프로그래밍이 쉽고, 파일의 형태를 단순하게 할 수 있다.

 

- Record의 개수가 적은 파일들에서 사용합니다.

 

 

2) Direct Access -> O(1)

 

- Definition: 원하는 레코드의 시작위치를 찾아서 검색.

 

- RRN(Relative Record Number): 파일의 시작에 대한 Record의 상대적인 위치.

 

 

- Variable Length Record X , Fixed Length Record O.

 

- Variable Length Record에서 사용하려면 각 Record의 길이를 알아야 하기에,

 

  각 레코드의 시작위치인 Index를 필요로 합니다.

 

- Byte Offset = n X r. [n is RRN of Records / r is a Byte of Record]

 

---

 

5. 2. Record Insertion and Deletetion

 

- 레코드의 데이터를 삭제하고 추가하는 방법.

 

 

1) Fixed Length Record.

 

- 삭제된 레코드를 List를 이용해서 연결하며, List 끝 부분은 -1로 표현합니다.

 

- 모든 노드의 삽입과 삭제가 List 한쪽 끝에서 발생.

 

 

 

2) Variable Length Record.

 

- Length Indicator를 사용합니다.

 

- 새로운 데이터가 들어오게 되면, Length Indicator를 보면서 충분히 큰 Record를 찾습니다.

 

 

---