10. 데이터베이스의 저장과 접근.

Presentation on theme: "10. 데이터베이스의 저장과 접근."— Presentation transcript:

1 10. 데이터베이스의 저장과 접근

2 10.1 데이터베이스의 저장(1) 데이터베이스 저장장치 디스크 접근시간(access time)
10.1 데이터베이스의 저장(1) 데이터베이스 저장장치 데이터를 저장하는 방법과 접근에 영향 직접 접근 저장 장치(DASD:Direct Access Storage Device)로 디스크 사용 RAID나 광저장 장치도 사용 디스크 접근시간(access time) 헤드가 원하는 트랙에 있는 레코드를 찾아 전송하는데 걸리는 시간 실린더, 트랙, 섹터, 판독헤드 탐구 시간(seek time) 회전지연 시간(rotational delay) 데이터 전송 시간(transfer time) 메인 메모리 접근시간에 비해 느림 약 10~30ms cf) 메인 메모리 : 약 10~100ns 밀리 초 (ms 또는 msec)는 천 분의 1초 즉 초 나노 초 (ns 또는 nsec)는 십억 분의 1초, 즉 10-9초 디스크 접근 횟수의 최소화가 가장 중요한 성능 개선 방법 디스크에의 배치, 저장이 중요한 문제 금오공과대학 컴퓨터공학부 컴퓨터공학전공

3 10.1 데이터베이스의 저장(2) 저장구조(storage structure) 디스크에 데이터가 배치되어 저장되어 있는 형태
다양한 저장구조를 지원해야 좋은 시스템임 DB의 부분별로 적절한 저장 성능요건 변경 시 저장 구조 변경 데이터베이스의 물리적 설계 DB의 사용 방법, 응용, 응용 실행 빈도수에 따라 적절한 저장방식을 선정하는 과정 금오공과대학 컴퓨터공학부 컴퓨터공학전공

4 10.2 데이터베이스의 접근 데이터베이스의 일반적인 접근 과정 DBMS는 사용자가 요구하는 레코드를 결정
파일 관리자에게 그 저장 레코드의 검색을 요청 파일 관리자는 그 저장레코드가 들어있는 페이지를 결정 디스크 관리자에게 그 페이지의 검색을 요청 디스크 관리자는 그 페이지의 물리적 위치를 결정 디스크에 입출력 명령을 내림 사용자 정보 요구 결과 DBMS 저장 레코드 요청 레코드 반환 파일 관리자 운영체제 페이지 요청 페이지 반환 디스크 관리자 디스크I/O 연산 블록 검색 저장 데이터베이스 금오공과대학 컴퓨터공학부 컴퓨터공학전공

5 디스크 관리자(1) 기본 입출력 서비스 (basic I/O service) 모듈 파일 관리자 지원 디스크 관리
물리적 디스크 주소를 알고 있어야 함 운영체제의 한 구성요소 파일 관리자 지원 파일 관리자는 디스크를 일정 크기의 페이지로 구성된 페이지 세트들의 논리적 집단으로 취급 데이터 페이지 세트와 하나의 자유공간 페이지 세트 페이지 세트 : 유일한 페이지 세트 ID 페이지 : 해당 디스크 내에서 유일한 페이지 번호를 가짐 디스크 관리 페이지 번호  (사상)  물리적 디스크 주소  파일 관리자를 장비에서 독립 파일 관리자의 요청에 따라 페이지 세트에 대한 페이지의 할당과 회수 금오공과대학 컴퓨터공학부 컴퓨터공학전공

6 ▶ 디스크 관리자(2) 디스크 관리자의 페이지 관리 연산 Notes 파일 관리자가 명령할 수 있는 연산
1) 페이지 세트 S로부터 페이지 P의 검색 2) 페이지 세트 S 내에서 페이지 P 의 교체 3) 페이지 세트 S에 새로운 페이지 P 의 첨가 (자유공간 페이지 세트의 빈 페이지를 할당) 4) 페이지 세트 S에서 페이지 P 를 제거 (자유공간 페이지 세트로 반환) Notes 파일 관리자의 요청에 의한 연산 : 1), 2) 디스크 관리자의 필요에 따른 연산 : 3), 4) 금오공과대학 컴퓨터공학부 컴퓨터공학전공

7 파일 관리자(1) DBMS가 디스크를 저장 파일들의 집합으로 취급할 수 있도록 지원 저장 파일(stored file)
한 타입의 저장레코드 어커런스들의 집합 한 페이지 세트는 하나 이상의 저장 파일을 포함 파일 이름 또는 파일 ID로 식별 저장 레코드 레코드번호 또는 레코드 ID(RID: Record Identifier)로 식별 전체 디스크 내에서 유일 (페이지 번호, 오프셋(슬롯번호)) OS의 한 구성요소 또는 DBMS와 함께 패키지화 금오공과대학 컴퓨터공학부 컴퓨터공학전공

8 ▶ 파일 관리자(2) 파일 관리자의 파일 관리 연산 정리해 봅시다. DBMS가 파일관리자에 명령할 수 있는 연산
1) 저장 파일 f에서 저장 레코드 r의 검색 2) 저장 파일 f에 있는 저장 레코드 r의 대체 3) 저장 파일 f에 새로운 레코드를 첨가하고 새로운 레코드 RID, r을 반환 4) 저장 파일 f에서 저장 레코드 r의 제거 5) 새로운 저장 파일 f의 생성 6) 저장 파일 f의 제거 정리해 봅시다. 금오공과대학 컴퓨터공학부 컴퓨터공학전공

