[DB] Indexing structures for files / 물리적 DB설계

Index structures for files

• index : 추가적인 보조접근구조, 검색속도 증가, 대체방법을 제공함, 효율적 검색

Single-level ordered indexes

• primary, secondary, clustering
• ISAM : Indexed Sequential Access Method

Multilevel indexes

• B trees, B+ trees

<Single level ordered>

Types of Single-level ordered indexes

• Primary index : 키 필드 정렬 파일에서 정렬 키 필드에 대해 정의된 인덱스
• Clustering index : 키가 아닌걸로 정렬된 파일에서 정렬 필드에 대해 정의된 인덱스
• Secondary index : any nonordering field

Primary Indexes

• < K(i), P(i) >
• K = 정렬 키 필드
• P = 디스크블럭의 포인터
• one index entry for each block
• Anchor record of the block, or the block anchor : 각 블럭의 첫 레코드
• Dense index : has an index entry for every search key value
• Sparse index : non-dense. (primary index)

if) 300,000 레코드, B=4096 bytes, R=100 bytes

→ bfr = B/R = 4096/100 = 40

→ 필요한 블럭 수 b = 300000/40 = 7500

→ 정렬 파일이므로 시간은 log 7500 = 13 block accesses

 

to insert a record

1. move records to make space
2. change some index entries

현실적으로 불가능한 방법들이므로, overflow 파일을 사용하거나 연결리스트 사용.

deletion ⇒ deletion markers

Clustering index

nonkey field

ordering nonkey field vs separate block cluster for each group →블럭당 같은 레코드만 저장. 공간낭비 가능성

→ 공간낭비 없지만 다음블럭까지 검색 필요

 

Secondary indexes : 보조인덱스

need more storage space and longer search time

dense index : 레코드 당 하나의 엔트리

임의 레코드의 검색시간 개선

on a nonkey field

can have the same value for the indexing field

1. index entry 여러개 사용
2. 가변길이 레코드 사용
3. 레벨을 하나 더

r=300,000 records fixed length, R=100bytes, B=4096bytes

secondary key, nonordering key field of the file that is V=9 bytes long

→ 보조인덱스 없다면 : 선형탐색, b/2 = 7500/2 = 3750 block accesses

→ 보조인덱스 있음

• R(i) = V+P = 9+6 = 15 = 인덱스 블럭의 크기
• bfr(i) = 4096/15 = 273
• b(i) = 300000/273 = 1099
• 이진탐색 시간 : log 1099 = 11
• 총 접근 블럭 수 = 11 index blocks + 1 data block = 12

1. Indexing filed가 key 일때

: 인덱스 필드가 정렬에 사용되면 Primary index, 정렬에 사용되지 않은 키라면 secondary index(key)

 

2. Indexing filed가 nonkey 일때

: 인덱스 필드가 정렬에 사용되면 Clustering index, 정렬에 사용되지 않은 키라면 secondary index(nonkey)

<Multilevel indexes>

bfr(i) = the blocking factor for the index

= the fan-out = fo (인덱스 차수)

• searching a multilevel index = log (밑=fo) (index block 수) 개의 블럭 접근 필요

ISAM = Indexed Sequential Access Method

 

bfr(i) = 273 = fan-out = fo

the number of first level index blocks b1 = 1099

block accesses = log(273) 1099

 

< Dynamic Multilevel indexes B Trees and B+ Trees >

B trees and B+ trees are special cases of the tree data structure

root node = level 0

search trees : 레코드 검색을 가이드해주는 특별한 형태의 트리

• p=3 → 포인터가 3개인 3차 트리

B-tree

: 트리가 항상 균형을 유지하고, 삭제로 낭비되는 공간이 있다면 절대 과도해지지 않도록 하는 추가적인 제약 조건이 있습니다.

차수 p인 B트리의 특성

1. 루트와 리프를 제외한 노드의 서브트리 수 : p/2이상 ≤ 개수 ≤ p → 적어도 노드의 반을 채워야함
2. 루트(리프가 아닌)의 서브트리 수 > 2 → 루트 노드부터 분기
3. 모든 리프는 같은 레벨 → 균형트리
4. 키 값의 수 : 리프는 (p/2이상 - 1) ~ (p-1)
   1. 리프가 아닌 노드 : 서브트리 - 1
5. 한 노드 내의 키값은 오름차순 정렬. → p-원 탐색트리

key 개수 = 포인터 개수 - 1

연산 : 직접탐색 = 키값에 의존한 분기, 한 노드 블럭 내에서는 순차탐색

순차탐색 = 중위 순회

삽입 = 트리 균형 유지, 분할 시 높이 증가

삭제 = 균형 유지, 합병 시 높이 감소

 

B+ tree : B트리의 변형

data pointers are stored only at the leaf nodes of the tree

leaf node들은 연결되어있다

• 인덱스 세트 : 내부 노드 (위쪽의 트리)
• 순차 세트 : 리프 노드 (모든 키 값들을 포함하며, 순차적으로 연결)

B+ 트리의 특성

1. 루트의 서브트리 : 0, 2, p/2 ~ p
2. 노드의 서브트리 (루트, 리프 제외) : p/2 ~ p
3. 모든 리프는 같은 레벨
4. 리프가 아닌 노드의 킷값 수 : 서브트리 - 1
5. 리프 노드 : 데이터 파일의 순차세트(리스트로 연결)

연산

탐색 : 인덱스 세트 = p-원 탐색트리, 리프에서 검색

삽입 : B트리와 유사, 오버플로우→분열→ 부모노드와 리프 둘 다에 키값 존재

삭제 : 리프에서만 삭제 or 합병 or 재분배

 

Index Creation (in sql)

 

CREATE [Unique] INDEX <index name>

ON <table name> (~~~)

[CLUSTER];

ex)

CREATE INDEX Dno_index

ON EMPLOYEE (Dno)

CLUSTER;