[DB-29] 자료구조 - 검색

1. 검색기법의 종류

• 선형 검색 (Linear Search) : 순차 검색으로 프로그램 작성이 쉬움
• 제어 검색 (Control Search) : 순서화된 파일이어야 검색 가능

2. 제어 검색 

- 이진 검색(binary search)

• 일정한 순서로 배열된 레코드를 2개 부분으로 되풀이하여 나누어서, 한 부분은 버리고 남은 부분을 검색하는 방법
• 자료가 반드시 정렬되어 있어야 함

- 보간(Interpolation) 검색

• 찾고자 하는 키가 있음 직한 위치를 추정하여 검색

- 피보나치 검색

- 블록 검색

- 이진트리 검색

3. 해싱 (Hashing)

• 키 값으로부터 레코드가 저장되어 있는 주소를 직접 계산하여, 산출된 주소로 바로 접근하는 방법. 키-주소 변환 방법이라고도 함
• 검색 방법 중 속도는 가장 빠르지만 충돌 현상 시 오버플로우 해결의 부담이 과중되며 많은 기억공간을 요구하는 검색 방법

해시 테이블

• 킷(bucket) : 하나의 주소를 갖는 파일의 한 구역을 의미하며, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미
• 슬롯(slot) : 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷을 형성
• 충돌(collision) : 레코드를 삽입할 때 2개의 상이한 레코드가 똑같은 주소로 해싱되는 것을 의미
• 동의어(synonym) : 해싱 함수의 값이 같은 키들의 집합

4. 해싱 함수의 종류

• 중간 제곱(mid-square) 방법 : 레코드의 키를 제곱한 후 그 중간 부분의 값을 목적 주소로 사용하는 방법
• 숫자 분석(digit analysis) 방법 : 모든 키들 내에서 각 자리별로 어떤 분포인지를 조사하여 비교적 고른 분포를 나타내는 자릿수를 필요한 만큼 선택하여 목적 주소로 사용
• 제산(division) 방법 : 레코드의 키를 해시 테이블의 크기보다 큰 소수로 나누는 방법
• 중첩(접지) 방법(Folding method) : 주어진 키를 여러 부분으로 나누고, 각 부분의 값을 더하거나 배타적 논리함(XOR : Exclusive OR) : 연산을 통하여 나온 결과로 주소를 취하는 방법
• 계수 분석 방법(Digit Analysis Method)
• 기수(Radix) 변환법

5. 오버플로 처리방법

• 재 해싱 방법(Rehashing) : 여러 개의 해싱 함수를 준비하였다가 충돌 발생 시 새로운 해싱 함수를 적용하여 새로운 해시표를 생성
• 개방 주소법(Open Addressing) : 충돌이 발생했을 때 순서대로 다음 버킷에 저장
• 체인 방법 : 오버플로우 발생 시 이를 별도의 기억공간에 두고 링크로 연결