9 페이지 세트S. 페이지 P 첨가 페이지 세트S. 페이지 P 제거 사상
DBMS 테이블 DBMS Façade 테이블.레코드 검색(), 대체() 테이블.레코드 추가(), 삭제() 테이블 추가(), 삭제() 사상 데이터 테이블 카탈로그 파일관리자 저장레코드 어커런스 레코드 ID (페이지번호 오프세트) 파일관리자 Façade 저장파일.저장레코드 검색(), 대체() 저장파일.저장레코드 추가(), 삭제() 저장파일.추가(), 삭제() 저장파일 파일 ID 1 n n 저장 저장 관리자 1 페이지 페이지 번호 페이지세트 저장관리자 Façade 페이지 세트S. 검색(페이지 P) 페이지 세트S. 교체(페이지 P) 페이지 세트S. 페이지 P 첨가 페이지 세트S. 페이지 P 제거 사상 물리적디스크주소 데이터 페이지세트 자유공간 페이지세트 금오공과대학 컴퓨터공학부 컴퓨터공학전공

10 10.3 페이지 세트와 파일 페이지 관리(page management) 예제 : 대학 데이터베이스
파일관리자가 물리적 디스크 I/O가 아닌 논리적인 페이지 I/O 로 관리할 수 있게끔 지원하는 디스크 관리자의 기능 예제 : 대학 데이터베이스 레코드들의 논리적 순서는 그림에 있는 것과 같이 각각 학번, 과목번호, 학번-과목번호 순임 저장 순서도 이 논리적 순서와 같음 저장 파일들은 28개의 페이지로 구성된 페이지 세트에 저장 각 레코드들은 하나의 페이지를 차지한다고 가정 금오공과대학 컴퓨터공학부 컴퓨터공학전공

11 ▶ 대학 데이터베이스 학생 등록 과목 학번 이름 학년 학과 S1: 100 나수영 4 컴퓨터 S2: 200 이찬수 3 전기
300 정기태 1 S4: 400 송병길 S5: 500 박종화 2 산공 학번 과목번호 성적 E1: 100 C413 A E2: E412 E3: 200 C123 B E4: 300 C312 E5: C324 C E6: E7: 400 E8: E9: E10: E11: 500 학생 과목번호 과목이름 학점 담당교수 C1: C123 프로그래밍 3 김성국 C2: C312 자료 구조 황수관 C3: C324 파일 구조 이규찬 C4: C413 데이터베이스 이일로 C5: E412 반 도 체 홍봉진 등록 과목 금오공과대학 컴퓨터공학부 컴퓨터공학전공

12 ▶ 예제의 연산 과정 (1) 처음(빈 디스크) : 파일 관리자 : 학생 파일에 있는 5개의 레코드 삽입
하나의 자유 공간 페이지 세트만 존재(1 ~ 27) 페이지 0 제외 : 디스크 디렉터리 파일 관리자 : 학생 파일에 있는 5개의 레코드 삽입 디스크관리자 : 자유공간 페이지 세트의 페이지 1에서 5까지를 "학생 페이지 세트" 라고 이름을 붙이고 할당 과목과 등록 파일에 대한 페이지 세트를 할당 4개의 페이지 세트가 만들어짐 "학생"(1~5), "과목"(6~10), "등록"(11~21),"자유공간" 페이지 세트 (페이지 22~27) 금오공과대학 컴퓨터공학부 컴퓨터공학전공

13 ▶ 대학 데이터베이스의 초기 적재 후의 디스크 배치도
1 2 3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 25 26 27 S1 S2 S3 S5 C1 C2 C3 C4 C5 E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 4 페이지번호 S4 22 금오공과대학 컴퓨터공학부 컴퓨터공학전공

14 ▶ 예제의 연산 과정 (2) 파일 관리자 : 새로운 학생 S6 (학번 600)을 삽입 1 2 3 4 5 6 S1 S2 S3
디스크 관리자 : 첫번째 자유 페이지 (페이지 22)를 자유공간 페이지 세트에서 찾아서 학생 페이지 세트에 첨가 1 2 3 4 5 6 S1 S2 S3 S4 S5 C1 7 8 9 10 11 12 13 C2 C3 C4 C5 E1 E2 E3 14 15 16 17 18 19 20 E4 E5 E6 E7 E8 E9 E10 21 22 23 24 25 26 27 E11 S6 금오공과대학 컴퓨터공학부 컴퓨터공학전공

15 파일 관리자 : S2 (학번 200)를 삭제 디스크 관리자 : 이 레코드가 저장되어 있던 페이지 (페이지 2)를 자유공간 페이지 세트로 반납 1 2 3 4 5 6 S1 S3 S4 S5 C1 7 8 9 10 11 12 13 C2 C3 C4 C5 E1 E2 E3 14 15 16 17 18 19 20 E4 E5 E6 E7 E8 E9 E10 21 22 23 24 25 26 27 E11 S6 금오공과대학 컴퓨터공학부 컴퓨터공학전공

