2021.06.04 - [이론공부/화일처리및응용] - 화일 처리 및 응용 공부 #17 (인덱스된 순차화일 ,B+트리)
직접 화일
- 임의 접근 화일
- 임의의 레코드 키 값으로 그 레코드를 접근 할 수 있는 화일
- 직접 화일, 직접 접근 화일
- 다른 레코드를 참조하지 않고 특정 레코드 접근이 가능 - 직접 화일의 종류
- 인덱스된 화일
- 인덱스를 이용해 레코드를 접근 - 인덱스된 순차 화일
- 인덱스를 이용한 임의 접근/순차 접근 모두 지원 - 상대 화일
-키와 화일 내 레코드의 상대적 위치를 이용해 레코드를 접근 - 해시 화일
- 키값을 레코드 주소로 변환하여 레코드를 접근
- 협의의 직접 화일
- 인덱스된 화일
상대 화일
- 리코드의 키와 화일 내 레코드의 위치 사이에 설정된 관계를 이용해 레코드를 접근
- 상대 레코드 번호
- 화일이 시작되는 첫 번째 레코드를 기준으로 레코드들에 0,1,2,3 .... N-1을 지정
- 이 RRN을 상대주소 라고함
(레코드의 논리적 순서와 물리적 순서는 무관, 레코드들이 키 값에 따라 물리적으로 정렬되어 있을 필요 없음)
사상함수
사상함수 A
A : 키값 -> 주소
- 레코드 기록 시 : 키값 -> 레코드가 저장될 주소
- 레코드 검색 시 : 키값 -> 레코드가 저장되어있는 주소
- 모든 레코드에 직접 접근이 가능
사상함수(A)의 구현 방법
- 직접 사상
- 디렉터리 검사
- 계산을 이용한 방법 ex) 해싱
직접 사상
절대 주소 이용
- 레코드의 실제 주소를 키값으로 사용
- 화일에 레코드가 처음 저장될 때 레코드의 절대 주소 <실린더 번호, 면 번호, 블록번호>
- 검색시 절대 주소를 이용
장점
- 키 값 -> 주소 변환 과정이 간단하고, 처리 시간이 거의 걸리지 않음
단점
- 물리적 저장 장치에 전적으로 의존
- 물리적 데이터 독립성이 결여 됨 (ex C 에서 D로 옮길때 복잡해짐)
디렉터리 검사
상대 화일 접근을 위해 <키값, 상대주소>쌍을 엔트리로 갖는 테이블, 즉 디렉터리를 유지
레코드 검색
- 디렉터리에서 키 값을 검색하여 그 키 값에 대응되는 레코드 번호로 저장된 레코드를 접근
장점
- 순차 탐색 대비 검색이 빠름(이진 탐색 적용가능)
단점
- 화일 구조 유지를 위해 화일과 디렉터리 재구성이 필요하게 된다
cow를 기준으로 나누고, 다시 dog아래를 기준으로 나눠서 상대주소를 반환 하는 이진 탐색이 가능
해싱(hashing)
계산을 이용한 사상함수 구현법
일반적으로, 주소공간 << 키 값 공간
예) - 10자리 학번
- 가능한 학번과 1:1이 되는 주소 (10^10개)
- 실제 유효 학생수 : 10^4 이하
- 모든 가능한 학번에 빈 레코드 주소를 할당하면
-> 막대한 저장 공간 낭비 발생 (10^10 >> 10^4) - 1.5만개 미만의 레코드 공간을 갖는 화일을 만드는 것이 효율적
ex) 저장주소 = 학번 / 1.5만
직접화일 : 임의의 레코드 키값으로 그 레코드를 접근할 수 있는 화일
사상함수 :
- 레코드 기록 시 : 키값-> 레코드가 저장될 주소
- 레코드 검색 시 : 키값 -> 레코드가 저장되어있는 주소
- 모든 레코드에 직접 접근이 가능
해싱, 해싱관련 용어 정리
- 해싱 함수를 이용하여 키 값을 저장, 주소로 변환하여 그 주소에 레코드를 저장하는것
- 해시 주소 : 해싱 함수가 키 값으로 부터 반환한 변환된 주소
- 해시 화일 : 해싱 기법으로 운영되는 화일
한정된 유효 주소 공간으로 균등하게 분산 시키는것을 주로 이해해야 함
해시 파일 설계시 고려해야할 사항
- 버킷 크기
- 하나의 버킷에 저장할 수 있는 레코드의 수
- 버킷 : 하나의 주소를 가진 저장구역을 말한다, 복수의 레코드를 저장한다 - 적재율
- 총 저장 용량에 대한 실제 저장되는 레코드 수의 비율 - 해싱함수
- 레코드 키 값으로부터 주소를 생성하는 방법 - 오버플로 해결 방법
- 주어진 주소 공간(버킷)이 만원이 된 경우의 해결 방법
해싱함수 사례
- 제산 잔여 해싱
- 중간 제곱 해싱
- 중첩 해싱
- 숫자 추출 방법
- 숫자 이동 변환
- 진수 변환
제산 잔여
제산잔여 해싱의 성능
적당한 성능을 위한 적재율 최대 허용치는 0.7~ 0.8
- n 개의 레코드 -> 1.25n 주소 공간 (80%의 경우)
ex) 레코드 4000개, 적재율 80%
- 주소 공간 = 4,000 /0.8 = 5,000개의 주소 공간 필요
- 제수 : 5003
- 20 이하의 소수 인자를 갖지 않는 수 중 5000에 가장 가까운 수를 선택한 경우
중간제곱 해싱
키 값을 제곱
중간에서 n개의 수를 취함
3x) 레코드가 4000개인 경우
- 최소 4자리의 주소 공간이 필요
- 키를 제곱한 수에서 4자리 수를 취한다
(주소공간이 아주 큰 경우 적절한 조정 인수를 곱해 주소 공간을 조절함)
중첩 해싱
- 키 값을 주소의 크기와 같은 자릿수를 갖는 몇 개의 부분으로 나눔
- 접어서 합을 구함
숫자추출
- 키값이 되는 숫자의 출현 분포를 이용
- 균등하게 분산 사용된 숫자 위치들을 주소 자리 수 만큼 선정 - 키들의 모든 자릿수에 대한 빈도 테이블을 만들어 분석
- 예
- 9자리 레코드 키 값을 분석하여 4개의 균등한 숫자 위치로 9번째 7번째 5번째 2번째 위치가 선정되었다고 가정
주어진 레코드키 : 546032178
변환된 레코드 주소 : 8134
숫자이동 변환
진수 변환
버킷(bucket)
- 레코드 저장이나 검색 시 지시하는 저장공간(주소)
- 하나 이상의 레코드 저장 가능
- 화일 구성하는 버킷 수가 이 화일을 위한 주소 공간이 된다.
버킷크기
- 버킷에 저장할 수 있는 레코드 수
- 한번의 접근으로 버킷 내에 있는 모든 레코드들을 전송할 수 있는 크기로 결정
- 저장 장치의 물리적 특성과 연관되어 있다.
충돌(collision)
- 두개의 상이한 레코드가 똑같은 버킷으로 해싱되는 경우
- 같은 주소로 해싱되어 충돌된 키 값들을 동거자(synonyms)라고 한다.
- 버킷이 만원인 경우에는 충돌이 문제가되어 오버플로가 발생
- 오버플로를 해결하기 위한 추가적인 작업은 해싱 기법의 오버헤드가 된다.
적재 밀도
- 적재 밀도가 높으면
- 삽입 / 검색 시 접근 시간이 길어진다.
(이미 여러 레코드가 지정된 주소에 저장되어 있을 확률이 높아 다른 주소를 검색해야하는 경우 발생하기 때문) - 적재 밀도가 낮으면
- 공간 효율이 떨어짐 - 실험적으로 적재 밀도가 70퍼센트 이상이면 충돌 가능성이 높음
- 30퍼센트의 자유공간을 예비하는것이 바람직하다 - ex) 학생 레코드 검색 시스템
- 학생 수 최대 60,000명, 자유공간 30퍼센트, 버킷크기 12
- 버킷 수 = 60,000/12*10/7 = 7143
충돌과 오버플로
- 키 값 공간이 주소 공간보다 크기 때문에 충돌 발생
- 오버플로(overflow)
- 하나의 홈 주소 또는 홈 버킷으로 충돌된 동거자들을 한 버킷에 모두 저장할 수 없는 경우
홈주소 : 해싱 함수가 생성한 버킷주소 - 해결 방법
1. 선형조사
2. 독립 오버플로 구역
3. 이중 해싱
4. 동거자 체인
5. 버킷 체인
선형조사
- 오버플로 발생시, 홈 주소에서부터 차례로 조사해서 가장 가까운 빈 공간을 찾는 방식
- 해당 주소가 공백인지 아닌지 판별할 수 있게 플래그 사용
선형 조사 저장/검색/삭제
- 저장
- 원형 탐색 : 빈 저장 공간 조사는 홈 주소에서 시작하여 화일 끝에서 끝나지 않고, 다시 화일 시작점으로 돌아가 홈 주소에 도착할때 종료 - 검색
- 레코드 저장 시에 선형 조사 방법을 사용했다면 검색 시에 선형 조사 방법을 사용해야함
- 탐색 키 값을 가진 레코드가 없거나 홈 주소에서 멀리 떨어져있는 경우, 많은 조사 필요 - 삭제
- 삭제로 생긴 빈 공간으로 검색 시 선형 조사가 단절 될 수 있음 -> 삭제 표시가 필요함
(삭제된 자리에 삭제 표시를 해서 선형 조사가 단절되지 않도록 함)
선형조사 단점
- 어떤 레코드가 화일에 없는것을 판단하기위해 조사해야할 주소 수가 적재율이 높을 수록 많아짐
- 적당한 적재율을 유지해야함 - 환치(displacement)
- 한 레코드가 자기 홈 주소를 동거자가 아닌 다른 오버플로된 레코드가 차지함으로 인해 다른 레코드 홈주소에 저장되는것
- 환치는 또다른 환치를 유발
- 탐색할 주소 수의 증가는 삽입/겁색 시간 증가를 야기함
- 대응책으로 처음 화일을 생성할때 2-패스 해시 파일 생성 (tow -pass hash file creation)방법을 이용함.
2 - 패스 해시 화일 생성
- 첫 번째 패스
- 모든 레코드를 해시 함수를 통해 홈 주소에 저장
- 오버플로된 동거자들은 바로 저장하지 않고 별도로 임시 화일에 저장
- 두 번째 패스
- 첫 번째 패스가 모두 끝나면 임시 화일에 저장해 둔 오버플로 동거자들을 선형 조사를 이용해 전부 적재
- 첫 번째 패스가 모두 끝나면 임시 화일에 저장해 둔 오버플로 동거자들을 선형 조사를 이용해 전부 적재
- 1 패스 화일 생성에 비해 훨씬 많은 레코드들이 원래의 자기 홈 주소에 저장됨
- 화일을 생성하기 전에 레코드 키 값들을 미리 알면 효율적
- 화일이 생성된 뒤에 레코드들이 추가될 때는 환치 발생 가능성이 있음
독립 오버플로 구역
- 별개의 오버플로 구역을 할당하여 홈 주소에서 오버플로된 모든 동거자들을 순차로 저장하는 방법
- 장점
- 동거자가 없는 레코드에 대해서는 한번의 홈 주소 접근만으로 레코드를 검색
- 1 패스로 상대 화일을 생성
- 환치 문제가 없음
- 단점
- 오버플로된 동거자를 접근하기 위해서는 오버플로 구역에 있는 모든 레코드를 순차적으로 검색
이중 해싱
- 오버플로된 동거자들을 오버플로 구역으로 직접 해시
- 오버플로 구역에서의 순차 탐색을 피할 수 있음
- 2차 해싱 함수를 이용
- 오버플로된 동거자를 해시하는 함수
- 오버플로된 동거자를 해시하는 함수
- 해싱과정
1. 1차 해싱 함수에 의해 상대 화일로 해시
2. 오버플로가 발생하면 오버플로 구역으로 해시- 오버플로 구역 주소 = (1차 해시주소 + 2차 해시 주소) mod (오버플로 구역 크기)
- 3. 오버플로가 재차 일어나면 선형 탐색을 이용
동거자 체인
- 각 주소마다 링크를 두어 오버플로된 동거자 레코드를 연결하는 방법
- 오버플로가 일어나면 선형 조사나 오버플로 구역을 이용해서 저장한 뒤에 링크로 연결
- 동거자에 대한 접근은 링크로 연결된 동거자들만 조사
- 독립 오버플로 구역에 사용할 수도 있고 원래의 상대화일에 사용할 수도 있음
- 장점:
- 홈주소에서 충돌감소
- 독립 오버플로 구역 사용시 환치 문제가 없음
- 탐색성능 : 동거자체인, 이중해싱, 선형조사 순 - 단점:
- 각 주소가 링크 필드를 포함할 수 있도록 확장해야 함
버킷체인
- 동거자 체인과 비슷
- 홈 버킷에서 동거자 오버플로가 일어나면 별개의 버킷을 할당받아 오버플로된 동거자를 저장하고 홈버킷에 이 버킷을 링크로 연결
- 장점:
- 재 해싱불필요
- 독립 오버플로 구역 사용시 환치 문제가 없음 - 단점 :
- 각 주소가 링크 필드를 포함할 수 있도록 확장해야 함
- 공간 낭비 가능성이 있음
'개념정리 > 화일처리및응용' 카테고리의 다른 글
| 화일 처리 및 응용 공부#20 (텍스트를 위한 화일) (0) | 2021.06.30 |
|---|---|
| 화일처리 및 응용 공부 #19 (직접화일2) (0) | 2021.06.23 |
| 화일 처리 및 응용 공부 #17 (인덱스된 순차화일 ,B+트리) (0) | 2021.06.04 |
| 화일 처리 및 응용 공부 #16 (트라이) (0) | 2021.05.31 |
| 화일 처리 및 응용 공부 #15 (B*트리) (0) | 2021.05.27 |