7장 인덱스된 순차 화일.

Presentation on theme: "7장 인덱스된 순차 화일."— Presentation transcript:

1 7장 인덱스된 순차 화일

2  인덱스된 순차 화일의 구조 순차 화일 : 순차 접근 방법 결합 직접 화일 : 직접 접근 방법 구조
순차 데이타 화일 : 순차적으로 정렬 인덱스 : 화일에 대한 포인터

3 ▶ 인덱스된 순차 화일의 예 이원 탐색 트리의 인덱스 구조를 가진 인덱스된 순차 화일의 예

4 ▶ 구현 방법 삽입, 삭제시 정적 인덱스(static index) 방법 순차 데이타 화일의 레코드 순서 유지 방법
인덱스 갱신 방법 정적 인덱스(static index) 방법 인덱스의 내용 변경, 구조 불변 오버플로우 구역 사용 인덱스 : 하드웨어 의존적 설계 보조기억장치의 물리적 특성(실린더, 트랙) IBM의 ISAM

5 ▶ 구현 방법 동적 인덱스(dynamic index) 방법 인덱스, 데이타 화일 : 블럭 블럭 : 예비 공간 인덱스
오버플로우 → 분열(split) 언더플로우 → 합병(merge) 인덱스 B+-트리 하드웨어 독립적 IBM의 VSAM

6  정적 인덱스 방법 정적인 구현 기억장치의 물리적 특성에 기반

7 ▶ 데이타 화일 기본 구역(prime area) 오버플로우 구역 각 실린더 분리된 화일 : 추가적인 삽입
트랙 0 : 트랙의 레코드에 대한 인덱스 트랙 1-n : 데이타 레코드 오버플로우 구역 분리된 화일 : 추가적인 삽입 오버플로우 포인터 = <실린더, 트랙, 레코드 번호> 실린더 당 오버플로우 구역 또는 한 화일당 한 오버플로우 구역

8 ▶ 인덱스 화일 엔트리 = <키 값, 포인터(실린더 번호, 트랙 번호)> 마스터 인덱스 실린더 인덱스 트랙 인덱스
최상위 레벨 인덱스 (주기억장치에 상주) <최고키값, 포인터> 실린더 인덱스 <최고키값, 실린더 번호> 트랙 인덱스 실린더에 저장된 레코드들에 대한 인덱스 트랙 0에 위치 <최저키값, 트랙 번호>

9 ▶ 정적 인덱스 방법 예 정적 인덱스 방법으로 구성된 인덱스된 순차 화일

10 ▶ 갱신 연산 (삽입) 가정 : 각 트랙 : 5 레코드, 40 % 자유공간 ① INSERT 김수철 INSERT 강원구
가정 : 각 트랙 : 5 레코드, 40 % 자유공간 ① INSERT 김수철 INSERT 강원구 ★ 트랙의 각 항목은 오름차순 유지

11 ▶ 갱신 연산 (삽입) ② INSERT 김시만 ★ 오버플로우 구역 - 기본구역과는 별개의 실린더

12 ▶ 갱신 연산 (삽입) ③ INSERT 남창원 INSERT 나용선 INSERT 나원규
★ 레코드의 순서 - 기본 트랙의 항목에 오버플로우된 항목도 포함하여 순서유지 기본 데이타 화일 실린더 1 트랙 1 2 3 강석오 1 김시만 op1 김연주 2 남창원 op2 문봉기 3 강 석오 김 연주 문 봉기 강 원구 나 민영 안 기영 강 인희 나 용선 유 성렬 김 성기 김 수철 나 원규 남 윤희 실린더 7 오버플로 구역 트랙 1 2 3 김 시 만 남 창 원

13 ▶ 갱신 연산 (삽입) ④ INSERT 김성복 ★오버플로우 구역의 레코드 : 체인으로 연결
<레코드, 해당 트랙의 다음 오버플로우 레코드에 대한 포인터>

14 ▶ 검색 직접 검색 순차 검색 마스터 인덱스 → 실린더 인덱스 → 실린더 주소 트랙 인덱스 → 트랙 포인터
포인터 = 데이타 구역의 트랙 데이타 트랙의 순차 탐색 포인터 = 오버플로우 구역 오버플로우 체인 탐색 순차 검색 기본 데이타 트랙 검색 오버플로우 체인 접근

15 ▶ 검색 성능 기본 구역의 레코드 접근 : 4회 오버플로우 구역 : 3 + k 재구성 인덱스 화일 : 2 트랙 인덱스 : 1
데이타 트랙 : 1 오버플로우 구역 : 3 + k 체인의 k번째 : k 재구성 삽입 빈번 → 긴 체인(성능 저하) 화일 관리자의 주기적 재구성 순차적 완독 재기록

