INDEXING STRUCTURES

Primary organization(ex. heap, hash, ...)이 이미 file에 존재한다는 가정하에 사용 ({value, pointer}로 구성되어 base file보다 size가 작다.)

• Static indexes: 구조가 유지 (insert, delete가 되어도 변화가 없음)
  • Single-level ordered indexes, Multilevel indexes
• Dynamic indexes: index와 data record 모두 update
  • Multi-level tree-based indexes: B+-tree

왜 indexes를 사용하는가 ?

• record retrieval의 속도 향상을 위해 사용
• sorting되어 있어서 binary search를 가능하게 한다.

Index structures는 secondary access paths를 제공하는 "disk의 추가적인 files"

• main path는 존재
• disk에 있는 primary data file에는 영향을 끼치지 않으면서 또 다른 접근 방법을 제공
• 효율적인 접근을 위해서는 indexing fields를 잘 결정하는 것이 중요

어떠한 field도 index를 생성하는데 사용될 수 있다.

• Different fields에 대한 multiple indexes 또한 생성 가능
• Multiple fields에 대한 (multi-level) index 생성 가능
  두 타입의 index를 같은 file에 생성 가능

data file에서 검색 조건을 기반으로 record를 탐색하면,
index file은 data file에 있는 하나 또는 이상의 disk blocks에 대한 pointer를 전달

대부분의 indexes는 ordered files 기반이고 tree data structure를 사용

TYPES OF SINGLE-LEVEL ORDERED INDEXES

Ordered Index

정렬 색인
Indexing field (attribute)

• index structure가 일반적으로 정의하는 file의 single field
• index key field의 value, data block pointer가 pair로 저장

index의 values는 "ordered", or "sorted"

• index에 대한 binary search 수행을 위해서이다.

index file은 data file보다 훨씬 작다

• data file에서 indexing할 key field와 block에 대한 pointer만을 저장하기 때문이다.

Several Types of Ordered Index

Primary index

• ordered file records의 ordering key를 key field로 지정하여 생성하는 index
• sorting의 key field를 사용하였기에 중복이 발생하지 않는다.

Clustering index

• non-key ordering field에 대해 생성하는 index
• key field가 아니기에 중복이 발생할 수 있다.
• 물리적인 data file은 clustered file

file은 최대 1개의 physical ordering field를 가질 수 있기에, 최대 1개의 primary index 또는 clustering index를 가질 수 있다. (두 개 동시는 불가)

Secondary index

• file의 어떤 non-ordering field에 생성하는 index
• 이미 index가 생성되어 있는데 부가적인 index를 생성(indexing이 되어 있지 않은 field에 대해 생성)
• data file은 여러 개의 secondary index를 가질 수 있다.

Primary Indexes

주요 색인, index records(entries)에 대한 Ordered file, 아래 2개의 field를 가짐

• Primary Key: $K(i)$
  • block의 첫번째 record의 primary key field의 값
• Pointer to a disk block: $P(i)$
  • $i$: 특정 index entry

Data file과 Index file

• data file의 primary key field: Name, data file의 sorting key field
• Block anchor: 각 block의 첫번째 값
• index file의 primary key value: indexing key field의 value

특정 record를 찾기 위해 index file에서 Binary search 수행 후, 해당 disk block의 pointer를 return
$\rarr$ data file보다 메모리 공간 감소

Characteristics of Indexes

Dense index

• data file의 모든 search key value에 대한 index entry를 가지는 index (1:1)

Sparse index

• 모든 search key value에 대한 index entry를 가지지 않는 index (=nondense)
• data file의 record 수 > index file record 수

Q: Which type of primary index is the one on the previous one?

• data file의 record 각각의 primary key value에 대한 1:1 index record가 아니기에 Sparse
  • $\frac {1}{한 block당 record 수}$ 만큼 공간 감소

Primary index의 index file은 data file보다 훨씬 작은 공간을 차지

• data file의 record 수보다 더 적은 index entries를 가짐
• ($Key, Block Address$)라는 두 개의 fields만 가지기 때문에 일반적으로 data record보다 더 작은 size
  • 따라서, index file에서의 binary search가 더 적은 block accesses를 수행

Calculating # of Block Accesses on a Data File without an Index

Ex1) $r$ = 300,000 records인 ordered file이 block size $B$ = 4KBytes인 disk에 저장

• File records가 length $R$ = 100bytes에, fixed size이고 unspanned
• KBytes를 1000 bytes로 치환한다면, records per block $bfr$은 얼마?
  • bfr = B/R = 4000 / 100 = 40
• file에 필요한 blocks의 수: $ceiling(r/bfr) ?$
  • r/bfr = 300000/40 = 7500
• data file에 대해 binary searches 수?
  • $log7500$

Calculating # of Block Accesses via a Primary Index File

