저장된 데이타 파일로 부터 원하는 정보를 빼내는 과정을 검색(검출)이라 한다. 주기억 장치에 저장한 파일이나 표로부터 필요한 자료를 찾는 내부검색(Internal Searching)과 보조기억 장치에 있는 파일이나 표로부터 자료를 찾는 외부검색(External Searching)이 있습니다.

검색(Searching)에 대해 알아 보겠습니다.

8-1. 검색의 종류(Searching)의 종류

8-1-1. 선형검색(Linear 또는 Sequential Searching)

메모리를 가장 적게 차지하는 가장 간단한 Serching방법으로 처음부터 하나씩 순서대로 비교하여 원하는 내용을 찾는 방식. 하나의 레코드를 처리하면 다음 번에 처리할 레코드의 위치가 결정 되므로 Pointer가 필요 없르며, 자료가 키값 순으로 저장되어 있지 않아도 검색이 가능하다. 평균 검색 길이는 (n+1) / 2회로 검색 시간이 오래 걸린다.

8-1-2. 제어검출(Control Searching)

주어진 키와 표의 어느 한키를 비교한 후 그 결과가 같은가 같지 않은가에 따라 작업 진행 여부를 결정한다.

(1) 이진검출(Binary Searching)

Ascending이나 Descending로 반드시 순서있게 정리되어 있어야 하며 연접리스트(Array)를 검색할 때 검색 장이 가장작다. 평균 조합 횟수는 0[log₂ n]

(2) Fibonacci검출

Fibonacci수열에 따라 다음에 비교할 대상을 선정하여 검출을 진행하는 검출방법

(3) 보간(Interpolation)검출

주어진 키와 일치하는 것이 있을만한 부분의 키를 선택하여 비교 검색한다.

8-1-3. 블럭검출(Block Searching)

일정한 수의 레코드들을 갖는 블럭(Block)을 구성하여 Index를 구성한 후 주어진 Key를 검색한다. 블럭(Block)단위로 순서있게 정리 되어 있어야 한다. 블록의 크기는 으로 한다.

8-1-4. 이진 검색트리(Binary Searching Tree)

크기의 변화가 많은 자료의 검색시 유용하며 비교적 빠르게 필요한 자료를 찿을 수 있다. 포인터를 조정하여 레코드의 삽입과 제거를 비교적 ,효율적으로 수행할 수 있다

8-1-5. 해싱(Hashing) 또는 스캐터 서어칭(Scatter Searching)

표나 파일을 구성한 각 레코드의 키이 계수적인 성질을 분석하여 레코드의 저장 주소를 계산, 산출하고 그들을 그 주소의 기억 공간에 보관하며, 같은 과정을 반복하여 주어진 키의 레코드를 검출하거나 기존 레코드의 제거, 새로운 레코드의 삽입 등을 수행하는 방법(Key Address변환법). 추가, 삭제가 쉽고, 검색 속도도 빠르다.

【보기】해싱함수

Chained Scatter	Pointer이용
Open Scatter	Bucket을 늘림. Pointer사용 않함.
Bucket	Hash Function에 의해 계산된 값에 데이터를 기억시키기 위해 마련한 장소.

【참고】테이블 서칭(Table Searching)

(1) 스윞서-치(Sweep Search)

(2) 스캐터 서-치(Scatter Search)

(3) 아이템 서-치(Item Search)

해싱함수의 종류

① 제산방법(Division)

키를 어떤 양의 정수로 나눈 나머지를 그 키의 홈 주소로 사용.

② 제곱방법(mid – square)

키를 제곱하고 이 값의 중간부분의 값을 취하여 홈주소로사용.

③ Folding

키를 여러 부분으로 나누고 각 부분의 값을 모두 더하거나 EX-OR하여 홈주소를 얻는다.

④ Radix변환방법

어떤 진법으로 표현된 주어진 키를 다른 진법으로 보고 키를 변환하여 홈주소를얻는 방법.

⑤ Algebraic Coding

⑥ 계수분석법(Digit Analysis)

⑦ 무작위 방법(Random Method)

---

이상 “검색(Searching)”에 대해 알아 보았습니다.