16 파일 관리자 : 새로운 과목 C6 (E 515)를 삽입 디스크 관리자 : 자유공간 페이지 세트에서 첫번째 자유페이지 (페이지 2)를 찾아서 과목 페이지 세트에 첨가 1 2 3 4 5 6 S1 C6 S3 S4 S5 C1 7 8 9 10 11 12 13 C2 C3 C4 C5 E1 E2 E3 14 15 16 17 18 19 20 E4 E5 E6 E7 E8 E9 E10 21 22 23 24 25 26 27 E11 S6 금오공과대학 컴퓨터공학부 컴퓨터공학전공

17 파일 관리자 : S4를 삭제 디스크 관리자 : S4가 저장되어 있던 페이지 (페이지 4)를 자유공간 페이지 세트에 반납 I : S6 D : S2 I : C6 D : S4 삽입, 삭제 연산 실행 후에는 페이지들의 물리적 인접성이 없어짐 1 2 3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 S1 C6 S3 S5 C1 C2 C3 C4 C5 E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 4 S6 금오공과대학 컴퓨터공학부 컴퓨터공학전공

18 ▶ 포인터 표현 방법 한 페이지 세트에서 페이지의 논리적 순서가 물리적 인접으로 표현되지 않음
한 페이지 세트에서 페이지의 논리적 순서가 물리적 인접으로 표현되지 않음 페이지 : 페이지 헤드 ­ 제어정보 저장 포인터 : 논리적 순서에 따른 다음 페이지의 물리적 주소 다음 페이지 포인터는 디스크 관리자가 관리 (파일 관리자는 무관) 금오공과대학 컴퓨터공학부 컴퓨터공학전공

19 페이지 헤드에 “다음 페이지” 포인터가 포함되어 있는 경우의 디스크 배치도
페이지번호 다음 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 16 17 18 19 20 21 22 23 24 25 26 27 x S1 C6 C4 C5 E1 E2 E3 C1 S5 S3 C2 C3 E6 E7 E8 E9 E10 E4 E5 E11 S6 금오공과대학 컴퓨터공학부 컴퓨터공학전공

20 ▶ 포인터 표현 방법(2) 디스크 디렉터리(페이지 세트 디렉터리) 디스크 디렉터리 (페이지 0) 실린더 0, 트랙 0에 위치
디스크에 있는 모든 페이지 세트의 리스트와 각 페이지 세트의 첫번째 페이지에 대한 포인터 저장 디스크 디렉터리 (페이지 0) 페이지 세트 자유공간 학 생 과 목 등 록 주 소 4 1 6 11 금오공과대학 컴퓨터공학부 컴퓨터공학전공

21 . ▶ 파일 관리자의 기능 저장 레코드 관리 (stored record management) 기능 예
DBMS가 페이지 I/O 에 대한 세부적인 사항에 대해 알 필요 없이 저장파일과 저장 레코드만으로 동작하게 함 예 하나의 페이지에 여러 개의 레코드 저장 학생 레코드에 대한 논리적 순서는 학번 순 1) 페이지 p에 5개의 학생레코드(S1~ S5)가 삽입되어 있다고 가정 . 5개의 학생 레코드를 처음 적재한 페이지 P의 배치도 P S1 S2 S3 S4 S5 금오공과대학 컴퓨터공학부 컴퓨터공학전공

22 . ▶ 파일 관리자(2) 2) DBMS : 학생 레코드 S9(학번 900)의 삽입 요청
페이지 p의 학생레코드 S5 바로 다음에 저장 3) DBMS : 레코드 S2의 삭제 요청 페이지 p에 있는 학생 레코드 S2를 삭제하고 뒤에 있는 레코드들을 모두 앞으로 당김 4) DBMS : 레코드 S7(학번 700)의 삽입 요청 학생레코드 S5 다음에 들어가야 되므로 학생 레코드 S9를 뒤로 옮김 . S2가 삭제되고 S9와 S7이 삽입된 후 의 페이지 P 의 배치도 P S1 S3 S4 S5 S7 S9 금오공과대학 컴퓨터공학부 컴퓨터공학전공

23 ▶ RID의 구현 RID = (페이지 번호 p, 오프셋(슬롯번호)) 오프셋 = 페이지 내에서의 레코드 위치(byte)를 표현
r의 RID p 4 페이지 번호 오프셋 (슬롯번호) RID = (페이지 번호 p, 오프셋(슬롯번호)) 오프셋 = 페이지 내에서의 레코드 위치(byte)를 표현 레코드가 한 페이지 내에서 이동할 때마다 RID의 변경 없이 오프셋의 내용(포인터)만 변경 최악의 경우 두 번째 접근으로 원하는 레코드 검색가능 해당 페이지가 오버플로우가 되어 다른 페이지로 저장된 경우 두 번 접근 금오공과대학 컴퓨터공학부 컴퓨터공학전공

24 ▶ Note 파일에 속하는 모든 저장 레코드들을 순차적으로 접근할 수 있음 제어 정보 사용자 데이터 필드
순차적 접근 : 페이지 세트 내에서는 페이지 순서, 페이지 안에서는 레코드 순서 레코드 순서 : RID의 오름차순(물리적 순차(physical sequence) ) 제어 정보 저장 레코드에 저장된 정보 중, 시스템이 필요로 하는 정보 파일의 ID 레코드 길이(가변 길이 레코드의 경우) 삭제 플래그(물리적 삭제를 하지 않는 경우) 레코드 앞에 접두부(prefix)로 만들어 저장 일반 사용자와 무관 사용자 데이터 필드 저장 레코드에 저장된 정보 중, 사용자가 필요로 하는 정보 DBMS가 이용, 파일 관리자와 디스크 관리자는 알 필요 없음 (파일 관리자는 파일을 단순히 바이트 스트링으로 인식) 금오공과대학 컴퓨터공학부 컴퓨터공학전공

