이분 검색
이분 검색(이진 검색,Binary Search): 전체 파일을 두 개의 서브파일로 분리해 가면서 검색하는 방식
- 반드시 순서화된 파일이어야 검색 가능
- 찾고자 하는 값을 파일의 중간 레코드 값과 비교하면서 검색
- 비교할수록 검색 대상이 되는 데이터의 수가 절반으로 줄어듦
해싱
해시 테이블(Hash Table)이라는 기억공간을 할당하고 해시 함수를 이용하여 해시 테이블 내의 홈 주소를 계산한 후 해당 기억장소에 저장하거나 검색 작업 수행
해시 테이블
- 한 개 이상 보관할 수 있는 버킷들로 구성된 기억공간
- 보조기억장치에 구성할 수도 있고 주기억장치에 구성할 수도 있음
버킷(Buchet)
: 하나의 주소를 갖는 파일의 한 구역
: 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미함
슬롯(Slot)
: 한 개의 레코드를 저장할 수 있는 공간
: n개의 슬롯이 모여 하나의 버킷 형성
Collision(충돌 현상)
: 서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상
Synonym
: 충돌로 인해 같은 Home Address를 갖는 레코드들의 집합
Overflow
: 계산된 Home Address의 Bucket 내에 저장할 기억공간이 없는 상태
: Bucket을 구성하는 Slot이 여러 개일 때 Overflow 발생하지 않을 수 있음
❗ 해싱 함수
제산법(Division)
: 레코드 키(K)를 해시표의 크기보다 큰 수 중에서 가장 작은 소수(Q)로 나눈 나머지를 홈 주소로 삼는 방식
: h(K) = K mod Q
제곱법(Mid-Square)
: 레코드 키 값을 제곱한 후 그 중간 부분의 값을 홈 주소로 삼는 방식
폴딩법(Folding)
: 레코드 키 값을 여러 부분으로 나눈 후 각 부분의 값을 더하거나 XOR한 값을 홈 주소로 삼는 방식
기수 변환법(Radix)
: 키 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수는 절단하고, 이를 다시 주소 범위에 맞게 조정하는 방법
대수적 코딩법(Algebraic Coding)
: 키 값을 이루고 있는 각 자리의 비트 수를 한 다항식의 계수로 간주
: 이 다항식을 해시표의 크기에 의해 정의된 다항식으로 나누어 얻은 나머지 다항식의 계수를 홈 주소로 삼는 방식
숫자 분석법(Digit Analysis, 계수 분석법)
: 키 값을 이루는 숫자의 분표를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방식
무작위법(Random)
: 난수를 발생시켜 나온 값을 홈 주소로 삼는 방식