16 ▶ 삭제 동적 삭제 삭제 표시 물리적 제거 ① 오버플로우 구역 - 체인 조정 ② 체인의 첫 레코드 - 트랙 인덱스 수정
③ 기본 구역 큰 키값의 레코드는 한자리씩 이동 오버플로우 레코드가 있는 경우 체인의 첫 레코드가 기본구역 이동 ②의 작업 삭제 표시 주기적인 쓰레기 수집(garbage collection)

17  ISAM 화일 IBM의 ISAM(Indexed Sequential Access Method)
특정 하드웨어의 특성에 맞도록 설계 장점 접근 시간 단축 기억 공간의 효율성 단점 기억장치의 유형 변경 또는 화일의 복사시 문제

18 (1) ISAM 화일의 구조 기본 데이타 구역 인덱스 구역 독립된 오버플로우 구역 데이타 레코드 저장 실린더 화일의 첫 실린더
트랙 0 : 트랙 인덱스 (기본구역과 오버플로우구역에 대한 포인터) 트랙 1~(n-1) : 고정 크기 레코드 (오름차순) 트랙 n : 실린더 오버플로우 구역 인덱스 구역 화일의 첫 실린더 실린더 인덱스 : 실린더를 지시 독립된 오버플로우 구역 화일의 마지막 실린더 실린더 오버플로우 구역의 오버플로우

19 ▶ 실린더의 트랙 할당

20 ▶ ISAM 화일의 실린더 할당

21 ▶ 실린더 오버플로우 구역 기본 구역의 오버플로우 트랙 오버플로우 인덱스 이점 단점 오버플로우 레코드를 원래 트랙과 연결
기본구역과 동일 실린더 오버플로우 구역 접근을 위한 별도의 탐구가 필요 없음 독립 오버플로우 구역 별도의 탐구 단점 모든 실린더에 동일 크기 → 사용의 불균형

22 ▶ 기본 데이타 구역 물리적 순서 유지 실린더 i의 레코드 키값 < 실린더 i+1의 임의의 키값 순차 접근 지원

23 (2) ISAM 화일의 인덱스 구조 다단계 인덱스 구조 트랙 인덱스 실린더 인덱스 마스터 인덱스

24 ▶ 트랙 인덱스 탐구 시간의 최소화 - 각 실린더의 트랙 0 인덱스 엔트리
정상 엔트리 (트랙의 최대키값, 트랙번호) 오버플로우 엔트리 (해당 트랙의 오버플로우 레코드의 최대키값, 최소키값을 가진 레코드 주소 쌍) NK1  OK1 < NK2  OK2 < ••• < NKn  OKn NKi : 트랙 i의 정상 엔트리 키값 OKi : 트랙 i의 오버플로우 엔트리 키값 ★ NKi = OKi : 오버플로우 레코드 없음

25 ▶ 실린더 인덱스 기본 데이타 구역의 실린더에 대한 엔트리 (실린더중 최대키값, 실린더의 트랙 인덱스 주소)

26 ▶ 마스터 인덱스 실린더 인덱스 - 여러 트랙으로 구성 마스터 인덱스 엔트리
(실린더 인덱스의 각 트랙에서 최대키값, 트랙의 주소) 한단계 또는 다단계 : 여러 트랙 최상위 단계 마스터 인덱스 : 한 트랙 정도 크기

27 ▶ ISAM 파일에서 키값이 144인 레코드 검색

28 (3) ISAM 화일에서의 삽입과 삭제 검색과 동일 방법으로 삽입해야될 기본 데이타 트랙 삽입 (a) 초기 화일
독립된 오버플로우 구역을 이용한 삽입 (a) 초기 화일

29 ▶ ISAM 화일에서의 삽입 (b) ARK를 삽입 (c) BED, BEG, BEN, BET, ARL을 차례로 삽입

30 ▶ ISAM 화일에서의 삽입 (d) ACE, BAR, BAT, AMY를 차례로 삽입

31 ▶ ISAM 화일에서의 재구성 및 삭제 재구성 삭제 독립된 오버플로우 구역의 사용 → 접근 시간 지연
오버플로우 체인 길이 증가 주기적 재구성 모든 레코드 → 기본 데이타 트랙으로 저장 삭제 삭제 표시 아주 높은 키값 삭제 필드 또는 플래그 삽입시 재이용

