[Database] - Indexing

📕Agenda

1. indexing은 record retrieval의 속도를 향상해줌.
2. index Structures는 secondary access paths를 제공
3. 어떠한 필드도 index를 생성하는 데 사용될 수 있다.
   1. Multiple indexes를 생성할 수 있다.
4. 대부분의 indexes는 oredred files 기반이고 트리 형태로 저장됨.
   1. B-tree
   2. B+-tree

 

📕Index is an address book of the disk

 

📕Single-Level Ordered Indexes

• Order index는 textbook에 index 하는 것과 유사하다.
• Indexing filed(attribute)
  • 인덱스는 인덱스 필드의 각 값을 해당 필드 값의 레코드를 포함하는
    모든 디스크 블록에 대한 포인터 목록과 함께 저장합니다.
• index의 값들은 정렬되어 있다.
• index file들은 physical disk에 저장된다.

 

📕Dense & Sparse index

• index는 dense or sparse이다.
  • Dense index
    • data file의 모든 search key value에 대한 index entry를 가지고 있다. 
      index -> Data 1:1 매핑
  • Sparse index
    • 모든 search key value에 대한 index entry를 가지지 않는 index 
      not 1:1 
    • data file의 record 수 > index file record 수
• dense or sparse의 여부는 데이터의 특성에 따라 달라진다.

왼쪽 dense index 오른쪽 sparse index

 

📕types of single-level Ordered indexes

 

📗Primary Index

• ordered file records의 ordering key를 key field로 지정하여 생성하는 index
• sorting의 key field를 사용하였기에, 중복 X
• two field
  • Primary key = K(i) , Pointer (address) to a disk block = P(i)
• 데이터 파일의 각 블록에 대해 인덱스 파일의 인덱스 항목 하나

 

💡Data file , index File

• data file의 primary key field : Name
• index file의 primary key value : indexing 된 data파일의 key value가 들어간다.
• Block anchor : 각 block의 첫 번째 값
  • block 1의 anchor는 Aaron Ed, block 2의 anchor는 Adams, John 
• index file의 수는 recods file의 수보다 적다.
• index file is sparse 

💡장점

• data파일보다 적은 records를 가진다.
  • block마다 하나의 index를 가지기 때문이다.
• index file의 entry 크기는 data record보다 작다.
  • primary index file은 K(i), P(i)만 저장
• 정렬어있어서 binary search를 수행할 수 있다.

💡문제점

• data 파일은 정렬되어야 한다.
• records의 삽입과 삭제의 비용이 비싸다.
  • 정렬되어 있기에, 삽입과 삭제의 과정 이후 index values를 바꿔야 하기 때문

💡해결책

• 순서가 지정되지 않은 overflow 파일 사용
• overlfow record의 linked list 사용

 

💡no indexing 

• 가정
  • data file의 records 수(r) = 300,000
  •  Block size(B) = 4096 bytes, 
  • Record size (R) = 100 bytes
• bfr = B/R = 4000 / 100 = 40 -> 각 블록에는 40 records가 있다.
• b= r/bfr = 300000/40 = 7500 ->
  300000개의 records(file)를 저장하기 위해서는 7500개의 block이 필요하다.
• data file에 대해 binary searches 수
  • log 7500 = 12.8 = 13 
• index file을 통해 record를 위치시키기 위한 block address 수
  • log2 b + 1
  • log2 b -> binary search, 1 -> 실제 data block에 접근하는 것

💡Primary indexing

• 가정
  • ata file의 records 수(r) = 300,000
  •  Block size(B) = 4096 bytes, 
  • Primary index file
    • size of key value(V) = 9 bytes
    • size of pointer(P) = 6 bytes
    • index entry의 size(Ri) = V+P = 15 bytes
• primary index file에서 indexing 된 block 수 : ri
  • 데이터 파일을 저장하는 데 필요한 블록(또는 인덱스) 수 =bfr
  • which is ri = 7500
• index의 bfr= bfri : block당 index entry 수
  • 4096 / 15 = [273.067] = 273
• index block 수 :
  • 7500/273 = 27.45545425-> 28개
• index file에서의 binary search 수 : 몇 번의 block accesses
  • log2 (index block 수) => log 2 (28) 
• data record를 위치시키기 위해서는 search 수 + 1(access the data file , load into memory)
  • 6

 

 

📗Clustering indexes

