정보처리산업기사 - 데이터베이스 이해 - 검색 (이분 검색 / 해싱)

※ 공부 내용의 복습 개념으로 정리된 글입니다. - 출처 시나공 

 

이분 검색

• 이분 검색(이진 검색, Binary Search)은 전체 파일을 두 개의 서브파일로 분리해가면서 Key 레코드를 검색하는 방식입니다.
• 이분 검색은 반드시 순서화된 파일이어야 검색할 수 있습니다.
• 찾고자 하는 Key 값을 파일의 중간 레코드 Key 값과 비교하면서 검색합니다.
• 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어듦으로 탐색 효율이 좋고 탐색 시간이 적게 소요됩니다.
• 중간 레코드 번호 !!M = \frac{(F+L)}{2}!! (단, F : 첫 번째 레코드 번호, L : 마지막 레코드 번호)

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

1. 첫 번째 값(F)과 마지막 값(L)을 이용하여 중간값 M을 구하여 찾으려는 값과 비교합니다.
   !!M = \frac{1+100}{2} = 50.5!! → 50(정수만 취합니다.)
   
   
2. 50이 찾으려는 값과 같은지, 아니면 작은지, 아니면 큰지를 확인합니다. 50은 찾으려는 값보다 큽니다. 그러므로 찾으려는 값은 1 ~ 49 사이에 있습니다. → 1회 비교
   
   
3. 이제 첫 번째 값은 1이고 마지막 값은 49입니다. 찾으려는 값이 50 사이에 있지만 50은 아니므로 49가 마지막 값이 됩니다. 다시 중간값을 구합니다.
   !!M = \frac{1+49}{2} = 25!! → 2회 비교
   
   
4. 25는 찾으려는 값보다 큽니다. 그러므로 찾으려는 값은 1 ~ 24 사이에 있습니다. 다시 중간값을 계산합니다.
   !!M = \frac{1+24}{2} = 12.5!! → 12 → 3회 비교
   
   
5. 12는 찾으려는 값보다 작습니다. 그러므로 찾으려는 값은 13 ~ 24 사이에 있습니다.
   !!M = \frac{13+24}{2} = 18.5!! → 18 → 4회 비교
   
   
6. 18은 찾으려는 값보다 큽니다. 그러므로 찾으려는 값은 13 ~ 17 사이에 있습니다.
   !!M = \frac{13+17}{2} = 15!! → 5회 비교
   
   
7. 15는 찾으려는 값과 같습니다.
   ※ 총 비교 횟수는 5회입니다.

 

 

728x90

 

해싱

해싱(Hashing)은 해시 테이블(Hash Table)이라는 기억공간을 할당하고, 해시 함수(Hash Function)을 이용하여 레코드 키에 대한 해시 테이블 내의 홈 주소(Home Address)를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행하는 방식입니다.

 

해싱 테이블(Hash Table)

레코드를 한 개 이상 보관할 수 있는 버킷들로 구성된 기억공간으로, 보조기억장치에 구성할 수도 있고 주기억장치에 구성할 수도 있습니다.

• 버킷(Bucket)
  • 하나의 주소를 갖는 파일의 한 구역을 의미합니다.
  • 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미합니다.
• 슬롯(Slot)
  • 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷을 형성합니다.
• Collision(충돌 현상)
  • 서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상입니다.
• Synonym
  • 충돌로 인해 같은 Home Address를 갖는 레코드들의 집합입니다.
• Overflow
  • 계산된 Home Address의 Bucket 내에 저장할 기억공간이 없는 상태로, Bucket을 구성하는 Slot이 여러 개일 때 Collision은 발생해도 Overflow는 발생하지 않을 수 있습니다.

해싱 함수(Hashing Function)

• 제산법(Division)
  • 레코드 키(K)를 해시표(Hash Table)의 크기보다 큰 수 중에서 가장 작은 소수(Prime, Q)로 나눈 나머지를 홈 주소로 삼는 방식, 즉 h(K) = K mod Q입니다.
• 제곱법(Mid-Square)
  • 레코드 키 값(K)을 제곱한 후 그 중간 부분의 값을 홈 주소로 삼는 방식입니다.
• 폴딩법(Folding)
  • 레코드 키 값(K)을 여러 부분으로 나눈 후 각 부분의 값을 더하거나 XOR(배타적 논리합)한 값을 홈 주소로 삼는 방식입니다.
• 기수 변환법(Radix)
  • 키 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수는 절단하고, 이를 다시 주소 범위에 맞게 조정하는 방법입니다.
• 대수적 코딩법(Algebraic Coding)
  • 키 값을 이루고 있는 각 자리의 비트 수를 한 다항식의 계수로 간주하고, 이 다항식을 해시표의 크기에 의해 정의된 다항식으로 나누어 얻은 나머지 다항식의 계수를 홈 주소로 삼는 방식입니다.
• 숫자 분석법(Digit Analysis, 계수 분석법)
  • 키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방식입니다.
• 무작위법(Random)
  • 난수(Random Number)를 발생시켜 나온 값을 홈 주소로 삼는 방식입니다.