primary index file의 $b$ blocks가 주어졌을때,

• index file을 통해 record를 위치시키기 위한 block accesses 수: $log_2b + 1$
• $log_2b \rarr$ binary search, $1 \rarr$ 실제 data block에 접근하는 것

Ex1') $r$ = 300,000 records인 ordered file이 block size $B$ = 4KBytes인 disk에 저장

• file의 ordereing key field ($V$): 9 bytes
• block pointer($P$): 6 bytes
• 각 index entry의 size ($R_i$): 9 + 6 = 15 bytes
• index의 $bfr$: block당 entries(records) ?
  • 4KBytes/15bytes = 259.xxx = 259
• index entries 수:
  • 7500
• index blocks 수:
  • 7500/259 = 28.xxx = 29
• index file에서의 binary search 수: 몇 번의 block accesses?
  • $log29$
• data record를 위치시키기 위해 index file을 통한 block accesses 수?
  • $log29$+1

Problems with a Primary Index?

Major problem: insertion and deletion of records

• record를 data file에서의 정확한 위치로 삽입하기 위해서는,
  • 새로운 record를 위한 공간을 만들기 위해 record들을 옮겨야 하고
  • index entries를 변경해야 한다.
  • records 이동은 몇 blocks의 block anchor를 변경시킬 수도 있다.

insertion에 대한 solution

• unordered overflow file을 사용
• data file의 각 block을 위한 overflow records의 linked list를 사용
  • 탐색 시간을 향상시키기 위해, overflow linked list 또한 sort

deletion에 대한 solution

• deletion markers 사용

Clustering Indexes

군집 색인
: 각 record에 대해 중복된 value를 가질 수 있도록 하는 non-key field에 대해 file records가 물리적으로 정렬되어 있는 경우

• Clustering field: non-key field
• Clulstered file: clustering field를 가지고 있는 data file

Clustering index

: 일종의 nondense index

• clustering field에 대해 동일한 값을 가지는 모든 records 탐색 시 속도 향상을 위한 목적으로 생성
  • primary index와 다른 점: primary index는 key field에 대한 index이지만, clustering index는 non-key field에 대한 index이다.
    • 둘 다 index file에서의 key field는 unique하지만, clustering index의 경우 실제 data file에서는 key field 중복 발생이 가능하다.
• ordered file은 아래 2개의 fields를 가진다.
  • clustered file의 clustering field와 동일한 type의 field
  • disk block pointer

index file에 저장되는 disk block pointer는
해당 key field의 값이 처음으로 나타나는 block의 address

• clustering field 1, 2는 disk block 1에서 처음으로 나타나므로 같은 block pointer를 가짐

Problems with a Clustering Index?

여전히 insertion, deletion에서는 문제

• 물리적으로 저장하는 방식이기 때문에 primary index와 같은 문제

해결방법

• clustering field의 각 (distinct) value에 대해 전체 block을 예약하는 방법
  • 한 value에 대해 block 1 전체 할당
  • overflow block 사용

Clustering Index with a Separate Block Cluster

clustering field value 3에 대해 새로운 record를 insert하려는 경우

• 해당 value의 block이 가득 찬 경우, overflow block을 사용하여 pointer로 연결
• 이후 새로운 '3' record들은 여기에 저장

Calculating # of Block Accesses via a Clustering Index File

Ex 1'') $r$ = 300,000 records인 ordered file이 block size $B$ = 4KBytes인 disk에 저장

• Zipcode 라는 clustering field로 정렬되어 있다고 가정
  • 1,000개의 distinct한 zipcodes가 file에 있다고 할때, 평균적으로 zipcode당 300 records가 있다고 가정
  • index entries 수 ($r_i$): 1000개
• $i$-th index record의 size: 5 bytes Zipcode + 6 bytes block pointer
  • $R_i$: 11 bytes
• ${bfr}_i$: 4000/11 = 363.xxx = 363
• index blocks 수: 1000/363 = 2.xxx = 3
• clustering index file에서의 binary searches 수: $log3$
• data record를 위치시키기 위해 clustering index file을 통한 block accesses 수?: $log3$+1

Secondary Indexes

보조 색인

• data file에 secondary 접근 방식을 제공
  • primary access는 이미 존재 (primary or clustering)
  • data records를 정렬하는 것은 의미가 없다.
• 각 record가 unique value를 갖는 key field & 중복된 값을 갖는 non-key field에 생성 가능

2개의 fields를 가지는 ordered file:

• Indexing field $K(i)$: data file의 non-ordering field와 동일한 type
• Record or block pointer $P(i)$: indexing field value를 가지고 있는 record or block에 대한 pointer
  • Record pointer $\rarr$ Dense
  • Block pointer $\rarr$ Sparse