25 10.4 파일의 조직 방법 물리적 저장 장치에 저장하기 위한 배치방법 파일 조직 순차 방법 인덱스 방법 해싱 방법
엔트리 순차 파일 (파일) 키순차 파일 인덱스된 순차 파일 다중키 파일 직접 파일 역파일 다중리스트 금오공과대학 컴퓨터공학부 컴퓨터공학전공

26 파일(엔트리순차) 파일 키(학번)순차 파일 ▶ 순차 방법 레코드들의 논리적 순서가 저장 순서와 동일
히프(heap) 또는 파일(pile) : 엔트리 순차(entry-sequence) 파일 일반적인 순차 파일 : 키 순차(key-sequence) 파일 레코드 접근 - 물리적 순서 파일 복사, 순차적 일괄 처리(batch processing) 응용 S4 S1 S2 S5 S3 S1(100) S2(200) S3(300) S4(400) S5(500) 파일(엔트리순차) 파일 키(학번)순차 파일 금오공과대학 컴퓨터공학부 컴퓨터공학전공

27 ▶ 인덱스 방법 인덱스를 통해 데이터 레코드를 접근 인덱스된 파일(indexed file)의 구성
인덱스 파일(index file)  파일!! 데이터 파일(data file)  파일!! 인덱스 파일 데이터 파일 키값 주소 K1 K2 K3 금오공과대학 컴퓨터공학부 컴퓨터공학전공

28 ▶ 인덱스된 순차 파일(indexed sequential file)
하나의 인덱스를 사용 순차 파일과 직접 파일을 결합한 형태 순차 데이터 파일(sequential data file) 레코드가 순차적으로 정렬 → 레코드 집합 전체에 대한 순차 접근 요구를 지원하는데 사용 (순차 접근 방법(sequential access method)) 인덱스(index) 레코드들에 대한 포인터를 가짐 → 개별 레코드들에 대한 임의 접근 요구를 지원하는데 사용(직접 접근 방법(direct access method)) 금오공과대학 컴퓨터공학부 컴퓨터공학전공

29 ▶ 인덱스의 문제점 검색시간 인덱스는 어디에 저장되는가? 데이터 화일에 레코드가 삽입되면 해결 방법은?
주민등록번호(인덱스)들이 정렬되어 있다면 이원 탐색 : O(log N), 순차 탐색 : O(N/2) 인덱스는 어디에 저장되는가? 데이터 화일에 레코드가 삽입되면 인덱스도 갱신 화일 관리 비용이 많이 듬 해결 방법은? B-Tree 금오공과대학 컴퓨터공학부 컴퓨터공학전공

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

31 ▶ 다중 키 파일(multikey file)
역 파일(inverted file) 각 필드마다 인덱스를 만들어 구현 다중 리스트 파일(multilist file) 하나의 인덱스 값마다 하나의 데이터 레코드 리스트를 구축 인덱스1 데이터 레코드 파일 키값 주소 K1 데이터 레코드 파일 다중리스트 인덱스 K1 K2 K1 K2 키값 주소 K1 K2 키값 주소 K1 K2 인덱스2 키값 주소 K2 역 파일 다중 리스트 파일 금오공과대학 컴퓨터공학부 컴퓨터공학전공

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

33 ▶ 학생 데이터 화일 레코드 주소 학번 이름 학과 주민 등록 번호 입학 년도 지도교수 주소 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 금오공과대학 컴퓨터공학부 컴퓨터공학전공

34 ▶ 레코드 주소를 이용한 학과 역 인덱스 학과 레코드 주소 기계 2 5 15 자원 6 전기 13 전자 3 10 14 18
▶ 레코드 주소를 이용한 학과 역 인덱스 학과 레코드 주소 기계 2 5 15 자원 6 전기 13 전자 3 10 14 18 컴퓨터 1 4 8 19 토목 9 16 17 항공 11 12 화공 7 20 금오공과대학 컴퓨터공학부 컴퓨터공학전공

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

36 ▶ 학과, 입학년도, 다중리스트에 대한 학생 데이터 화일
금오공과대학 컴퓨터공학부 컴퓨터공학전공

37 ▶ 다중 리스트 화일의 구조 역 화일 다중 리스트 화일 역 인덱스를 구성 → 데이터 화일 구조에 영향 없음
다중 리스트 인덱스 구성 → 데이터 화일 구조 변경 필요 데이터 화일 : 인덱스의 리스트를 위한 포인터 필드 추가 데이터 레코드의 포인터 필드의 수 = 인덱스 수 인덱스 엔트리 : 하나의 포인터 값만 갖는 고정길이 금오공과대학 컴퓨터공학부 컴퓨터공학전공

38 ▶ 다중리스트 화일의 구조 데이터 레코드 구조 … 링크 필드 1 링크 필드 2 다중 리스트 인덱스 필드 1 인덱스 필드 2
금오공과대학 컴퓨터공학부 컴퓨터공학전공

