Database-17장

index structure

file에 제공되는 index는 보조 접근 구조이다
주어진 검색조건에 대응해 record를 검색할때 속도를 높여주기위한 목적으로 사용된다
기존에 저장되어 있는 물리적인 위치와 상관없이 대체방안을 제공하는 목적
indexing field에 대해 record를 효율적으로 검색하는 방법 제공

-single level index(정렬용도)
primary, secondary, and clustering
ISAM : 이 방법을 사용하는 file의 명칭

-multilevel indexes
btree 나 b+tree

Primary index

record가 정렬된 field에 대한 index

Clustering index

같은 방법으로 record가 정렬된 fiedl에 대해 index가 구성되는데, 그 field가 key가 아닌 것
같은 값을 같는 record가 여러개인 경우가 있다

file은 primary index , clustering index 둘중 한가지만 가질 수 있다.

Secondary index
-정렬되지 않은 field에 대한 인덱스
-Primary access method의 추가적인 보조기능 제공

Primary indexes

두 개의 field를 갖는 fixed length의 record형태의 file
index = <K,P> 키값, 그 키값이 저장되어 있는 주소
K : main file을 정렬하는 key field
P : disk block에 대한 포인터
한 index entry는 각각 데이터 블럭당 하나씩 존재한다

각각의 대표하는 하나의 record는 anchor record or block anchor라고 한다

특정 record 값을 찾기위해 해당되는 block을 바로 찾아갈 수 있는 기능 제공 이렇게 index entry가 block당 하나씩만 존재하는 경우 anchor record라 한다(전체가 다 메모리로 들어오므로 첫번째만 알고 있으면 된다)

모든 record에 대한 entry가 없기 때문에 sparse index라고 한다
모든 record데 대해 entry가 존재하는 경우 dense index라고 한다

Primary index = sparse index
secondary index =dense index

unspanned 방식이므로 bfr=4096/100을 계산후 할당한 뒤, 남는 공간은 버린다(96bytes)

정렬이 되어있기 때문에 binary search를 이용하면 Log2b=13 block access , 13block을 access하는데 만약 primary index가 구성되어 있다면?

primary index for the file 예시 log2(28) + 데이터 블럭 1개 = 6block access >> 성능향상

bfr=273 , 한 block에는 273개의 entry가 존재한다, block pointer는 7,500/273=28개가 필요하다
binary search의 경우 5idx block accesses + 1 data block access
index file의 크기가 작으면 MM에 위치시켜 한 블럭만으로 바로 찾아가는 방법이 가능하다

문제점
삽입,삭제등의 갱신이 부담스럽다

record를 삽입하기 위해서는
새로운 record를 위한 공간을 위해 record를 전부 움직여야하고, anchor record가 바뀌니 index file도 같이 바꿔주어야 한다

문제를 줄이기 위한 수단
-overflow file 사용
-linked list를 사용하여 찾아갈 수 있게 한다

record가 삭제되는 경우 delete marker 이용

Clustering index
정렬키가 nonkey field - clustering field

Ordering field가 특별한 값을 같는경우 primary index,그렇지 않으면 clustring index

block당 같은 record만 저장하는 방식, 넘치면 linked list를 이용해 overflow file과 연결해준다

Primary key가 아닌 Zipcode에 대한 index를 구성하며, Zipcode는 1000가지의 종류가 존재한다(index entry가 1000개, 평균 300record가 존재)

Secondary Indexes

-특정 record 검색시 PK로만 하진 않는다, 검색을 빠르게 해주기 위해 다른 field에 대해 index를 만드는데 이것을 Scondary index라고 한다.
-dbms는 자동으로 primary index를 만들어준다
-block이 아닌 record당 하나의 entry가 생기기 때문에 dense index를 갖는다
-secondary index가 존재 하지 않으면 linear search를 해야하기 때문에, 이런 기능은 매우 효율적인 검색 기능을 제공해 준다

index field value가 있는 곳에 대한 모든 block pointer가 존재

Secondary index의 key가 unique한 값을 갖는데 Nonkey Field인 경우

해당 키값 하나에 대해 여러가지 record가 발생

나올때마다 index entry를 중복시켜주는 방법
가변길이 entry를 이용하는 방법 (좋은 방법이 아니다)
level을 증가시킨 고정길이 entry를 이용 , P는 data 에 대한 pointer가 아닌 pointer들의 집합block에 대한 pointer

example 3
Secondary key-a nonrodering key field(대체 키)에 대한 record 검색
secondary index가 없을때와 , 있을때의 예
index entries가 record개수 전체인것에 유의해야 한다

Multilevel indexes

fan out : binary search같은 탐색의 branch 수
bfri = bfri개수만큼의 fan-out을 가진다=fo
bfri를 이용해 tree의 차수를 가지면 검색이 매우 빨라진다
탐색시간은 log2b = logfo(b)로 변경

dense secondary index를 multilevel index로 바꾸어라

-두 트리는 data structure의 특별한 경우(균형잡힌 트리는 아니다)

record 값을 찾기 위한 특별한 타입의 tree, K는 키값 P는 pointer

B-trees

tree가 너무 한쪽으로 치우치면 트리의 장점을 전혀 받을 수 없다.
그렇기 때문에 balance를 유지하는것이 중요하고 이런 조건을 갖는것을 B-tree라고 한다 (B: balance)
임의의 삽입,삭제의 경우에도 tree의 balance를 맞춰준다

3차 B-Tree 예시, p=3(최소2개), key 수 = 2(최소1개), 오름차순 만족

33,75,124,122,123 순차 삽입하고 난 후 트리의 level이 하나 증가한다

nonordering key field에 대해 Btree를 만들고, p=23으로 가정. 각각의 노드는 2/3정도 차있다. pointer = 16, search key =15, fo = pointer = 16

block = 512, data pointer = 7, tree pointer =6, search key = 9의 값으로 해당 공식을 이용하면, 레벨당 entries를 구하는게 가능하다

B+ TREE

BTREE의 변형으로서 data pointer가 leaf node에만 저장이 된다.
-중간 노드에는 data pointer가 없고 분기값만 저장되어 있다
-모든 data들은 leaf node에 반드시 entry가 있으며, leaf node를 가야 data를 판단할 수 있다.
-leaf node의 단말 node들은 순차탐색을 위해 자기들끼리 연결되어 있다
-linked list를 따라가면 순차 탐색이 가능하도록 구성되어 있다.