제6장 파일과 색인

(1)

- 데이터베이스 시스템 –

제6장 파일과 색인

2013. 12. 03

가천대학교 IT대학

컴퓨터미디어융합학과

(2)

목 차

6.1 디스크와 파일 6.2 색인 구성 6.3 B-tree 색인

6.4 Hash 색인

6.5 다중키 색인

(3)

6.1 디스크와 파일

파일 구성:레코드를 파일에 배치하는 방법.  비용 결정.

6.1.1 저장장치

H/W cost

Access time

CPU : clock cycle: 0 giga Hz/sec

Memory: load/fetch cycle: 00 nano sec Disk: block get/put: 00 mili sec

일정 비용으로 무작위 페이지를 검색.

제6장 파일과 색인

CPU

Cache

Main Memory

Tape, USB

Primary Storage

Secondary Storage Magnetic Disk

Tertiary Storage Primary Storage

(4)

6.1 디스크와 파일

디스크 구조

- Disk controller: 디스크 드라이브 구동 및 컴퓨터 연결 - Arm/Header: 팔 끝에 읽고/쓰기 센서

- Cylinder: 각 원반에서 같은 트랙의 집합 - Track: 축을 중심으로 동심원

- Secter: 트랙을 일정한 각도로 분할, 디스크 특성으로 크기는 불변

- Block : 몇 개의 섹터로 구성, 크기 조절 가능.

성능: 전송율. 00-000Mb/sec

(5)

6.1 디스크와 파일

디스크 성능

- access time: 읽기/쓰기 요구 접수부터 전송 시작 시간

seek time: 2-30msec

avg seek time : 4-10msec

- rotational latency time: 4-11msec - data transfer rate: 25-100 mb/sec - MTTF mean time to failure :

회전 축 arm

head

트랙

섹터 블록

(6)

6.1 디스크와 파일

6.1.2 디스크 공간 관리

Disk space manager: DBMS

페이지 단위로 공간 관리. 페이지 = 블록

File Manager: OS

디스크 레코드들의 파일을 관리

- 레코드관리: 레코드 유일 식별자 rid(record id) - 색인관리: 탐색 키의 값으로 rid관리

ex. “디스크 d에서 실린더 c, 트랙 t의 블록 m을 읽기”

제6장 색인

(7)

6.1 디스크와 파일

6.1.3 Buffer Manager

디스크 장치와 주기억장치 buffer pool로 페이지 이동.

파일과 색인 관리 - 스케줄링:

- 파일 구성:

- 버퍼-교체 기법 -멀티 버퍼링:

인터리브 방식: single CPU,

제6장 색인

(8)

6.1 디스크와 파일

6.1.4 파일 구성

- 히프 파일: 비순서 파일

- 순차 파일: 특정 순서로 구성된 파일. 키 순서,,  색인: 레코드 위치를 찾기 위해 구성된 파일.

- 해시 파일: 키 값으로 레코드의 위치를 찾을 수 있는 파일

파일 형식

- 고정길이 레코드, 가변길이 레코드 - spanned, unspanned

제6장 색인

(9)

6.1 디스크와 파일

6.1.4 파일 구성

제6장 색인

record 1 record 2 record 3

record 4 record 5 record 6

block # i

block # i+1

(a) 비신장 방식

record 1 record 2 record 3 record 4

record 5 record 6

block # i P

record

record 7 record P

(10)

6.1 디스크와 파일

6.1.4 파일 구성

파일 연산

Record-at-a-time

- open, close: 버퍼 할당, 헤더 검색, 파일 포인터 설정 및 해제 - find

- insert - delete - modify

- scan: 한번에 하나씩 모든 레코드 읽기 Set-at-a-time

- FindAll - deleteAll

제6.1장 파일구성

(11)

6.1 디스크와 파일

6.1.4 파일 구성 레코드 접근 방식

- 레코드에 순서 부여, 블록 내 레코드에 순서 부여 - i 번째 레코드: [i/bfr]에 위치하고,

블록 내에서는 ( i mod bfr) 번째 레코드.

 relative file

제6장 색인

(12)

6.1 디스크와 파일

6.1.5 파일 종류

Heap(or pile) 파일

 가장 단순한 화일

 일반적으로 삽입 순서대로 화일에 저장

 삽입 시 화일 끝에 첨부, 중간에 공간이 있으면 삽입 가능

 탐색 시 모든 레코드 순차 접근

 삭제 시, 삭제된 레코드가 차지하던 공간을 재사용하지 않 음

 좋은 성능을 위해 주기적으로 재조직해야 삽입 외에는 비효율

