7. Secondary Index의 구성 방식 7. Secondary Index의 구성 방식

(1)

7. Secondary Index의 구성 방식 7. Secondary Index의 구성 방식

 기존 secondary index 관리의 문제점

동일한 d k 를 갖는 새로운 레코드가 입력될

 동일한 secondary key를 갖는 새로운 레코드가 입력될 경우, secondary index에 새로운 레코드 추가

 동일한 secondary key가 중복 가능

영남대학교 데이터베이스연구실 Algorithm: Chapter 7 (Page 21)

(2)

Composer index

Secondary key Primary key

Co pose de

BEETHOVEN ANG3795

BEETHOVEN OV DG139201 G

BEETHOVEN DG18807

BEETHOVEN RCA2626

COREA WAR23699

DVORAK COL31809

PROKOFIEV LON2312

RIMSKY KORSAKOV MER75016

RIMSKY-KORSAKOV MER75016

SPRINGSTEEN COL38358

SWEET HONEY IN THE R FF245

(3)

7.1 역 인덱스 (역 파일) 7.1 역 인덱 (역 파일)

 기본 개념

S d d 를 구조로 구현

 Secondary Index를 array 구조로 구현

 새로운 record 첨가 시, array에 포함 가능

필요한 작업: field rearrangement in existing record

 필요한 작업: field rearrangement in existing record

 Example

 문제점

 주어진 key에 대한 array space의 한계y y p



Internal fragmentation

(4)

Revised composer index

Secondary key Set of primary key references

ev sed co pose de

BEETHOVEN ANG3795 DG139201 DG18807 RCA2626

Secondary key Set of primary key references

DVORAK COL31809

COREA WAR23699

RIMSKY-KORSAKOV MER75016

PROKOFIEV LON2312

SWEET HONEY IN THE R

FF245

SPRINGSTEEN COL38358

역 파일(inverted file) 혹은 역 인덱스(inverted index) 구조

(5)

7.2 다중 리스트 파일(Multilist File) 7.2 다중 리 파일(Multilist File)

 구성 방식

보조 키에 대한 다중 리스트 인덱스 파일

 보조 키에 대한 다중 리스트 인덱스 파일 +

 데이터 파일 (각 보조 키에 대한 link field 포함)

(6)

다중 리스트 파일의 구조

다중 리 파일의 구

Beethoven LON ¦ 2312 ¦ Romeo and Juliet ¦ Prokofiev . . . Corea

Dvorak

RCA ¦ 2626 ¦ Quartet in C Sharp Minor . . . WAR ¦ 23699 ¦ Touchstone ¦ Corea . . .

Dvorak Prokofiev

Rimsky Korsakov

¦ ¦ ¦

ANG ¦ 3795 ¦ Symphony No. 9 ¦ Beethoven . . . COL ¦ 38358 ¦ Nebraska ¦ Springsteen

Rimsky-Korsakov Springsteen

S t H I th R

COL ¦ 38358 ¦ Nebraska ¦ Springsteen . . .

DG ¦ 18807 ¦ Symphony No. 9 ¦ Beethoven . . . MER ¦ 75016 ¦ Coq d’or Suite ¦ Rimsky

Sweet Honey In the R MER ¦ 75016 ¦ Coq d’or Suite ¦ Rimsky . . . COL ¦ 31809 ¦ Symphony No. 9 ¦ Dvorak . . .

¦ ¦ i li ¦ h

인덱스

DG ¦ 139201 ¦ Violin Concerto ¦ Beethoven . . . FF ¦ 245 ¦ Good News ¦ Sweet Honey In The . . .

데이터 파일

(7)

역 인덱스와 다중 리스트의 비교 역 인덱 와 다중 리 의 비

역 인덱스 다중 리스트

인덱스의 구성 가변 길이 고정 길이

(인덱스 관리가 용이) 데이터 파일의 변

경 여부

변경이 필요 없음

(인덱스를 사용하지 않는 프 로그래머에게 투명)

변경 필요(보조 인덱스 수 만 큼 링크 필드 추가)

검색 처리

경우에 따라 데이터 파일을 액세스할 필요없이 인덱스

파일에서 처리 가능 대부분의 경우에 데이터 파일 을 액세스하여야 함

(예: Beethoven이 작곡한 곡 의 수는?)

을 액세스하여야 함

(8)

7.3 역 인덱스의 개선

 기본 개념

7.3 역 인덱 의 개선

 Secondary index에서 Primary key reference들을 list 로 pointing

Primary key reference 수에 제한 없음

 Primary key reference 수에 제한 없음

 Internal fragmentation 

 새로운 record 삽입이 용이

(9)

Secondary key index

Lists of primary key references BEETHOVEN

COREA

ANG3795 DG139201 DVORAK

PROKOFIEV

DG18807 RCA2626

PROKOFIEV RCA2626

. .

.

WAR23699

.

COL31809

LON2312

Conceptual view of the primary key

. . .

Conceptual view of the primary key

reference fields as series of lists.

(10)

Improved revision of the composer index

LON2312 1

BEETHOVEN 3

0 0

Secondary Index file Label ID List file

p oved ev s o o t e co pose de

LON2312 -1

RCA2626 -1

BEETHOVEN 3

COREA 2

0 1

WAR23699 -1

ANG3795 8

DVORAK 7

PROKOFIEV 10

2 3

COL38358 -1

DG18807 1

RIMSKY-KORSAKOV 6

SPRINGSTEEN 4

4 5

MER75016 -1

COL31809 -1

SWEET HONEY IN THE R 9

6 6

7

DG139201 5

FF245 -1

8 9

(11)

Linked list 구현 방식의 장단점 Linked list 구현 방식의 장단점

 장점

S d k 의 중복이 없음

 Secondary key의 중복이 없음

 Record 삭제 시, secondary index에는 “-1”로 표현 Secondary index file 크기가 작아지므로 관리 용이

 Secondary index file 크기가 작아지므로, 관리 용이

 Primary key reference의 정렬 부담 완화

 구현 용이 (Both file : fixed length record)

 단점

 Clustering 개념 지원되지 않음 !!!

 Clustering 개념 지원하기도 어려움 !!!

 Then, How?

(12)

8. Binding 8. d g

 Key와 Physical address 간에 binding 시점

h i h fil d ( i k )

 At the time the files are constructed (primary key)

 At the time they are actually used (secondary key)

 Bind-at-construction의 장점

 Simple & fast access

 Secondary device를 자주 액세스할 경우, 특히 우수

 Bind-at-construction의 단점

 Data file의 재구성 시, index file 변경 (very expensive)

 안전하지 않다. 왜?

(13)

언제 Bind-at-construction을 사용하는가?

언제 Bind at construction을 사용하는가?

 Static data file

d d f 가 중요할 경우

 Rapid read performance 가 중요할 경우

 반대로 생각할 것 !