하나의 data file에 여러 개의 secondary indexes가 존재할 수 있다.

• 각각은 특정 field에 대한 추가적인 접근 방법을 의미하는 것이므로 존재 가능

Secondary Index on Key Field

key field에 대한 secondary index가 가능하기 위해서는 1차 index에서 key field에 대한 index를 생성하면 안됨 (아닌가 unique attribute는 여러 개일 수도 있지 않나 ...)
$\rarr$ Clustering index 사용

• Key field: 각 record마다 unique한 값
  • = Secondary key
    • UNIQUE key field 해당
• data file의 각 record마다 하나의 index entry가 생성 $\rarr$ Dense

• nonordering key field에 대한 Dense secondary index (block pointers)
  • Data file의 secondary key field에 대한 1:1 index field value가 존재하기 때문에 dense
  • Block pointer라고 해서 무조건 sparse한 것은 아님

Calculating # of Block Accesses via a Secondary Index File

Ex 1'') $r$ = 300,000 records이고 각 record의 size $R$ = 100 bytes로 fixed length인 ordered file이 block size $B$ = 4KBytes인 disk에 저장

• file은 $b$ = 7,500 blocks를 가짐
• secondary key field: 9 bytes, block pointer: 6 bytes

secondary index가 아니였다면, linear search로 인해 평균적으로 7500/2 = 3750 번의 block accesses가 필요했을 것이다.

• 각 index entry size = 15 bytes
• $bfr$: 4000/15 = 266.xxx = 266
• dense index entries 수 = data file의 records 수 = 300,000
• 필요한 index blocks 수: 300000/266 = 1127.xxx = 1128
• 위 index에서 필요한 binary search의 block accesses 수: $log1128$
• 위 index를 사용한 record 탐색에 필요한 block accesses 수: $log1128$ + 1(실제 data file에 접근)

primary index보다 더 많은 block accesses가 드는 이유 ?

• primary index는 nondense 했기 때문에 더 짧다.

secondary index는 primary index와 비교하여 대개 더 많은 저장공간을 필요로 하고, 탐색 시간이 더 길다.

• index entry가 많아진 탓
• 하지만 임의의 record 탐색 시간은 향상

Summary of Index Types

• indexing field가 key인 경우, Secondary index의 index field는 data file의 candidate key 중 하나를 사용
• Clustering index의 경우, ordering field이 모든 distinct한 value 각각이 새로운 block의 시작에서 나타난다면 block anchoring이 가능
• Secondary (Key or Nonkey)의 경우, block anchoring이 존재하지 않는다.
  • Secondary index는 indexing에 사용하는 field가 data file에서는 정렬되지 않았기 때문에 anchor X

MULTILEVEL INDEXES

Multilevel Indexes

검색이 수행될 때 남아 있는 검색 공간을 줄이기 위해 설계

• index block의 blocking factor를 증가시킴(=fanout)으로써 search를 줄임
• multilevel index의 첫 level: index file 그 자체
• 두번째 level: 첫 level에 대한 primary index
• 세번째 level: 두번째 level에 대한 primary index

Two-level primary index

• ISAM(Indexed Sequential Access Method) with static structure
• 첫 level: data file에 대한 blocking factor: 2
• 두번째 level: 첫 level에 대한 blocking factor: 4
  • blocking factor가 증가!

DYNAMIC MULTILEVEL INDEXES

Why Dynamic?

ISAM: index insertions과 deletion은 여전히 문제

• 모든 index levels이 물리적으로 정렬된 file(즉, static)이어서 insert/delete 동안 구조가 변경되지 않기 때문이다.
• overflow pages로 인한 성능 저하

해결방법

• 각 index blocks에 일정 공간을 새로운 entries의 삽입을 위해 비워둠 (빈 공간에 entry가 삽입될 수 있도록)
• data file이 커지거나 줄어드는 것을 위한 적절한 알고리즘 사용

tree data structure에 기반한 dynamic multilevel index 개발

• single level: search cost 문제
• multi level: static한 문제

Review of Tree Data Structure

"unbalanced" tree의 경우 각 leaf node마다의 탐색 시간이 천차 만별

$B^+$-Tree Structures: Most Widely Used Index

• insert/delete가 $log_pN$ cost에 수행 ($p$: fanout(1 node에 몇 개의 record), $N$: leaf pages 수)
• tree의 height-balance를 유지
• root를 제외하고 최소 한 node가 반은 채워져야 함
• 각 node (disk block) m은 $d \leq m \leq 2d$를 만족
  • $d$: tree의 order (root를 제외한 order)
• equality와 range-searches를 효율적으로 지원

Internal nodes: search의 방향 지시

• 일부 search field 값은 검색을 안내하기 위해 반복될 수 있다.
• data records가 저장되지 않는다.
  • B-tree는 internal nodes에서도 실제 data records를 저장

