01 화일의 기본 개념 02 화일 저장장치 03 화일 입출력 제어 04 순차화일 05 화일의 정렬 06 화일의 합병

Presentation on theme: "01 화일의 기본 개념 02 화일 저장장치 03 화일 입출력 제어 04 순차화일 05 화일의 정렬 06 화일의 합병"— Presentation transcript:

1 01 화일의 기본 개념 02 화일 저장장치 03 화일 입출력 제어 04 순차화일 05 화일의 정렬 06 화일의 합병 07 인덱스 구조 08 인덱스된 순차 파일 09 직접화일 10 다중 키 파일 11 다차원 공간 파일 12 텍스트를 위한 화일과 데이터 베이스

2 9.다중 키 화일

3 순서 다중 키 파일의 개념 역 파일 다중 리스트 파일 역 파일의 종류 역 파일의 연산 다중 리스트 파일의 구조
완전 역 화일 (Completely inverted file) 부분 역 화일 (Partially inverted file) 역 파일의 연산 다중 리스트 파일 다중 리스트 파일의 구조 다중 리스트 파일의 연산

4  다중 키 화일의 개념 하나의 데이타 화일 - 다수의 접근 경로(키) 구현 방법 (예) 학생 레코드 구조
(예) 학생 레코드 구조 다중 키 : 학번, 학과별, 입학 년도 별, 지도 교수 별 구현 방법 데이타 중복 이용 : 각 응용에 맞는 화일을 각각 구성 기억 공간 증가 데이타 무결성(integrity) 유지 곤란 한 화일에 대한 다수의 접근 경로 구축 : 다중 키 화일 역 화일(inverted file) : 인덱스 이용 다중리스트 화일(multilist file) : 레코드 사이의 다중리스트 이용 학번 이름 학과 주민 등록 번호 입학 년도 지도 교수 주소

5  역 화일 역 화일 구조 역 인덱스 (역) 인덱스를 이용하는 구조 역(inversion)
인덱스와 데이타 레코드 화일을 연결 역 인덱스 데이타 화일에 있는 키 필드 값을 인덱스 키로 모두 포함 인덱스 엔트리 = (키 값, 레코드 포인터) 이 때, 화일은 키 필드에 대해 전도(도치)되었다고 함 많은 DBMS의 물리적 데이타베이스 구조에 사용 쉽고 편리한 자연어 형태의 질의어도 가지고 있음

6 ▶ 학생 데이타 화일 317pp, 그림 9.2 레코드 주소 학번 이름 학과 주민 등록 번호 입학 년도 지도교수 주소 1 2 3
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1111 1121 1981 2014 2083 2918 3025 3112 3241 3358 3826 3874 4156 4862 5133 5342 5357 6412 6861 6945 이정진유근택이상수김성준용기환문용길나수영이상철황수관한재식이병찬홍병수송성헌김철수김연주유광석황시영이인기이규재안경화 컴퓨터기  계전  자컴퓨터기  계자  원화  공컴퓨터토  목전  자항  공항  공전  기전  자기  계토  목토  목전  자컴퓨터화  공 01 02 03 04

7 ▶ 레코드 주소를 이용한 주민등록번호 역 인덱스
318pp, 그림 9.3 주민 등록 번호 레코드 주소 10 16 1 4 6 8 13 12 15 2 19 5 14 7 18 11 9 20 17 3

8 ▶ 역 인덱스의 구성 그림9.3에서 주민등록번호(인덱스)들이 정렬되어 있다면 역 인덱스에서 정렬된 키의 순서 ≠ 레코드의 순서
직접 주소 기법 이원 탐색 : O(log N), 순차 탐색 : O(N/2) 역 인덱스에서 정렬된 키의 순서 ≠ 레코드의 순서 데이타 화일에 레코드가 삽입되면 : 역 인덱스도 갱신 화일 관리 비용이 많이 듬 인덱스 구조 : 테이블, 트리 형태 검색시간은 단축되나 처리가 더 복잡 직접 화일 위나, 인덱스 된 순차화일 위에 구성이 가능 학번을 기본 키로 하는 인덱스된 순차 화일에서 주민 등록 번호로 역 인덱스 구성 : 학번, 주민 등록 번호로 직접 접근이 가능하고, 학번으로 순차 접근이 가능

9 ▶ 역 화일의 종류 역(inversion) 역 인덱스가 만들어지는 수에 따라
데이타 화일에서 키 값 제거하여 역 인덱스에만 위치 역 인덱스가 만들어지는 수에 따라 완전 역 화일 (Completely inverted file) 데이타 레코드의 모든 필드에 대한 역 인덱스 데이타 레코드 화일은 존재 안 함(논리적) 부분 역 화일 (Partially inverted file) 몇 개의 필드에 대해서만 역 인덱스 구성