제6장 색인

(13)

6.1 디스크와 파일

6.1.5 파일 종류

Sequential file, Ordered file

 필드 값에 따라 순서대로 저장

 일반적으로 탐색 키 값의 순서에 따라 저장됨

 탐색 키는 순차 화일을 정렬하는데 사용되는 필드를 의미

 삽입 연산은 순서를 고려하기 때문에 시간이 많이 걸릴 수 있음

 삭제 시 삭제된 공간이 빈 공간으로 남아서 비효율적

제6장 색인

(14)

6.1 디스크와 파일

6.1.5 파일 종류

Sequential file, Ordered file key seq. file.

장점:

탐색 키 사용 시 검색이 효율적. 2진 탐색(고속): log₂b 전체 읽기 시 효율적

부분 탐색 가능.

단점;

삽입, 삭제 ?? overflow file

제6장 색인

(15)

6.1 디스크와 파일

6.1.5 파일 종류

Hash 파일. 상대 파일 해시 함수, 해시 키 직접 탐색. O(1) 삽입, 삭제 ??

알고리즘?? 내부 해싱, 외부 해 싱

제6장 색인

key 해시

함수 h

1 2 0

N-2 N-1

... ...

...

h(key) = key mod N

...

오버플로우 페이지들

버켓

...

(16)

6.2 색인 구성

6.2.1 색인 개념

파일 안의 레코드를 찾아주는 보조 파일.

Primary index

기본 키 값으로 해당 레코드를 찾아주는 파일.

순서 파일의 순서 키 필드에 대한 색인: 물리적 순서 Clustering index

키가 아닌 필드에 따라 물리적으로 정렬된 중복을 허용하는 색인.

Secondary index :

파일의 물리적 순서와 다른 순서로 구성되는 검색 키의 색인.

제6.2장 색인 구성

(17)

6.2.1 색인 개념 색인 구성

단일 단계 색인 기본 색인

클러스터링 색인 보조 색인

다단계 색인

희소 색인, 밀집 색인 B-tree 색인

Hash 색인 다중키 색인

(18)

6.2.1 색인 개념 색인의 장점

 검색 속도 향상

 소수 레코드 수정, 삭제 시 연산 속도 향상

Ex.

 테이블이 매우 크고, 질의에서 일부(예, 2%~4%)를 검색하 고, WHERE절이 잘 표현되었을 때 특히 성능에 도움이 됨

단점

 추가 공간 소요.

 연산 속도 저하

(19)

6.2.1 색인 개념 색인 평가

- 접근 형태: 특정 속성값을 가진 레코드를 찾는 방법 - 접근 시간: 시간

- 삽입 시간: 위치 탐색 시간 + 색인 구조 갱신 시간 - 삭제 시간: 위치 탐색 시간 + 색인 구조 갱신 시간 - 공간 부담: 색인을 위해 사용되는 공간

(20)

6.2.2 색인 구조 primary index

순서 키 필드와 디스크 블록의 주소로 구성된 순서 파일 색인 레코드: (순서 키 필드, 블록 포인터)

<K(i),D(i)> = <기본 키,디스크 주소>: for 색인 레코드 i 색인 레코드의 수 = 파일의 블록 수

anchor record: 각 블록의 첫 번째 레코드 희소 색인.

레코드의 삽입 ? 레코드의 삭제 ? 레코드의 삽입?

(21)

6.2.2 색인 구조

primary index

44011

블록 앵커

블록 포인터

44011

사번 성명 소속 생년월일

44012 44110

44115 44190

44211

45330 45331 44211

44255 44115 44116 44156

<K(i),P(i)>

...

block 1

직위

기본키

45330

...

block 0

block i

block n primary index file

44190 block 2

...

레코드 크기: 400바이트

(22)

6.2.2 색인 구조 Clustering index

키가 아닌 필드에 따라 물리적으로 정렬된 색인.

블록 포인터

1

사번 성명 부서번호 생년월일

1 1 2

2 3 3 3

28 28

49 49 50 50

...

block 1

1 2 3 4

27 28

...

직위 block 0

block i

block n clustering index file

3 4 4 4 block 2

2

3

...

4

50

...

클러스터링 색인 값

부서번호

레코드 크기: 400바이트 레코드 수: 10,000개

(23)

6.2.2 색인 구조 Secondary index :