• 각 record에 대해 중복된 value를 가질 수 있도록 하는 non-key filed에 대해 file records가
  물리적으로 정렬되어 있는 경우
• Clustering field : non-key field
• Clustered file : clustering field를 가지고 있는 data file

💡Clustring index

• nondense index
• clustering field에 대해 동일한 값을 가지는 모든 record 탐색 시 속도 향상을 위한 목적으로 생성
  • primary index와 다른 점
    • primary index는 key field에 대한 index
    • clustering index는 non-key-filed에 대한 index이다.
      • 둘 다 index file에서의 key field는 unique 하지만,
        clustering index의 경우 data file에서는 key field 중복 발생이 가능하다.
      • 중복이 발생할 수 있음. -> not unique
• ordered file은 2가지의 filed를 가진다.
  • clustering field
  • disk block pointer
    • 해당 key field의 값이 처음으로 나타내는 block의 address

• clustering filed 1,2는 disk block 1에서 처음으로 나타나므로 같은 block을 가리킨다.
• 해당 filed value를 찾기 위해서 화살표가 가리키는 block부터 탐색해야 함.
• index 수 < records의 수
• nondense index

💡문제점

• data file은 clustering field별로 정렬되어야 합니다.
  • physical ordering이 필요하기에 비용이 비싸다.
• 삽입과 삭제는 여전히 비용이 비싸다.

💡해결 방법

• clustering field의 각 value에 대해 전체 block을 예약하는 방법
  • 한 value에 대해 block 1개를 전체 할당
  • overflow block 사용
  • 만약 block 내에 전부 다 들어가지 못하면 block을 추가로 할당하고 pointer로 연결

💡Calculating using clustering indexes

• 가정
  • r = 300,000 , B = 4096byte 
  • data는 actor name으로 정렬되어 있다.
  • 1000개의 unique 한 actor name이 있다고 가정.
  • acter name 당 300 records가 있다고 가정
• ri = 1000 ( 1 cluster per actor)
• V=5, P = 6 bytes so Ri = V+P = 11 byte
• bfri =B/ri = [4096/11] = 372.067 = 372
• bi = ri/bfri = 1000/372  = 2.688xx -> 3 -> cluster index file을 저장하기 위해서는 3개의 block이 필요하다.
• search cost
  • binary search 수 :
    • log2 (bi) = log 2(3) 
  • data record를 위치시키기 위해서는 log 3 + 1 

 

 

📗Secondary indexes

• data file에 secondary 접근 방식을 제공
  • primary access는 이미 존재한다.
• 각 record가 unique value를 갖는 key field & non-key field에 생성 가능
• 2개의 field를 가지는 ordered file
  • indexing field [K(i)] : data file의 non-ordering field와 동일한 type
  • record pointer or block pointer [P(i)] : indexing field value를 가지고 있는 pointer
    • Record pointer -> Dense
    • Block pointer  -> Sparse
• Data file은 여러 개의 secondary index를 가질 수 있다.
  
  • 각각은 특정 field에 대한 추가적인 접근 방법을 의미하기에 존재 가능

• index와 data record는 1대 1 매핑
  • 모든 record는 indexing 되어 있다.
  •  index의 수와 records의 수는 같다.
  • block pointer는 저번 개념부터 그 value가 등장하는 block을 가리킴.
• dense index file이라고 부를 수 있다.
• Data file은 정렬, 비정렬 상태. (둘 다 가능)
• 하지만 secondary index file은 반드시 정렬되어 있어야 함.
• 동일한 데이터 파일에 대해 Multiple secondary index를 생성할 수 있습니다.
• index files를 정렬하는 것이 왜 중요할까?
  • 탐색해야 하기에 정렬되어 있어야 함.

 

💡장점

• data file은 정렬될 필요성이 없다.
  • no physical sorting necessary
• 동일한 데이터 파일에 대해 많은 secondary index를 생성할 수 있다.
  • physical disk에 각각의 secondary index file을 저장한다.
  • 각각의 secondary index 파일은 의미 있는 파일
• primary indexing 보다 빠르다.

Calculating using secondary indexes

• without indexing
  • number of record in data file [r] = 300,000 and record size [R] = 100 bytes 
  • Block size B = 4096 bytes, and b= 7500 
  • data file is not ordered,
  • search cost
    • 정렬되어 있지 않기에 binary search 불가능, linear search 가능!
    • b/2 = 7500/2 = 3750번의 block accesses in average