10 ▶ 역 인덱스 구성 방법의 대안 역 인덱스의 키 값을 데이타 레코드에서 제외했을 때 키 대안
"학번이 3358인 학생의 주민등록번호는 ?" ① 데이타 화일 : 학번 3358인 학생 레코드의 주소 검색 ② 역인덱스 : 주소를 포함하는 인덱스 엔트리 탐색 후, 역 인덱스에서 순차 탐색하여 주민번호 찾음 → 검색이 비 효율적임 키 기본 키 (primary key) : 유일 식별, 물리적 순서 결정 보조 키 (secondary key) : 레코드 접근을 위한 필드 대안 간접 주소 기법 이용 인덱스 엔트리 = (보조 키, 기본 키)

11 ▶ 기본 키를 이용한 주민등록번호 역 인덱스 구조의 변형
주민 등록 번호(보조 키) 학 번(기본 키) 3358 5342 1111 2014 2918 3112 4156 3874 5133 1121 6861 2083 4862 3025 6412 3826 3241 6945 5357 1981 (장점) 데이타 화일의 물리적 재구성 또는 재조직이 가능 → 역 인덱스 화일에 영향 없음

12 ▶ 비유일 보조 키에 대한 역 인덱스 학과 이름에 대한 역 인덱스 문제점 키 값 엔트리(학번)들을 정렬할 것인가?
인덱스는 어떻게 구성할 것인가? 주소 기법(직접/간접)은? 학 과 학 번 기 계 자 원 전 기 전 자 컴퓨터 토 목 항 공 화 공 1121, 2083, 5133   2918   4156   1981, 3358, 4862, 6412   1111, 2014, 3112, 6861   3241, 5342, 5357   3826, 3874   3025, 6962

13 ▶ 가변수의 포인터를 위한 인덱스 구현 방법 ① 가변 길이 인덱스 엔트리로 관리한다
② 고정길이 인덱스 엔트리로 관리한다 - 최대수의 엔트리를 수용할 수 있는 공간을 할당 ③ 인덱스 엔트리를 중복시켜 관리한다 -역 인덱스의 엔트리 = (보조키 값, 하나의 주소) 쌍 역 인덱스 화일에서 주소 값(기본 키)을 정렬시키면 레코드 검색은 신속하나, 레코드 갱신시 추가 부담 역 화일의 매력 : 인덱스만으로도 질의 응답이 가능 ①주민등록번호가 인 학생이 있는가 ? ② 컴퓨터공학과에는 몇 명의 학생이 있는가 ? ③ 기계과에 속하는 학생의 학번들을 나열하라. ④주민등록번호가 인 학생의 학번은 무엇인가 ?

14 ▶ 역 화일의 연산 역 화일의 연산 : 데이타 화일과 역 인덱스 화일 포함 레코드의 삽입 레코드의 삭제 레코드의 갱신
데이타 화일 : 레코드 삽입 역 인덱스 화일 : 인덱스 엔트리 삽입, 포인터만 첨가 레코드의 삭제 데이타 화일 : 레코드 삭제 역 인덱스 화일 : 포인터 제거, 공백이면 엔트리 제거 레코드의 갱신 레코드 갱신 작업 후(데이타 화일) 갱신 영향을 받은 모든 역 인덱스 화일에 삽입, 삭제 연산을 수행(역 인덱스 화일)

15 순서 다중 키 파일의 개념 역 파일 다중리스트 파일 역 파일의 종류 역 파일의 연산 다중 리스트 파일의 구조
완전 역 화일 (Completely inverted file) 부분 역 화일 (Partially inverted file) 역 파일의 연산 다중리스트 파일 다중 리스트 파일의 구조 다중 리스트 파일의 연산

16  다중 리스트 화일 다중 리스트 역 인덱스와 다중 리스트 인덱스의 차이점 현재 많은 상용 DBMS의 물리적 DB구조의 기초
각 보조키에 대해 하나의 다중 리스트 화일 유지 역 인덱스와 다중 리스트 인덱스의 차이점 역 인덱스 (키 값, 그 키 값의 모든 레코드들에 대한 포인터) 인덱스 엔트리 : 여러 개의 포인터 값을 갖는 가변길이 다중 리스트 인덱스 (키 값, 하나의 레코드에 대한 시작 포인터) 나머지 레코드 → 데이타 화일에서 연결리스트 구조로 유지 디렉토리 역할 : 각 리스트의 헤드만 유지 인덱스 엔트리 : 하나의 포인터 값만을 갖는 고정길이

17 ▶ 다중리스트 화일의 구조 다중 리스트 인덱스

18 ▶ 다중 리스트 화일의 구조 역 화일 다중 리스트 화일 역 인덱스를 구성 → 데이타 화일 구조에 영향 없음
다중 리스트 인덱스 구성 → 데이타 화일 구조 변경 필요 데이타 화일 : 인덱스의 리스트를 위한 포인터 필드 추가 데이타 레코드의 포인터 필드의 수 = 인덱스 수 인덱스 엔트리 : 하나의 포인터 값만 갖는 고정길이

