[데이터베이스] 17. 자료의 탐색(순차 탐색, 이진 탐색, ...)

1. 탐색의 종류

• 기억 공간에 저장된 특정 레코드를 찾아내기 위해서는 탐색하는 과정이 필요하다.

1-1. 순차 탐색(Sequencial Search)

• 선형 검색(Linear Search) = 순차 검색(Sequential Search)
• 순서화되어 있지 않은 경우 사용하며 첫번째 레코드 키 값부터 차례대로 비교하여 검색한다.

1-2. 이진 탐색(Binary Search)

• 제어 검색의 일종이다.
• 반드시 순서화된 파일이어야 검색할 수 있다.
• 탐색 효율이 좋으며 탐색 시간이 적게 소요된다.
• 전체 파일을 두 개의 서브 파일로 분리해 가면서 Key 레코드를 검색하기 때문에 검색회수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어든다.
• 찾고자 하는 Key 값을 파일의 중간 레코드 Key 값과 비교하면서 검색한다.
• 중간 레코드 번호(m) : m=(첫번째 레코드 번호+마지막 레코드 번호)/2

1-3. 보간 탐색

• 찾으려는 레코드가 있을 법한 부분의 키를 택하여 검색하는 방법이다.

1-4. 피보나치 탐색(Fibonacci Search)

• 피보나치 수열에 따라 다음에 비교할 대상을 선정하여 검색하는 방식으로 중간 레코드 번호를 계산하기 위해 가감산만을 이용하기 때문에 효율이 우수하다.

1-5. 블록 탐색(Block Search)

• 데이터 영역을 블록으로 나누고 각 블록마다 최대 레코드 키 값을 Index에 저장한 뒤 이것을 이용하여 찾고자 하는 레코드가 어느 블록에 속하는지를 검색하는 방법이다.