39 ▶ 인덱스의 구조 및 종류(1) 인덱스의 구조 기본 인덱스(primary index)
<레코드 키 값, 레코드 주소(포인터)> 기본 인덱스(primary index) 기본 키를 포함한 인덱스 보조 인덱스(secondary index) 기본 인덱스 이외의 인덱스. 보통 보조키를 포함 집중 인덱스(clustered index) 데이터 레코드의 물리적 순서가 인덱스 엔트리 순서와 동일하게 유지하도록 구성된 인덱스 같은 인덱스 키 값을 가진 레코드는 물리적으로 인접하게 되어 검색이 효율적 비 집중 인덱스(unclustered index) 집중 형태가 아닌 인덱스 하나의 데이터 파일에 여러 개 생성 가능 금오공과대학 컴퓨터공학부 컴퓨터공학전공

40 ▶ 인덱스의 구조 및 종류(2) 밀집 인덱스(dense index) 희소 인덱스(sparse index)
데이터 레코드 하나에 대해 하나의 인덱스 엔트리가 만들어지는 인덱스 역 인덱스(inverted index)는 보통 밀집 인덱스 형태로 만듬 희소 인덱스(sparse index) 데이터 파일의 레코드 그룹 또는 데이터 블록에 하나의 엔트리가 만들어지는 인덱스 금오공과대학 컴퓨터공학부 컴퓨터공학전공

41 하나 더! 검색 엔진의 원리 웹 문서 사용자 질의 질의 결과 파싱된 검색결과 DB 검색 색인 및 웹 문서 정보 웹 검색 로봇
Index Builder 데이터베이스 질의처리기 사용자 질의 질의 결과 DB 검색 검색결과 색인 및 웹 문서 정보 파싱된 금오공과대학 컴퓨터공학부 컴퓨터공학전공

42 Web IR 흐름도 Keyword/URL Stopping Web Connection Stemming Web Page Load
Information Retrieval Keyword/URL Stopping Web Connection Stemming Web Page Load Term Retrieval HTML Tag Remove Term Weighting Lexical Analysis DB Indexing 금오공과대학 컴퓨터공학부 컴퓨터공학전공

43 Web Page 수집 HTML Tag Remove Lexical Analysis Stopping Stemming
Web Robot & Web Agent 초기 URL을 시작으로 연속적인 탐색 HTML Tag Remove 문서의 내용과 관계없는 HTML의 해석기호 제거 Lexical Analysis a word or token 의 분리(생성) Stopping Index term으로 가치가 없는 단어 제거 Stoplist의 구축 Stemming Provide with ways of finding morphological variant of search terms 단/복수, 파생어, 형 변환 등 education educational educator educators Term Weighting 문서에 나타난 각 단어(색인어)의 중요도를 책정 금오공과대학 컴퓨터공학부 컴퓨터공학전공

44 DB indexing 정보의 검색과 제공에 사용, 역 색인(inverted index)구조 사용
금오공과대학 컴퓨터공학부 컴퓨터공학전공

45 (1) B-트리 차수 m인 B-트리의 특성 공백이거나 높이가 1이상인 m-원 탐색 트리(m-way search tree)
루트와 리프(leaf)를 제외한 내부 노드는 최소 ⌈m/2⌉, 최대 m개의 서브트리를 가짐(적어도 ⌈m/2⌉-1개의 키 값을 가짐) 루트는 그 자체가 리프가 아닌 이상 적어도 두 개의 서브트리를 가짐 모든 리프는 같은 레벨에 있음 균형 트리 금오공과대학 컴퓨터공학부 컴퓨터공학전공

46 ▶ B-트리의 노드의 구조 및 특성 ＜n, P0, <K1, A1>, P1, <K2, A2>, P2, … , Pn-1, <Kn, An>, Pn> n : 키 값의 수 ( 1≤n<m ) P0, …, Pn : 서브트리에 대한 포인터 K1, …, Kn : 키 값 각 키 값(Ki)은 그 키 값을 가지고 있는 레코드에 대한 포인터 Ai를 함께 포함  한 노드 안에 있는 키 값들은 오름차순 Pi (0≤i≤n-1)가 지시하는 서브트리에 있는 모든 노드들의 모든 키 값들은 키 값 Ki+1보다 작음 Pn이 지시하는 서브트리에 있는 노드들의 모든 키 값들은 Kn보다 큼 Pi (0≤i≤n)가 지시하는 서브트리들은 모두 m-원 서브 탐색 트리 금오공과대학 컴퓨터공학부 컴퓨터공학전공

47  3차 B-트리 a b c d e f g h i j k l m n o p q r s t u v 69 ^ 19 43 128
138 d e f g h i 16 ^ 26 40 60 ^ 100 ^ 132 ^ 145 ^ j k l m n o p q r s t u v 7 15 18 20 30 36 42 50 58 62 65 70 110 120 130 136 140 150 금오공과대학 컴퓨터공학부 컴퓨터공학전공

48 ▶ 연산(1) B-트리에서의 연산의 종류 삽입 직접 탐색 : 키 값에 의한 분기 순차 탐색 : 중위 순회
삽입, 삭제 : 트리의 균형을 유지해야함 분할 : 노드 오버플로 발생시 합병 : 노드 언더플로 발생시 삽입 리프노드 빈 공간이 있는 경우 : 단순히 빈 공간에 삽입하면 됨 오버플로 1) 두 노드로 분열(split) 2) m/2 째의 키 값  부모노드 3) 나머지는 반씩 나눔 (왼쪽, 오른쪽 서브트리) f 60 ^ o p 50 58 62 65 금오공과대학 컴퓨터공학부 컴퓨터공학전공