19 ▶ 학과, 입학년도 대한 다중 리스트 인덱스 학 과 학 번 기 계 자 원 전 기 전 자 컴 퓨 터 토 목 항 공 화 공
학과에 대한 다중 리스트 인덱스 학 과 학 번 기 계 자 원 전 기 전 자 컴 퓨 터 토 목 항 공 화 공 1121 2918 4156 1981 1111 3241 3826 3025 ► 입학 년도에 대한 다중 리스트 인덱스 입학 년도 학 번 01 02 03 04 1111 1121 1981 5133

20 ▶ 학과, 입학년도, 다중리스트에 대한 학생 데이타 화일

21 ▶ 다중리스트 화일의 구조 데이타 레코드 구조 다중 리스트 인덱스 설계 시의 고려 사항 인덱스 키 값들을 정렬할 것인가?
인덱스의 구성 방법은? 주소법 : 직접/간접 리스트의 데이타 레코드의 정렬 여부 … 다중 리스트 인덱스 필드 1 링크 필드 1 인덱스 필드 2 링크 필드 2

22 ▶ 레코드의 검색 과정 질의 유형의 예 ① 컴퓨터공학과에는 몇 명의 학생이 있는가 ?
② 컴퓨터공학과에 속한 학생의 학번을 모두 검색하라. ③ 학번이 인 학생의 소속이 컴퓨터 공학과인가 ? 처리 과정 역 화일 : 인덱스만 접근해도 가능 다중리스트 : 데이타 레코드를 접근해야 가능 (대안) 인덱스 엔트리에 리스트 길이 정보를 가짐 다중 리스트 인덱스의 변형 인덱스 엔트리 = (키 값, 첫번째 레코드의 포인터, 리스트 길이)

23 ▶ 학과에 대한 다중리스트 인덱스 학 과 학 번 길 이 기 계 자 원 전 기 전 자 컴 퓨 터 토 목 항 공 화 공 1121
기 계 자 원 전 기 전 자 컴 퓨 터 토 목 항 공 화 공 1121 2918 4156 1981 1111 3241 3826 3025 3 1 4 2

24 ▶ 입학 년도에 대한 다중 리스트 인덱스 입학 년도 학 번 길 이 01 02 03 04 1111 1121 1981 5133 7

25 ▶ 리스트 길이 정보의 활용 특정 유형 질의에 대한 최적 접근 경로 선정 시 이용
(질의) "입학년도 = 01 이고 학과 = 컴퓨터인 학생의 이름을 검색하라" 처리 방법 ① 학생 데이타 화일의 순차적 탐색 20개의 레코드 접근 ② 학과 다중 리스트 인덱스 사용 4개의 레코드 ③ 입학년도 다중 리스트 인덱스 사용 7개의 레코드 ∴ ② 선택 i) 학과 = 컴퓨터인 레코드 접근해서 ii) 4개의 레코드 : 입학 년도 필드 검사

26 ▶ 다중 리스트 화일의 연산 레코드의 삽입 레코드의 삭제 레코드의 갱신 다중 리스트의 구현 방법
데이타 화일 : 새 레코드를 삽입하면 인덱스 참조 → 데이타 화일의 연결리스트에 연결 만약, 인덱스에 없으면 : 새 인덱스 엔트리로 삽입 레코드의 삭제 데이타 화일 : 연결리스트에서 하나의 노드 삭제하면 인덱스 : 연결리스트에서 유일 멤버이면 → 인덱스 삭제 (예) “이정진” 학생을 삭제할 때 : 학과, 입학년도를 연결 리스트에서 삭제, 인덱스의 링크 변경 레코드의 갱신 데이타 화일 : 레코드 필드 값이 변경되면 다중 리스트 변경(필요시 다중 리스트 인덱스도 갱신) 다중 리스트의 구현 방법 단순/이중 연결 (원형) 리스트

27  역 화일과 다중 리스트 화일의 비교 공통점 차 이 점 역 인덱스 다중 리스트 인덱스 인덱스 엔트리
모든 보조 키에 대한 인덱스 유지 인덱스는 테이블, 트리 형태 로 구성 인덱스 엔트리들은 정렬 가능 데이타 레코드는 직접/간접 주소법 사용 차 이 점 역 인덱스 다중 리스트 인덱스 인덱스 엔트리 보조키 값의 모든 레코드 포인터 첫번째 레코드만 포인터, 나머지 레코드는 연결리스트 엔트리 길이 가변 길이 고정 길이 정 렬 오버헤드 데이타 화일 구조 영향 없음 링크 필드 첨가 질 의 •질의 처리 능력 우월 (역 인덱스만의 접근 으로 응답 가능) • 인덱스를 사용하지 않는 프로그래머에게 투명하다(인덱스가 있음을 몰라도 됨) • 인덱스 관리 용이 (고정길이 엔트리) • 투명성 보장 위해 : 데이타 관리자의 별도 작업 필요 • 한 화일에 다수의 정렬 순서 제공이 가능