[ADV_db]Chap 3. Indexing

---

# Basic Concept

---

• Index File(Index entries)

이런 Index File은 더 빠른 검색을 위해 사용된다. 따라서 검색 키와 포인터로 이루어져 있고, 원본 파일보다는 용량이 작다. 또한, 여러 검색 키마다 여러 인덱스를 저장할 수 있다.

• Search Key
  • 여기서 말하는 Search Key는 그동안 배웠던 primary key,Candidate key,super key와는 다른 개념이다.
  • 하나 이상의 속성으로 구성될 수 있다.
  • 인덱스 파일에는 여러 종류의 검색 키에 대한 인덱스가 존재할 수 있다.
    • 예를 들어, 책을 고를 때 작가,출판사,주제,제목 등으로 인덱스를 둘  수 있는 거처럼 말이다.
• Index의 기본적인 종류
  • Ordered Indices
    • Search Key에 따라 정렬된 인덱스
    • 정렬하는데 여러 방법이 있지만, 어느 것도 완벽하지는 않다. 따라서 다음의 평가 기준을 가지고 결정하여 사용한다.
      • Access Type
        • 특정 값을 가지는 속성인 경우
        • 구별된 범위 안에 속하는 속성인 경우
      • Access Time
      • Insertion time
      • Deletion time
      • Space overhead
  • Hash Indices
    • Hash function을 통해 Bucket에 균등하게 분배되어 있는 Search Key

---

# Ordered Indicies

---

• Clustering Index(Primary Index)
  • Search key에 따라 순차적으로 정렬된 인덱스
  • 물리적으로 저장되는 순서가 나타난 인덱스
  • 이 방법으로 정렬할 때는 주로 Search key가 Primary key속성을 사용하는데, 필수는 아니다.
• Non-Clustering Index(Secondary Index)
  
  • 순차적으로 정렬이 아닌 다른 방식의 정렬인 경우
  • 물리적으로 저장되는 순서가 아닌 논리적으로 원하는 속성으로 정렬한 인덱스
• Index-Sequential file
  
  • 인덱스만 Clustering Index일 뿐만 아니라 실제 Record들도 그 순서에 따라 정렬되어 있는 구조

---

# Index File

---

• Dense Index File
  • 레코드마다 접근 가능한 모든 Search-key들을 index로 가지고 있는 경우
  • Sparse Index보다 용량이나 생성,삭제 등 수정하는 시간은 더 오래 걸리지만, 검색 속도는 빠르다.
  • Insertion의 경우, Search-key를 통해 삽입할 위치를 찾고 Index와 Record를 모두 수정한다.
    • 만약 새로운 공간을 추가적으로 만들어야 한다면, Overflow Block가 필요하다.
    • Overflow Block이란 ? 레코드를 삽입할 자리가 없으면 데이터를 재구성하는 번거로운 과정을 거치기 보다는 따로 블록을 만들어 두고 저장하는 방식이다.
  • Deletion의 경우, 해당 Search-key에 대응하는 Record가 하나라면 Index와 Record를 모두 삭제하고, 같은 Search-key를 가진 다른 Record가 남아있으면, Index의 포인터 주소만 수정하고, Record를 삭제한다
  • Dense하기 위해서는 같은 Search-key를 가지는 Record들은 연속적으로 있어야한다. 

• Sparse Index
  • Sparse Index는 Index가 Clustering index일때만 쓸 수 있다.
  • Insertion의 경우, Search-key를 가지고 들어갈 위치를 찾고, 새로운 블록이 만들어지면 Index와 Record를 모두 수정하지만, 그렇지 않은 경우는 Index만 수정한다.
  • Deletion의 경우,
    • 같은 Search key를 가진 다른 레코드가 존재한다면 포인터만 다른 레코드로 옮기고 인덱스는 그대로 둔다.
    • 만약 해당 검색 키의 유일한 레코드 였다면 그 다음 레코드로 인덱스 파일을 대체하고 레코드는 삭제한다.
    • 마지막으로 만약 다음 레코드가 이미 인덱스파일에 있다면, 그냥 삭제한다. 
   

• 대부분 Sparse Index를 사용한다. 어차피 메모리에는 Block단위로 옮겨지기 때문에 전체 데이터를 Block size로 잘라서 각 Block마다 Search-key를 지정해서 Sparse Index를 만든다.
  • 이 방식으로 하면 Space overhead는 유지한 상태로 Disk Access Time을 줄일 수 있다.
   

• Multilevel Index
  • Index조차 커져서 메모리에 올릴 수 없게 되면 Index를 Indexing한 Multilevel Index를 메모리에 올려 사용한다.
   

• Non-clustering index(Secondary Index)
  • Search-key에 해당하는 Record가 여러 개인 경우, 가운데 Bucket이라는 포인터 집합을 통해 같은 서치 키 값을 가진 레코드들을 모으고, 서치 키 값들만 Indexing한다.
  • 이 때, Secondary Index는 Dense해야한다.
   

• Composite search key
  
  • 두 개 이상의 속성을 Search-key로 사용하는 경우