기본 색인이 존재하는 파일을 보조하는 색인 - 기본 키가 아닌 다른 순서로 구성되는 색인.

- 고유하지 않은 필드 값으로 검색할 필요성 부분검색

- 제목만 알고 자세한 내용을 찾을 때 내용기반 색인

구성 방식

- 기본 키 색인 활용 방식

(24)

6.2.2 색인 구조

Secondary Index 면허번호: unique

1

보조 키 블록 포인터 44011

사번 직위 생년월일

44012 44110

44115 44116 44156

44190 2

3

1989 2000

...

6 면허번호

11 19 33

2 13 10 2000

7 8 1 9

...

45330 45331 45369

14 1989

3 4 성명

11

secondary index file

block 0

block 1

block 2

block n 면허번호

. ...

레코드 크기: 400바이트 레코드 수: 10,000개

(25)

6.2.2 색인 구조

Secondary index file: 중복을 허용하는 색인 파일

Inverted file: 내용으로 키를 찾아 내용을 찾는 파일

1

보조 키 bucket 포인터 2

3

50

...

bucket

45337

사번 직위 생년월일

44012

44190

6 부서번호

35 13 3

2 25 10 50

7 8 1 45

42250

14 12 3 성명

1

2 block 0

block 1

block 2

block n

부서번호 ...

. .

블록 포인터 bucket

0

bucket 1

bucket m bucket

2

...

레코드 크기: 40바이트

(26)

6.2.3 색인 순차 파일

갱신: 가장 간단

삽입: overflow  재편성

삭제: 실제 삭제 시  재편성.

442

prime data area

block 0

...

442 ptr 450 ptr 478 ptr 503 ptr

455 461 472

450 470

480 490 569

478 505

677

block 1

block i

block n

677 ptr

...

458 463 477

457 471 block x

index area

..

.. ...

...

(27)

6.2.3 색인 순차 파일

ISAM의 색인 구조

450 ptr ptr ptr

344 ptr ptr ptr

344 ptr 435 ptr

200 ptr 234 ptr 477 ptr 488 ptr

480 ptr ptr ptr

480 ptr 506 ptr

444 ptr ptr ptr

overflow index

root Level 0

Level 1

Level 2 = leaf page

ptr ptr ptr

(28)

6.2.4 다단계 색인

파일이 커지면 색인이 커지고, 색인 탐색 시간도 증대 Dense index

색인 레코드가 파일에 있는 모든 검색 키 값에 대해 구성.

Sparse index

색인 레코드가 파일에 있는 검색 키 값의 일부에 대해 구성.

(29)

6.2.4 다단계 색인

Dense index Sparse index

포인터

1

1 1 2

2 3 3 3

prime data file block 1

1 2 3 4

...

직위 block 0

4 5 5 6 block 2

2

4

...7 색인 값

부서번호 5 6 7 8

포인터

1

1 1 2 2 3 3 3 block 1

1 4 7 12

직위 block 0

4 5 5 block 2

2

4 색인 값

(30)

Dense index Sparse index Multi-index data record: 500 bytes, index: 25 bytes.

1. 레코드 수가 1,000개일 때 디스크 접근 비용은?

1 block = 500 bytes

2. 레코드 수가 10,000개일 때 디스크 접근 비용은?

1 block = 2,000 bytes

3. 레코드 수가 100,000개일 때 디스크 접근 비용은? 1 block = 4,000bytes

1

100 200 300

1 2

2 3 20

4

1000

100 101 102

Sparse Index Prime Data FIle

2 19 20 1981 1000

Dense Index

(31)

6.3 B-Tree Index

Static Tree

Tree 효율: 높이, 구조,

skewed tree: 순차 파일과 유사

대안

:

잎 노드의 높이가 일정

Balanced Tree, Dynamic Tree

추가, 삭제: 모든 잎 노드 높이가 항상 동일 탐색 효율 우수.

ex. Almost B-tree, B-tree, B*-tree, B⁺-tree

중간 노드 색인

파일

데이터 파일 잎

노드

root

(32)

Order가 k인 B-tree

노드의 반을 비워두고,

색인 증가 시: 노드 분열, 감소 시: 노드 통합 k = (한 노드의 색인 수)/2

1) 잎 노드: 높이 동일.

2) 모든 노드: (k - 2k) 개의 키 뿌리: (1 - 2k) 개의 키

3) 뿌리: 0에서 최대 2k+1개의 자식 노드