• using secondary indexing
  • V=9, P=6  Ri = 15 bytes
  • bfri = B/Ri = 4096 / 15 =  273.xxx = 273
  • 필요한 index block 수 : ri/bfri = 300,000 / 273 = 1098.xx -> 1099 
    • cluster index파일을 저장하는데 1099개의 block이 필요하다
  • search cost
    • log2 (bi) => log2 1099 = 11
  • total cost = search cost + 1 -> 12

💡결과 비교

• primary indexing은 28개의 block
• clustering indexing은 3개의 block
• secondary indexing은 1099개의 block
• primary index보다 더 많은 block access가 많은 이유
  • primary index는 nondense 했기 때문에 짧다.
• secondary index는 primary index와 비교하여 더 많은 저장공간을 필요로 하고, 탐색 시간이 더 길다.
  • index entry가 많은 것이 이유
  • 하지만 정렬되어 있지 않은 data file에 대해서는 search time이 훨씬 짧다.

 

📕Secondary indexing for nonkey value field

• record pointer를 저장하고 있는 추가적인 block을 사용할 수 있다.

 

 

📕index type의 속성

• indexing field가 key인 경우, Primary index, nonkey인 경우, Clustering index
• Primary index
  • Number of Index Entries : data file에 있는 Block 수
  • Nondense
  • block Anchoring : Yes
• Clustering index
  • Number of index Entries : 중복되지 않는 index field value의 값의 수.
  • Nondense
  • block Anchoring : Yes or No
    • Yes : ordering field이 모든 distinct 한 value 각각이 새로운 block의 시작에서 나타난다면 가능
    • NO : 그 외의 경우
• Secondary index
  • key or nonkey 둘 다 block anchoring이 존재하지 않는다.
    • secondary  index는 indexing에 사하는 field가 data file 내에서는 정렬되지 않았기 때문에 
      anchor 불가능

📕Multilevel Indexes

• 검색이 수행될 때 남아 있는 검색 공간을 줄이기 위해 설계
• 정렬된 index file에서의 search cost는 log2 (bi)이다.
  • search cost를 줄일 수 있을까? -> 근본적으로 log의 base를 증가시켜야 함.
  • 우리가 2보다 큰 base를 사용할 수 있을까?
  • Multilevel indexing을 사용 -> search cost  : log bfri (bi)

 

📗two-level primary indexing

• Second level로 탐색하려는 숫자의 선택지를 좁혀주는 역할
  • 만약 내가 71을 탐색하고 싶다면 71보다는 작고, 71보다는 큰 block을 찾아가야 할 것이다
  • 그러면 우리는 Second level에서 55에 해당하는 pointer를 타고 들아 가서
    First level에서 71을 찾을 수 있을 것이다.
  • 만약 level 2가 없다면 우리는 13개의 블록을 다 탐색해야 하지만, level 2로 인해 block accesses를 줄일 수 있다.
• top level = 여기서는 two level이기에 Second level
  • single block이어야 한다.
• First level : data file에 대한 blocking factor : 2
• Second level : First level에 대한 blocking factor : 4
  • 결과적으로 단계가 높아질수록 blocking factor가 증가 -> search time이 감소

📗Calculating using multi-level indexes

• 가정
  • r = 300,000 and R = 100, block size B = 4096 , b = 7500
  • R1 = V+P = 9+6 = 15
  • bfri = 4096 /15 = 273
  • bi = 300,000/ 273 = 1098.xxx -> 1099
• First level은 data file을 저장하기 위해서 1099개의 block이 필요하다.
• second level에 필요한 block 수 ( indexing level 1(b1))
  • b2 = [b1/bfri] = 1099/273 =4.xxx -> 5 block 
• 우리는 b t = 1 block까지 이 과정을 반복한다.
• third level 에 필요한 block 수 (indexing level 2(b2))
  • b3 = [b2/bfir] = 5/273 = 1 block -> finish
• 3 level index file은 single block을 가진다.
• The search cost is t=3
• total cost : 3 + 1 = 4 blocks
  • find and load a requested data in to memory

 

💡문제점

• 여전히 삽입과 삭제에서 문제가 발생
• 모든 index file이 physical disk에 저장
  • index levels이 insert/delete 동안 구조가 변경되지 않기 때문이다.
• 정렬을 유지해야 함.

💡해결책

• 매우 편리한 해결책은 dynamic multilevel라고 불리는 multilevel index를 사용하는 것이다.
  • B-tree
  • B+- tree