32  동적 인덱스 방법 블럭에 기초한 구현 : 동적인 구현 인덱스 화일 데이타 화일 인덱스 블럭의 트리구조
다중 레벨 인덱싱 (인덱스의 인덱스 화일) 최고 레벨 인덱스(마스터 인덱스)는 주기억장치에 적합 인덱스 엔트리 = <키 애트리뷰트 값, 포인터(데이타 블럭 또는 인덱스 블록)> 데이타 화일 순차적인 구조 - 데이타 블럭들 블럭들 사이에 자유공간이 분포 나중의 삽입을 위해 데이타 블럭들은 논리적인 순서로 연결 데이타 블럭 체인

33 ▶ 동적 인덱스 방법의 인덱스된 순차 파일 직접 검색 검색 레코드의 키 = '문봉기'

34 ▶ 삽입 데이타 블럭 분할 인덱스 블럭의 분할을 야기할 수 있음 (가정) 데이타 블럭 : 5 레코드
인덱스 블럭 : 4개의 <키값, 포인터> 쌍 자유공간 또는 패딩(padding) 존재

35 ▶ 삽입 예 ① INSERT 나동성 INSERT 강인회 데이타 블럭 1에 삽입

36 ▶ 삽입 예 ② INSERT 나문수 데이타 블럭 1의 분열과 인덱스 블럭의 변화

37 ▶ 삽입 예 ③ INSERT 김성복 INSERT 권성길 INSERT 고재현

38  VSAM 화일 VSAM : Virtual Storage Access Method 동적 인덱스 방법 VSAM 화일의 구조
제어 구간(control interval) 데이타 레코드 저장 제어 구역(control area) 제어 구간의 모임 순차셑(sequence set) 제어 구역에 대한 인덱스 저장 인덱스 셑(index set) 순차셑의 상위 인덱스

39 (1) VSAM 화일 구조

40 ▶ 제어 구간 구조 데이타 블럭 자유 공간 레코드 정의 필드(RDF: Record Definition Field)
키값에 따른 물리적 순차 자유 공간 레코드 정의 필드(RDF: Record Definition Field) RBA (Relative Byte Address) 레코드의 바이트 수 제어구간 정의필드(CIDF: Control Interval Definition Field) 제어 구간 내의 자유 공간 바이트 수 자유 공간의 위치

41 ▶ 제어 구간 양식과 삽입, 삭제 VSAM화일의 제어구간 양식 제어 구간에 대한 삽입, 삭제
저장된 레코드들 사이에 빈공간이 없도록 함

42 ▶ 제어 구역 일정 수의 제어 구간의 그룹 일정 수의 트랙으로 구성 순차셑 인덱스 엔트리=(제어 구간의 최대키값, 주소)
제어 구간의 물리적 순서는 필요 없음 순차셑에 의해 유지(체인으로 연결)

43 ▶ 인덱스셑 인덱스 블럭으로 구성된 트리 구조 엔트리= (차하위 레벨의 인덱스 블럭의 최대키값, 인덱스 블럭에 대한 주소)
인덱스셑의 최하위 단계 : 순차셑 지시 키값의 크기순으로 저장

44 (2) VSAM 화일에서의 삽입과 삭제 키 순차 화일(key-sequenced file) 지원
레코드들을 키값순으로 저장 제어 구간내의 물리적 순서 제어 구간들의 정렬 : 순차셑 순차셑의 정렬 : 인덱스셑 분산 자유 공간 (distributed free space) 제어 구간 내의 자유 공간 키 순차 VSAM : 각 제어 구역 끝의 빈 제어 구간

45 ▶ 키 순차 VSAM 화일 순차적 접근 직접 접근 화일의 첫 제어 구간의 RBA를 식별위해 인덱스 탐색
연결된 순차셑 체인을 따라가며 각 제어 구간 접근 직접 접근 인덱스셑 -> 순차셑 (B+-트리와 유사)

46 ▶ 키 순차 VSAM 화일 예 제어 구역 2

47 ▶ 레코드의 삽입 레코드의 이동 (∵ 제어 구간내의 물리적 순서 유지) 자유 공간의 부족 → 제어 구간의 분열(split)
만원이 된 제어 구간 제어 구역 끝의 빈 제어 구간으로 레코드 절반 이동 순차셑 엔트리로 제어구간 순서 유지 제어 구역 분열 만원이 된 제어 구역 화일 끝의 빈 제어구역으로 반 이동 순차셑 고정으로 문서 유지

48 ▶ 키가 52인 레코드가 삽입된 뒤의 제어 구역

49 ▶ 키가 54인 레코드가 삽입된 뒤의 제어 구역 키가 54인 레코드가 삽입되어 제어 구간 분열이 일어난 뒤의 제어 구역 1

