1. 이분 검색
- 전체 파일을 두 개의 서브 파일로 분리해가면서 Key 레코드를 검색하는 방식
- 반드시 순서화된 파일이어야 검색할 수 있음
- 찾고자 하는 Key 값을 파일의 중간 레코드 Key 값과 비교하면서 검색
- 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어듦으로 탐색 효율이 좋고 탐색 시간이 적게 소요
![]() - F : 첫 번째 레코드 번호 - L : 마지막 레코드 번호 |
2. 해싱
- 키- 주소 변환 방법
- 해시 테이블이라는 기억공간을 할당
- 해시 테이블 Hash Table : 레코드를 한 개 이상 보관할 수 있는 버킷들로 구성된 기억공간, 보조기억장치에 구성할 수 있고 주기억장치에 구성할 수 있음
- 버킷 Bucket
- 하나의 주소를 갖는 파일의 한 구역
- 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미
- 슬롯 Slot
- 한 개의 레코드를 저장할 수 있는 공간
- n개의 슬롯이 모여 하나의 버킷을 형성
- 충돌현상 Collision
- 서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상
- 충돌현상 해결 방법
- 체이닝 Chaining : Collision이 발생하면 버킷에 할당된 연결 리스트에 데이터를 저장하는 방법
- 개방 주소법 Open Addressing : Collision이 발생하면 순차적으로 그 다음 빈 버킷을 찾아 데이터를 저장하는 방법
- 재해싱 Rehashing : Collision이 발생하면 새로운 해상 함수로 새로운 홈 주소를 구하는 방법
- 동의어 Synonym
- 충돌로 인해 같은 Home Address를 갖는 레코드들의 집합
- 오버플로 Overflow
- 계산된 Home Address의 Bucket 내에 저장할 기억공간이 없는 상태
- Bucket을 구성하는 Slot이 여러 개 일 때 Collsion은 발생해도 Overflow는 발생하지 않을 수 있음
- 버킷 Bucket
- 해시 테이블 Hash Table : 레코드를 한 개 이상 보관할 수 있는 버킷들로 구성된 기억공간, 보조기억장치에 구성할 수 있고 주기억장치에 구성할 수 있음
- 해시 함수를 이용하여 레코드 키에 대한 해시 테이블 내의 홈 주소를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행하는 방식
- 해싱 함수 Hashing Function
- 제산법 Division : 레코드 키(K)를 해시표의 크기보다 큰 수 중에서 가장 작은 소수(Prime, Q)로 나눈 나머지를 홈 주소로 삼는 방식, h(K) = K mod Q
- 제곱법 Mid-Square : K는 제곱한 후 그 중간 부분의 값을 홈 주소로 삼는 방식
- 폴딩법 Folding : L를 여러 부분으로 나눈 후 각 부분의 값을 더하거나 XOR(배타적 논리합)한 값을 홈 주소로 삼는 방식
- 기수 변환법 Radix : 키 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수는 절단하고, 이를 다시 주소 범위에 맞게 조정하는 방법
- 대수적 코딩법 Algebraic Coding : 키 값을 이루고 있는 각 자리의 비트 수를 한 다향식의 계수로 간주, 다항식을 해시표의 크기에 의해 정의된 다항식으로 나누어 얻은 나머지 다항식의 계수를 홈 주소로 삼는 방식
- 숫자 분석법, 계수 분석법 Digit Analysis : 키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방식
- 무작위법 Random : 난수를 발생시켜 나온 값을 홈 주소로 삼는 방식
- 해싱 함수 Hashing Function
'Study > EIP' 카테고리의 다른 글
[정보처리기사 필기] 데이터 입출력 구현 - 033. 절차형 SQL (0) | 2025.01.24 |
---|---|
[정보처리기사 필기] 데이터 입출력 구현 - 032. 데이터베이스 개요 (0) | 2025.01.24 |
[정보처리기사 필기] 데이터 입출력 구현 - 030. 정렬 Sort (0) | 2025.01.23 |
[정보처리기사 필기] 데이터 입출력 구현 - 029. 트리 Tree (0) | 2025.01.23 |
[정보처리기사 필기] 데이터 입출력 구현 - 028. 자료 구조 (0) | 2025.01.23 |