49  삽입 예: 59삽입 59 삽입 o에 overflow  50,58,59 의 중간값인 58을 기준으로 o와 o’으로 분할
중간값 58이 부모로 삽입 부모에 여유가 있으므로 쉬프트 b b f f 60 ^ 58 60 o o o’ p p 50 58 50 59 overflow 금오공과대학 컴퓨터공학부 컴퓨터공학전공

50  삽입 예: 57삽입 57 삽입 o에 여유가 있으므로 그냥 삽입 o o’ p o o’ p 58 60 58 60 50 59
62 65 50 57 59 62 65 금오공과대학 컴퓨터공학부 컴퓨터공학전공

51  삽입 예: 54삽입 54의 삽입 o에 overflow  50,54,57의 중간값이 54를 기준으로 o와 o”으로 분할
54가 부모로 삽입 o 58 60 o o’ p 50 57 59 62 65 o o o’’ 54는 부모 노드 f로 이동 50 57 50 57 overflow 금오공과대학 컴퓨터공학부 컴퓨터공학전공

52  삽입 예: 54삽입(계속) 부모 노드 f에 54 삽입 f가 overflow  54,58,60의 중간 값인 58을 기점으로 f와 f’으로 분할 o는 58보다 작으므로 f에 o’은 58보다 크므로 f’에 58이 부모로 삽입 overflow f f f’ 58 60 54 ^ 60 ^ 58은 부모 노드 b에 삽입 o o’ p o o’’ o’ p 금오공과대학 컴퓨터공학부 컴퓨터공학전공

53  삽입 예: 54삽입(계속) 부모 노드 b에 58 삽입 부모 b에 overflow  19,43,58 중 43을 기점으로 b와 b’으로 분할 19,43,58 중 43이 부모로 삽입 b b b’ 19 43 19 ^ 58 ^ 43은 부모 a에 삽입 d e f d e f f’’ 금오공과대학 컴퓨터공학부 컴퓨터공학전공

54 부모 노드 a에 43 삽입 ^ · · · · · · · 69 43 69 a a b c b b’ c
금오공과대학 컴퓨터공학부 컴퓨터공학전공

55 ▶ 연산(2) 삭제 삭제키가 리프 노드인 경우 그냥 삭제 삭제키가 리프가 아닌 노드에 존재
후행키 값과 자리교환(후행키-항상 리프에) 리프노드에서 삭제 언더플로 : 키수 < ⌈ m/2 ⌉ - 1 재분배 (redistribution) 최소키 수 이상을 포함한 형제노드에서 이동 (형제노드의 키 → 부모노드 → 언더플로 노드) 합병 (merge) 재분배 불가능시 이용 (형제노드 + 부모노드의 키 + 언더플로 노드) 금오공과대학 컴퓨터공학부 컴퓨터공학전공

56  삭제 예 60의 삭제 20의 삭제 b b b f f f 60 62 62 o p o p o p 50 50 50 62 65
후행키와 자리교환 f f f 60 62 62 o p o p o p 50 50 50 62 65 50 60 65 50 65 b b 최소키 수 이상을 포함한 형제노드에서 이동 e e 26 40 30 40 l m n l m n 20 30 36 42 26 36 42 금오공과대학 컴퓨터공학부 컴퓨터공학전공

57 (2) B+-트리 인덱스 세트 (index set) 순차 세트 (sequence set) 내부 노드
리프에 있는 키들에 대한 경로 제공 직접처리 지원 순차 세트 (sequence set) 리프 노드 모든 키 값들을 포함 cf. B-Tree인 경우에는? 순차 세트는 순차적으로 연결  순차처리 지원 내부 노드와 다른 구조 금오공과대학 컴퓨터공학부 컴퓨터공학전공

58  차수가 3인 B+-트리 a 69 인덱스 세트 b c 20 43 110 d e f g h 순차 세트 15 20 35 40 43 55 69 70 90 110 120 125 금오공과대학 컴퓨터공학부 컴퓨터공학전공

59 ▶ B+-트리(2) 특성 노드 구조 ＜n, P0, K1, P1, K2, P2, … , Pn-1, Kn, Pn>
n : 키 값의 수 ( 1≤n<m ) P0, …, Pn : 서브트리에 대한 포인터 K1, …, Kn : 키 값 루트는 0 또는 2에서 m개 사이의 서브트리를 가짐 루트와 리프를 제외한 모든 내부 노드는 최소 ⌈m/2⌉개, 최대 m개의 서브트리를 가짐 리프가 아닌 노드에 있는 키 값의 수는 그 노드의 서브트리 수보다 하나 적음 모든 리프 노드는 같은 레벨 한 노드 안에 있는 키 값들은 오름차순 금오공과대학 컴퓨터공학부 컴퓨터공학전공