50 ▶ 삽입과 삭제 물리적 삭제 → 레코드 이동 수록 순차 화일 (entry-sequential file)
순차셑 엔트리 변경 → 인덱스 셑 수록 순차 화일 (entry-sequential file) 레코드 순서: 화일에 수록되는 순서 인덱스 유지 안 함 RBA 제공: 사용자가 인덱스 구축 가능 상대 화일 (Relative File) 레코드의 제어 구간 저장시 상대 레코드 번호에 따라 저장 상대 레코드 번호 : 사용자가 정의 인덱스 없음 레코드길이 일정 : 제어구간의 레코드수 동일

51 ▶ 삽입과 삭제 크기가 8인 상대 레코드 VSAM 화일의 제어 구간 구조 VSAM 의 장점
기본데이타구역과 오버플로우구역의 구분 없음 레코드 삭제 → 빈공간도 자동적으로 자유 공간에 통합 B+-트리 구조를 인덱스로 이용 제어 구간의 분열 제어 구간에서 각 레코드의 제어 정보 유지 가변 길이 레코드 수용

52  인덱스된 순차 화일의 설계 기본적인 고려사항 ① 필드의 배치 ② 키 필드 - 고정 vs 가변 길이 레코드
- 인덱스와 데이타 화일에 같은 키 ③ 예상되는 레코드 삽입 - 자유공간 할당 (약 40%) ④ 화일을 구현하기 위한 방식

53 ▶ 설계 결정을 위한 매개 변수 정적 인덱스 방법 ① 인덱스 구역의 크기 ② 인덱스의 레벨 ③ 기본 데이타 구역의 크기
정적 인덱스 방법　 ① 인덱스 구역의 크기 ② 인덱스의 레벨 ③ 기본 데이타 구역의 크기 ④ 오버플로우 데이타 구역의 크기 ⑤ 기본 데이타 구역의 레코드 블럭킹 동적 인덱스 방법 ① 데이타 블럭의 크기 ② 인덱스 블럭의 크기 ③ 초기 인덱스 레벨 수 ④ 최대 인덱스 레벨 ★ 시스템 본래의 블럭 크기, 예상 레코드수, 화일의 용도 등에 따라 결정

54 ▶ 인덱스 설계 인덱스 참조 능력 y =  블럭의 크기 / 인덱스 엔트리 크기  =  B / (V+P) 
인덱스 분기율(fanout) y =  블럭의 크기 / 인덱스 엔트리 크기  =  B / (V+P)  인덱스 레벨 vs 인덱스 분기율

55 (1) 정적 인덱스의 설계 2,000 바이트 레코드 100만개 디스크 팩 : 200 실린더
실린더 : 19 트랙, 140,000 바이트/트랙 트랙 : 최대 70 레코드 55 레코드만 적재 마지막 2트랙 : 자유공간 트랙 0 : 트랙 인덱스

56 ▶ 초기 적재 실린더 16 트랙  55 레코드 = 880 레코드/실린더 실린더 수 =  100만 레코드/880 
실린더 수 =  100만 레코드/880  = 1,137 실린더 = 6 디스크 팩 트랙 인덱스 V = 14 바이트 P = 6 바이트 18 트랙  20 바이트  2 = 720 바이트 └ (정상, 오버플로우) 엔트리 실린더 인덱스 디스크 팩 별로 200 실린더씩 그룹 6  200  20 = 24,000 바이트 마스터 인덱스 6 디스크 팩에 대한 6 인덱스 엔트리

57 ▶ 정적 인덱스 설계 예

58 (2) 동적 인덱스 설계 하드웨어 독립적인 인덱스의 설계 B : 2000 바이트 ( 블럭크기 )
R : 바이트 ( 레코드 크기 ) V : 바이트 ( 인덱스 값 크기 ) P : 바이트 ( 포인터 크기 ) 100만 레코드 : 화일 B = = 10 : 블럭당 레코드의 수 R 106 = : 화일에 필요한 블럭의 수 || 첫단계의 인덱스 엔트리 수

59 ▶ 동적 인덱스 설계 계산 B 2000 y = ---------- = ---------- = 100 : 분기율 V + P 20
블럭당 인덱스 엔트리들의 최대 수 ┛ 105 ----- = 103 : 첫째 단계의 인덱스를 위해 필요한 블럭의 수 100 ⇒ 1000  20 = 20,000 : 인덱스의 바이트 103 ----- = 10 : 둘째 단계의 인덱스를 위해 필요한 블럭의 수 ⇒ 10  20 = 200 : 인덱스의 바이트 (주기억장치에 저장)  10/100  = 1 : 최고단계의 인덱스 블럭

60 ▶ 동적 인덱스 설계 예