[정보처리기사] [1과목 - 데이터베이스] 5. 자료 구조의 기본 - 검색(Search)

선형 검색(Linear Search)

　- 검색 : 컴퓨터를 이용해서 기억공간에 보관중인 특정 레코드를 찾아내는 작업임

　- 선형 검색(Linear Search)

　　＊ 순서화되어 있지 않은 파일에서 순차적으로 검색하는 방식으로, 찾고자 하는 Key 값을 첫 번째 레코드 Key 값부터 차례로 비교하여 검색하는 방식임

　　＊ 순차 검색(Sequential Search)이라고도 함

　　＊ 프로그램 작성이 가장 쉬움

★★ 제어 검색(Control Search)

　- 제어 검색은 반드시 순서화된 파일이어야 검색할 수 있음

　- 제어 검색 : 한 번의 비교 동작이 끝난 후 비교 대상이 된 레코드를 다음에 비교할 대상을 선택하는 기준으로 이용하여 검색하는 방식

　- ★ 이분 검색(이진 검색, Binary Search)

　　＊ 이분 검색은 전체 파일을 두 개의 서브파일로 분리해 가면서 Key 레코드를 검색하는 방식임

　　＊ 찾고자 하는 Key 값을 파일의 중간 레코드 Key 값과 비교하면서 검색하는 방식임

　　＊ 비교 회수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어듦으로 탐색 효율이 좋고 탐색 시간이 적게 소요됨

　　＊ 중간 레코드 번호  (단, F : 첫번째 레코드 번호, L : 마지막 레코드 번호)

　　＊ 예제 ) 1 ~ 100까지의 숫자 중 15를 찾는 데 걸리는 횟수는?

　　　 ① 첫 번째 값(F)과 마지막 값(L)을 이용하여 중간값 M을 구하여 찾으려는 값과 비교함

　　　　　 (정수만 취함)

　　　 ② 50이 찾으려는 값과 같은지, 아니면 작은지, 아니면 큰지를 확인함.

　　　　　50은 찾으려는 값보다 큼.

　　　　　그러므로 찾으려는 값은 1 ~ 49 사이에 있음 → 1회 비교

　　　 ③ 이제 첫 번째 값은 1이고 마지막 값은 49임

　　　　　찾으려는 값이 50 사이에 있지만 50은 아니므로 49가 마지막 값이 됨

　　　　　다시 중간 값을 구함

　　　　 → 2회 비교

　　　 ④ 25는 찾으려는 값보다 큼.

　　　　　그러므로 찾으려는 값은 1 ~ 24 사이에 있음

　　　　　다시 중간 값을 계산함

　　　　　 → 3회 비교

　　　 ⑤ 12는 찾으려는 값보다 작음

　　　　　그러므로 찾으려는 값은 13 ~ 24 사이에 있음

　　　　　 → 4회 비교

　　　 ⑥ 18은 찾으려는 값보다 큼

　　　　　그러므로 찾으려는 값은 13 ~ 17 사이에 있음

　　　　　 → 5회 비교

　　　 ⑦ 15는 찾으려는 값과 같음

　　　 ※ 총 비교 횟수는 5회 임

　- 피보나치 검색(Fibonacci Search)

　　＊ 피보나치 검색은 피보나치 수열에 따라 다음에 비교할 대상을 선정하여 검색하는 방식임

　　＊ 이분 검색에서는 중간 레코드 번호를 계산하기 위해서 나눗셈이 필요하지만 피보나치 검색은 가감산만을 이용하기 대문에 효율이 우수함

　　　 - 피보나치 수열 : 피보나치 수열은 의 순서를 갖는다. 즉, 1, 1, 2, 3, 5, 8, 13, 21 … 

이다

　- 보간 검색(Interpolation Search)

　　＊ 보간 검색은 찾으려는 레코드가 있음직한 부분의 키를 택하여 검색하는 방식임

　　＊ 선정 레코드 번호 = ( 찾으려는 키값(추측) - 최소키값) / (최대키값 - 최소키값 ) * 레코드 수

　　＊ 찾으려는 레코드 근처에서부터 찾아가기때문에 검색시간이 빠르지만, 예측을 해야 하므로 실제로는 프로그래밍이 불가능함

　- 블록 검색(Block Search)

　　＊ 블록 검색을 위해서는 파일을 구성하는 레코드들을 다음과 같이 구성해 놓아야 함

　　　 - 파일을 구성하는 레코드들을 여러 개의 Block으로 분할하여 Block 단위는 순서화시키고, Block내의 자료는 순서화와 관계없이 저장시킴

　　　 - Index 부분을 두어, 각 Block마다 최대 레코드 키 값을 가지는 레코드 번호를 저장시킴

　　＊ 인덱스를 이용하여 찾고자 하는 레코드가 어느 Block에 속하는지 검색한 후, 해당 Block 내에서는 선형 검색을 함

　　　 - 위와 같이 구성되어 있을 때 39를 검색하기 위해서는 인덱스에서 2, 7, 12가 가리키는 값과 비교하고, 세 번쨰 블록에서 42, 40, 39와 차례로 비교하므로 6번 비교하여 성공함

　- 이진 트리 검색(Binary Tree Search)

　　＊ 이진 트리 검색은 파일을 이진 검색 트리^[각주:1]로 구성하여 검색하는 방식임

　　＊ 검색 과정

　　　 ① 찾고자 한느 레코드 Key 값 X가 이진 검색 트리에 존재하는지 조사하려면 먼저 Root Node와 비교함

　　　 ② 만약 X가 Root Node의 Key 값보다 작으면 왼쪽 Subtree로 검색을 계속하고, 크면 오른쪽 Subtree로 검색을 계속하고, 같으면 검색을 종료함

　　　 ③ i가 0인 경우 검색에 실패한 경우임

　　　　  - 즉 X가 임의의 노드 값과 같지 않아서 왼쪽 또는 오른쪽 자식을 찾아가기 위해 그 노드의 L, L 또는 R, L 포인터를 i에 기억시켰을 때, i에 기억시킨 포인터 값이 Nil Pointer인 경우 찾고자 하는 레코드가 없기 때문

1. 이진 검색 트린느 왼쪽 자식 노드의 값은 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값은 부모 노드의 값보다 큰 값을 갖는 노드들로 구성한 트리 [본문으로]