뿌리와 잎 이외 노드: (k+1) - (2k+1)개의 노드.

제6.3장 트리 색인

(33)

B-tree와 B+-tree 노드

색인 엔트리 색인 값 data pointer

1 2 3 4

child node pointer

degree = k = 2

child pointer

data

1 2 3 4

degree = k = 2

child

forward pointer backward

pointer

(34)

B-Tree와 B

⁺

-Tree Index

bucket이 없는 경우

B-tree B⁺-tree

4 8 23 47

16

16 23 4 47 8

고 객 파 일 B-tree 색인

16 23 4 47 8

고 객 파 일 16

4 8 16

23

23 47

(35)

B-Tree

삽입 순서 25,15,5

(2) 25 삽입 25 (3) 15 삽입

15 25

(4) 5 삽입

15 25

인노드 정렬

5 15 25

중간 노드의 올라가기

인노드의 생성 (1) 빈 노드 생성

5

15

5 15 25

노드 분열과 새 노드 생성 노드 내 정렬

(36)

B-Tree

삽입 순서 10,30,20

5 25

15

(5) 10 삽입, 30 삽입

5 10 25 30

15

(6) 20 삽입

5 10 25 30

15

인노드의 생성 20

20 30

25 새 노드의 생성과 연결

15 25

20 25 30 색인의 정렬

중간 색인의 올라가기

(37)

B⁺-Tree

삽입 순서 25,15,5

(2) 25 삽입 25 (3) 15 삽입

15 25

(4) 5 삽입

15 25

노드 생성과 인노드 배치

5 15 25

중간 색인의 올라가기 15

인노드의 생성 (1) 빈 노드 생성

5

5 15 25 인노드 정렬

포인터 연결

(38)

B⁺-Tree

삽입 순서 10,30,20

제6장 색인

30

(7) 20 삽입

30

30 (6) 30 삽입

15 25

(5) 10 삽입

5 10 15 25

15

새 노드 생성과 연결 인노드 생성

5 10 15 25

15

5 10 15 25

15 30

30

15 25 20 인노드 생성

25 색인 올리기

(39)

6.4 해시 색인

기존 기술

: 원하는 레코드 탐색을 위하여 다른 레코드를 읽어 야

해 싱: 속성 값을 직접 주소 값으로 변환

키 값을 이용하여 해당 레코드의 주소를 직접 탐색.

키 값으로 버켓 주소를 결정:

자료 페이지들은 버켓으로 구성. 버켓: 자료 페이지 + 초과 페이지

해시 함수:

키 값(매우 큰 범위)  정수 값(작은 범위)

ex. 학번: 1982013001 - 1998830238, 레코드: 0 – 수만.

분포가 균일할수록,,

제6.4장 해시 색인

(40)

정적 해싱

테이블의 크기가 고정된 해싱.

버켓의 수가 고정된 해싱: 해싱 함수가 일정.

동적 해싱

버켓의 수가 가변적인 해싱: 해싱 함수가 가변적

내부 해싱: 배열에 대한 해싱.

외부 해싱: 디스크 파일에 대한 해싱.

(41)

내부 해싱: 배열에 대한 해싱.

외부 해싱: 디스크 파일에 대한 해싱.

h(CID) : CID mod N

0 1 2

...

CID Name Address Job

330 451

753

Credit

N-2 N-1

853 570 N

N+1

N+p

next N+1 -1

N

N+9 -1 Data fields

Overflow pointer

...

Address space

Overflow space

(42)

내부 해싱: 배열에 대한 해싱.

외부 해싱: 디스크 파일에 대한 해싱.

(43)

직접 해싱: 키 값  레코드의 주소

간접 해싱: 키 값  버켙 주소  레코드의 주소

학번  5번 버켙  205번 레코 드

h(200503228)  7

120

100 bucket 0

eid 사원번호

key

bucket 1

bucket i

bucket 9

h

...

211 241 111

261

119 109

...

bucket 10 371

311

h(key) : key mod 10

(44)

해싱 충돌과 대책

해시함수: 고루 분포해야

아니면, 충돌 시 다음 레코드에 저장

 최악의 경우 : 모든 레코드가 다음 주소에 저장  선형 탐색

1995044018 1996044018 키1 = 1995044018

키2 = 1996044018

hash(키1) = 018 hash(키2) = 018 hash() = 키 mod 1000

00 01 02 03 . . 018 019 020 021

. 파 일

(45)