60 ▶ B+-트리(3) Pi, (0≤i≤n-1)가 지시하는 서브트리에 있는 노드들의 모든 키 값들은 키 값 Ki+1보다 작거나 같다. Pn이 지시하는 서브트리에 있는 노드들의 어떤 키 값도 키 값 Kn보다 크다. 리프 노드는 모두 링크로 연결되어 있다. 리프 노드의 구조     ＜q, <K1, A1>, <K2, A2>, … , <Kq, Aq>, Pnext> Ai : 키 값 Ki를 가지고 있는 레코드에 대한 포인터 q : ⌈m/2⌉≤ q Pnext : 다음 리프 노드에 대한 링크 금오공과대학 컴퓨터공학부 컴퓨터공학전공

61 ▶ B+-트리(4) B-트리와의 차이점 인덱스 세트에 있는 키 값 :
리프 노드에 있는 키 값을 찾아가는 경로만 제공하기 위해서 사용 인덱스 세트에 있는 키 값은 사실상 모두 순차 세트에 다시 나타남 인덱스 세트의 노드와 순차 세트의 노드는 그 내부 구조가 서로 다름 리프 노드 : 키 값과 이 키 값을 가진 레코드의 포인터가 함께 저장 인덱스 세트에 있는 노드 : 키 값만 저장된다. 노드에 저장할 수 있는 원소의 수도 서로 다름 순차 세트의 모든 노드가 순차적으로 서로 연결된 연결 리스트 효율적 순차 접근 금오공과대학 컴퓨터공학부 컴퓨터공학전공

62 ▶ B+-트리의 연산 탐색 삽입 삭제 B+-트리의 인덱스 세트 : m-원 탐색 트리와 같음 리프에서 검색 B-트리와 유사
리프의 오버플로우 (분할)시 중간 키 값이 부모 노드, 분할노드에 모두 존재 순차 세트의 연결 리스트의 순차성 유지 삭제 재분배, 합병이 필요 없는 경우 리프에서만 삭제 인덱스 세트의 노드는 분리자(separator)로 유지 ∵ 다른 키 값을 탐색하는데 분리 키 값으로만 사용 재분배: 인덱스 키 값 변화, 트리 구조 유지 합병 : 인덱스의 키 값도 삭제 금오공과대학 컴퓨터공학부 컴퓨터공학전공

63  삭제 예 재분배, 합병이 필요 없는 경우 리프에서만 삭제 예 인덱스 세트의 노드는 분리자(separator)로 유지
∵ 다른 키 값을 탐색하는데 분리 키 값으로만 사용 예 43을 삭제 No underflow 인덱스 43은 그대로 리프의 43만 삭제 69 20 43 110 15 20 35 40 55 69 70 90 110 120 125 금오공과대학 컴퓨터공학부 컴퓨터공학전공

64  삭제 예 재분배: 인덱스 키 값 변화, 트리 구조 유지 예: 리프의 125를 삭제 underflow 재분배 가능 110
재분배: 인덱스 키 값 변화, 트리 구조 유지 예: 리프의 125를 삭제 underflow 재분배 가능 110 70 90 110 120 125 69 20 43 90 15 20 35 40 55 69 70 90 110 120 금오공과대학 컴퓨터공학부 컴퓨터공학전공

65  삭제 예 합병 : 인덱스의 키 값도 삭제 예: 키 값 55의 삭제 Underflow 재분배 불가능  합병
필요없는 분리 키값 43도 삭제 20 43 15 20 35 40 55 69 69 20 90 15 20 35 40 69 70 90 110 120 금오공과대학 컴퓨터공학부 컴퓨터공학전공

66 B- B+ 트리는 어디에 사용되는가? 그 효과는 무엇인가? 금오공과대학 컴퓨터공학부 컴퓨터공학전공

67 ▶ 해싱 방법 다른 레코드 참조 없이 목표 레코드 직접 접근 키 값과 레코드 주소 사이의 관계 설정
직접 파일(direct file) 키 값과 레코드 주소 사이의 관계 설정 해싱 함수(hashing function) 키 값으로부터 주소를 계산 사상 함수(mapping function) : 키 → 주소 삽입, 검색에도 이용 B- B+ 트리와 비교하였을 때, 장점은 무엇인가? 금오공과대학 컴퓨터공학부 컴퓨터공학전공

68 (1) 버킷 해싱 · 버킷(bucket) : 하나의 주소를 가지면서 하나 이상의 레코드 를 저장할 수 있는 파일의 한 구역
버킷 크기 : 저장장치의 물리적 특성과 한번 접근으로 채취 가능한 레코드수 고려 버킷 해싱 : 키 → 버킷 주소 충돌(collision) : 상이한 레코드들이 같은 주소(버킷)로 변환 버킷 만원 - 오버플로우 버킷 한번의 I/O가 추가됨 B- B+ 트리와 비교하였을 때, 단점은 무엇인가? 버킷 1 2 버킷 주소 3 해싱 함수 h(k) 4 레코드 키값(k) n-1 n 금오공과대학 컴퓨터공학부 컴퓨터공학전공

69 (2) 확장성 해싱(1) 충돌 문제에 대처하기 위해 제안된 기법 특정 레코드 검색 - 1~2번의 디스크 접근
모조키(pseudokey) 확장성 해싱 함수: 키 값  일정 길이의 비트 스트링(모조키) 모조키의 처음 d 비트를 인덱스로 사용 디렉터리 헤더 : 정수값 d를 저장 d = 전역 깊이(global depth) 버킷들을 지시하는 2d 개의 포인터 디스크에 저장 금오공과대학 컴퓨터공학부 컴퓨터공학전공