Leaf nodes: data pointers를 저장

• search field의 모든 값에 대한 entry를 가짐
  • 서로 "linked" (B-tree는 그렇지 않다.)
• 검색 field가 key field인 경우는 record에 대한 data pointer를 저장
  • key field이므로 각 record마다 고유한 값을 가지기 때문에 해당 record로의 pointer 저장
• 검색 field가 nonkey field인 경우는 data file records에 대한 pointer를 포함하는 block pointer를 저장
  • 각 record마다 고유한 값이 아니므로 block로의 pointer 저장

Example of $B^+$-Tree with Order = 2

• Order = d = 2 $\rarr$ 각 node마다 최소 2개의 entry를 포함해야 한다.
• Search는 root로부터 시작
• $5^*, {15}^*$에 대한 탐색
  • ${15}^*$는 탐색을 수행하여 없다는 것 확인
• Worst: root 1번, leaf page 1번, 실제 data block 접근 1번 $\rarr$ order+1 = height+1

Inserting an Index Entry into a $B^+$-Tree

• 알맞은 leaf $L$를 탐색
• $L$에 index entry를 삽입
  • $L$에 충분한 공간이 있다면, 완료
  • 그렇지 않다면, $L$를 분리 ($L, L2$)
    • entry를 고르게 분배하고 middle key를 COPY UP
    • PUSH UP하지 않는 이유는 leaf node에서의 data pointer를 잃지 않기 위함
    • $L2$를 가리키는 index entry를 $L$의 부모에 삽입
• 위 과정이 재귀적으로 발생
  • index node를 분리하는 경우, entries를 고르게 분배하지만, middle key를 PUSH UP해야 한다.
• 분리 과정은 tree의 크기를 키울 수 있다; root의 분리는 곧 tree의 height를 증가

Insert $8^*$ into Example $B^+$-Tree

• $8^*$이 insert되면서 node의 수용 가능한 entry 수를 넘어버려서 split
• middle key인 $5^*$가 parent로 COPY UP

• $5^*$이 parent로 COPY UP되면서 parent node의 수용 가능한 entry 수를 넘어버려서 split
• 이때는 middle key인 ${17}^*$가 PUSH UP되면서 새로운 root가 생성되고 height가 증가

Example $B^+$-Tree After Inserting $8^*$

• height가 증가하면서 search cost 또한 증가
• 위 예제에서 entries 재구성으로 split을 피할 수 있다.
  • 재구성은 평균 점유율을 향상
  • 하지만 I/O을 증가시키므로 좋지 않다.

Comparison of Example of $B^+$-Tree

• height가 증가함으로써, search cost가 증가

• 평균 점유율은 향상하지만 I/O가 증가

Deleting an Index Entry from a $B^+$-Tree

• root부터 시작해서 삭제할 entry가 속해있는 leaf $L$을 탐색
• entry 삭제
  • half-full을 만족한다면, 종료
  • 그렇지 않고 $d-1$ entries를 가진다면,
    • $L$과 같은 부모를 가지는 sibling으로부터 entry를 빌려와서 재구성 $\rarr$ middle key의 변경 유발
    • 재구성이 실패하는 경우(sibling 또한 half-full을 만족하지 못하는 경우), $L$과 sibling을 merge
• merge 발생 시, $L$의 부모로부터 entry($L$이나 sibling을 가리키는)를 삭제해야 한다.
• merge는 root로 전파되어 height를 낮출 수도 있다.

Example $B^+$-Tree Before/After Deleting $19^*, 20^*$

• $19^*$를 삭제하는 것은 half-full을 만족하므로 문제가 없다.

• $20^*$를 삭제하는 것은 half-full을 위반하므로 sibling으로부터 entry를 빌려오고 middle key의 COPY UP이 필요

Deleting $24^*$

• $24^*$를 삭제하면, half-full 위반이 발생
• 따라서, sibling과의 merge를 수행
• 이때, merge를 수행하는 leaf를 가리키는 entry를 삭제해야 하므로, middle key인 $27^*$를 삭제
• parent가 half-full을 위반
• splitting key인 $17$이 자식으로 PULL DOWN되어 새로운 root가 생성

root level: 3 -> 2

$B^+$-Trees in Practice

Typical order: 100 (Typical fill-factor(node가 평균적으로 채워지는 정도): 67%)

• Average fanout = 133 (search cost 감소량)

Typical capacities:

• Height 4: ${133}^4$ = 312,900,700 records
• Height 3: ${133}^3$ = 2,352,637 records

buffer pool에서의 최상위 레벨 유지:

• Level 1 = 1 page (= root) = 8 Kbytes
• Level 2 = 133 pages = 1 Mbytes
• Level 3 = 17,689 pages = 133 Mbytes