충돌 대책: 좋은 해시 함수, 자료구조

버켙

00 01 . 09

. 18

. 33

김기일 박상기

이기환 홍성도 장사희

hash(key) 김길동

예비 버켙

키= 고객번호

(46)

충돌 대책: 좋은 해시 함수, 자료구조

hash(key)

김길동

박상기

이기환 홍성도 버 켙 09

기본 파일 . .

000 001 002 003 004 005 006 007 008

079 레코드번호 김기일

장사희 버 켙 0

버 켙 18

버 켙 33

(47)

정적 해싱의 문제점

테이블 크기 예측의 부정확, 곤란  충돌 야기 자료의 대폭 증가 시 대처 곤란

확장형 해싱

레코드 수의 증감  해시 함수 변경  재편성 불필요

(48)

디렉토리 버켓

0 0

bucket 0 0

오정해 이인규 0...

전체 깊이 사용 깊이

색인과 해싱의 비교

접근 형태: 한번에 극소수의 레코드 접근?

삽입과 삭제의 빈도수?

부분 탐색이 많은가?

select A1,A2, ..., An from r

where Ai ≤ C2 and Ai ≥ C1

색인과 해싱의 통합

IMS: HSAM: 순차 탐색

HISAM: 루트는 색인, 기타는 순차 탐색 HDAM: 루트는 해싱, 기타는 포인터 HIDAM: 루트는 색인, 기타는 포인터

(53)

6.5 다중키 색인

select item from purchase

where b-name = "성남” and c-name = "김기동

그리드 구조

다차원 테이블에 레코드 포인터 기억

단일 키 탐색에도 적합 ex. 부분 탐색

지점

고객

성남 부산 대구 인천 대전 광주

강동호 김기동 나운규 백문기

성남 강동호 성남 김기동 부산 김기동 부산 백문기

그리드 파일

(54)

복수키

name major

h(major) = 00 Kim, 1990, 4000

Lee, 1991, 3000 Kee, 1990, 2000

Yoo, 1992, 5000 Rho, 1990, 4000

Park, 1990, 6000 Kim, 1989, 4000 Lee, 1990, 3000

3000 4000 5000 6000

2000 3000 4000 4000

h₁ h₂

h(major) = 11 h(name) = 00

h(name) = 10 h(name) = 01

name으로 기본키, major로 보조키를 구성한 해싱 파일 구조

<major, rid>

primary data file secondary index

(55)

1. 디스크 장치의 특성을 설명하시오. 데이터베이스는 왜 디스크를 이용 하는가?

2. 공간 관리기, 버퍼 관리기, 파일 관리기를 설명하시오 3. DBMS는 왜 OS의 파일 관리기를 선호하지 않는가?

4. DBMS와OS의 버퍼 관리기는 어떻게 다른가?

5. 히프 파일, 순서 파일, 해시 파일의 특성을 설명하시오 6. 신장 레코드와 비신장 레코드의 효율성을 설명하시오

7. 고정길이 레코드와 가변길이 레코드의 효율성을 설명하시오 8. 색인의 필요성을 설명하시오.

9. 기본 키, 보조 키, 클러스터링 키의 차이점과 용도를 설명하시오.

10. 비클러스터링 색인의 실례를 들어보시오.

11. 레코드 수가 100만개 일 때 접근 비용은? 1 레코드는 200bytes이고, 1 블록은 1,000byte이고, 1 색인은 20bytes이다. 1 색인은 4 블록을 가

제6장 익힘 문제

(56)

13. 내용기반 검색이란? 어떻게 구현하는가? 문제점과 대책은 무엇인가?

14. 색인 순차 파일의 장단점과 대책을 설명하시오.

15. B-tree 색인을 정의하고, 장단점을 기술하시오.

16. B-tree와 B⁺-tree의 차이점을 기술하시오.

17. 다음의 자료가 입력될 때 B-tree를(order=2) 구성하시오.

Data = 20, 25, 10, 80, 35, 60, 15, 45, 66, 76

18. Hash 색인을 정의하시오. 장단점을 기술하시오 19.확장형 해싱을 정의하시오.

20. 다음 자료가 입력될 때 확장형 해싱 색인을 작성하시오.

순서 고객 비트값 순서 고객 비트값 1 이효리 1000 4 이서진 1110 2 배용준 1100 5 이보영 0111 3 성유리 0110 6 이영애 0011 21. 복수 키를 구현하는 방법을 기술하시오.

제6장 익힘 문제