70 (2) 확장성 해싱(2) 버킷 정수 값 p( <= d)가 저장된 헤더가 존재 p = 지역 깊이 (local depth)
번호 디렉터리 레코드의 모조키가 시작하고 있는 비트 스트링 p= 3 d= 3 1 2 3 4 000 ··· 000 3 001 001 ··· 010 011 2 100 01 ··· 101 1 110 1 ··· 111 금오공과대학 컴퓨터공학부 컴퓨터공학전공

71 (2) 확장성 해싱(2) 추가 1101이 추가되면 디렉터리 3 3 000 3 001 010 011 2 100 101 1 110
p= 3 d= 3 1 2 3 4 000 3 001 010 011 2 100 101 1 110 111 금오공과대학 컴퓨터공학부 컴퓨터공학전공

72 ▶ 확장성 해싱의 연산 (1) 검색 모조키의 처음 d비트를 디렉터리에 대한 인덱스로 사용
접근된 디렉터리 엔트리는 목표 버킷에 대한 포인터를 제공 검색 예 1) 키 값 k → 모조키 2) 모조키의 처음 3비트(=d) 사용 디렉터리의 6번째(101) 엔트리를 접근 3) 엔트리는 4번째 버킷에 대한 포인터 키 값 k를 가지고 있는 레코드가 저장되어있는 곳 p= 1 : 모조키 비트 1로 시작하는 레코드 저장 디렉터리 p= 3 d= 3 1 2 3 4 000 001 3 010 011 2 100 101 1 110 111 금오공과대학 컴퓨터공학부 컴퓨터공학전공

73 ▶ 확장성 해싱의 연산 (2) 저장 모조키의 처음 d 비트를 이용 디렉터리 접근 포인터가 지시하는 버킷에 레코드 저장
오버플로 처리(버킷이 만원일 때) 새로운 버킷을 생성 오버플로 버킷의 레코드들과 새로 저장할 레코드를 오버플로 버킷과 새로 할당한 버킷에 분산 오버플로 버킷의 p+1값에 따라 기존 버킷과 새로 할당된 버킷의 깊이 값 p는 모두 (p+1)로 설정 디렉터리 오버플로( d< (p+1)인 경우 ) 디렉터리 크기 증가(d 값을 1 증가시킴) 포인터 조절 금오공과대학 컴퓨터공학부 컴퓨터공학전공

74  버킷 오버플로 예 버킷 4가 만원인 상태에서 모조키가 110으로 시작하는 레코드 삽입 버킷을 분할 : 빈 버킷 할당
모조키 11로 시작되는 레코드를 새 버킷으로 이동 디렉터리의 110과 111의 포인터 값은 새 버킷을 지시하도록 변경 분할된 버킷의 깊이는 2로 증가 디렉터리 3 버킷 1 2 3 4 레코드의 모조키가 시작하고 있는 비트 스트링 3 000 ··· 000 3 001 001 ··· 010 011 2 01 ··· 100 101 1 110 1 ··· 111 금오공과대학 컴퓨터공학부 컴퓨터공학전공

75 1101이 추가되면 디렉터리 p= 3 d= 3 1 2 3 4 000 001 3 010 011 2 100 101 1 110 111 디렉터리 3 버킷 레코드의 모조키가 시작하고 있는 비트 스트링 3 000 ··· 000 3 001 001 ··· 010 011 2 100 01 ··· 101 2 110 10 ··· 111 2 11 ··· 금오공과대학 컴퓨터공학부 컴퓨터공학전공

76  디렉터리 오버플로 예 첫번째 버킷(000)이 만원인 경우에 레코드 삽입
전역 깊이(d) < ( 지역 깊이(p) + 1) d를 증가시켜 디렉터리 확장 : 2배 증가 빈 버킷을 할당받아 모조키가 0001로 시작되는 레코드를 이동 디렉터리 헤더와 버킷 헤더에 있는 깊이 값 증가 포인터 조정 000 001 010 011 100 101 110 111 디렉터리 3 2 금오공과대학 컴퓨터공학부 컴퓨터공학전공

77  디렉터리 오버플로 예 디렉터리 버킷 레코드의 모조키가 시작하고 있는 비트 스트링 4 4 0000 ··· 4 0001 ···
0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 4 0001 ··· 3 디렉터리 3 3 001 ··· 000 3 001 2 010 2 01 ··· 011 100 101 2 110 2 111 2 10 ··· 2 11 ··· 금오공과대학 컴퓨터공학부 컴퓨터공학전공

78 ▶ 확장성 해싱의 연산 (3) 삭제 삭제할 레코드를 찾아 삭제 한 버킷에 하나만 있는 레코드를 삭제하는 경우
버디 버킷을 검사, 두 버디에 있는 레코드들이 한 버킷에 들어갈 수 있으면 합병 버디 버킷(buddy bucket) : 똑같은 깊이 값(p)을 가지고 있고 그 모조 키들의 처음 (p－1)비트들은 모두 같은 버킷 버킷의 새로운 깊이 값은 p－1 모든 버킷들의 깊이 값이 디렉터리 깊이 값보다 작게 되면 디렉터리의 깊이를 하나 감소(d ← d-1) 디렉터리 크기는 반으로 줄어듦 포인터 엔트리들을 적절히 재조정 금오공과대학 컴퓨터공학부 컴퓨터공학전공