Indexing

Indexing

인덱스는 데이터에 대한 접근의 속도를 향상시키는데 사용된다.

Search Key : record를 찾기 위해 사용되는 속성 집합(primary key 개념과 다른개념)

Index file은 다음 형태의 인덱스 엔트리로 구성된다.

• Search-key | pointer or value

❗종류

• Ordered indices : B-tree와 같이 정렬된 순서로 키가 저장된다.

• Hash indices : 해쉬함수를 사용하여 동일하게 분포된 키를 탐색한다.

  ⚡ lb(lower bound) < key < ub(upper bound) ⇒ Range query : ordered

  ⚡ key = v ⇒ Point query : Hash

Index Evaluation Metrics

• 접근 유형
  • Range query
  • Point query
• Access time(search time)
• Insertion time
• Deletion time
• Space overhead

Ordered Indices 정렬된, 순서있는 인덱스

key는 2가지 방식으로 저장된다.

• Primary index (clustered index) 주 인덱스
  • 인덱스의 행의 순서가 파일의 행의 순서와 같다.
• Secondary index (non-clustered index) 보조 인덱스
  • 인덱스의 행의 순서가 파일의 행의 순서와 다르다.
    • 실제 데이터 값을 포인팅 하고 있는 주소를 index가 포인팅 하는 형식