DB - indexing

· index file - <search_key, pointer>형태의 레코드로 구성됨

 

· 2가지 기본적인 indices

  - Ordered indices: search key가 정렬되어 저장됨

  - Hash indices: search key는 "hash function"을 통해 "buckets"간에 균일하게 분배됨

 

· Index Evaluation Metrics

  - Dense index에서 record를 찾는데 걸리는 cost는 O(N/B)

    N개의 elements가 각 search key에 따라 B개 elesent를 가지는(block size)의 block으로 나눠져서 저장된다.

    즉, IO는 N/B번의 연산 안에 해당 값을 가지는 block을 찾을 수 있다.

  - Sparse index에서 recored를 찾는데 걸리는 cost는 O(N/B^2)

    dense index에서는 N/B의 index가 존재하는데 spase index는 그 중의 일부(block의 개수로 쪼갠만큼)만 가진게된다.

    즉, N/B^2개의 index 가짐

 

  * 일단 해당 block 찾으면 io연산은 일어나지 않으므로 block 찾는 것만 생각하면 됨

  * Q: Dense index의 primary index의 수는 table의 row 수와 항상 같다 (X)

 

  - Sparse index file은 삽입 삭제의 overhead가 적고, 공간을 적게 사용하지만 dense index보다는 느리다

 

 ·  Primary index와 Secondary index

  - Primary index는 정렬된 파일이다 (sequentially ordered file)

    clustering index라고도 부름   (clustering: 뭉쳐져 있다 - 데이터가 근접한 곳에 저장된다)

  - Secondary index

    index의 레코드는 bucket을 가리키고, 그 bucket은 실제 레코드가 있는 곳을 가리킨다. 

    각, 실제 데이터를 가지고 있는 file구조와 bucket의 순서는 상관이 없다

     -> bucket 순서대로 데이터가 정렬되어 있지 않음

    반드시 dense index이여야한다.

 

 * primary index를 사용한 sequential scan은 빠르고(efficient),

   secondary index를 사용한 sequential scan은 느리다(expensive).

 

·  Multilevel index

  - Single-level Sparse index file에서 Sparse index를 inner index라고 하고

    이 inner index를 하나의 block으로 보고 sparse index를 하나 더 만드는데 이를 outer index라고 한다.

 

· Index Update

  - Deletion

    : 어떤 레코드를 지웠을 때, 그 레코드가 있는 블락이 비어지게되면 그 블락을 가리키는 search key는 index에서 지워        지게 된다.

    ㄴ Dense indices: search key 삭제는 파일 레코드 삭제와 유사

    ㄴ Sparse indices: index에서 현재 지운 레코드를 가리키는 search key는 다음 레코드의 search key로 대체된다.

                            만약, 덮어씌우려는 search key가 이미 index에 존재한다면 그냥 삭제만 한다.

  - Insertion

    ㄴ Dense indices: 현재 추가한 레코드의 search key가 index에 없으면 삽입한다.

    ㄴ Sparse indices: 어떠한 레코드가 이미 존재하는 블락에 삽입되면 index는 변화 없다.

                            하지만, 새로운 블락이 만들어지게 되면, 그 블락의 처음 search-key가 index로 추가된다.

 

· Seconday Indices

  어떠한 조건을 만족하는 특정 분야의 값들을 가지는 모든 레코드를 찾으려고 할 때

  ex) 특정 학과에 소속된 모든 강사를 찾아라