[DB] Chapter 14. 인덱싱 & 14-1. 기본 개념

대부분의 쿼리(query)는 파일 내의 레코드 중에서 극히 일부분만 참조한다.

ex. 물리학과에 속한 모든 교수를 찾아라 ⇒ instructor 의 레코드들만 참조한다.
ex. ID가 2201인 학생이 취득한 총 학점을 계산해라 ⇒ student의 레코드들만 참조한다.

물리학과인지 알아내기 위해서 instructor 릴레이션의 모든 레코드들 살펴보는 건 비효율적이다.
마찬가지로 ID = 2201인지 알아내기 위해서 student 릴레이션의 모든 레코드를 살펴보는 것 역시 비효율적이다.

이상적인 방법은 시스템이 원하는 값을 가진 record를 직접 찾는 것이다. 이를 구현하기 위해서 파일과 관련된 부가적인 구조를 설계한다.

1. 기본 개념

ex) 교재의 인덱스

교재에 특정 내용을 알고싶다면...

1) 교재의 맨 뒤에있는 index 부분으로 이동
2) 원하는 단어를 찾고
3) 그 단어와 매핑되어 있는 페이지를 찾아서 그 페이지로 이동하면 된다 .

이러한 방식은 DB 시스템에서 파일을 위한 인덱스와 비슷한 방식이다.

DB 시스템의 인덱스는 도서관에서 사용하는 인덱스 방법과 동일한 역할을 한다.

ex) 주어진 ID를 가진 student 레코드를 검색

1) DB 시스템은 인덱스를 이용
2) 주어진 ID와 대응되는 record가 어느 디스크 블록에 있는지 찾고
3) student 레코드를 얻기 위해 해당 블록을 가져온다.

cf) 여기서 언급한 디스크는 SSD와 같은 영구 저장장치를 의미함

이렇듯... 인덱스(index)는 DB에서 효율적으로 query를 처리하기 위한 중요한 요소다.
인덱스가 없다면, 각각의 query에 대해 모든 relation의 전체 내용을 읽어야 하는데 이는 일부 record만 요구하는 query에 있어 굉장히 비효율적인 방식이다.

그렇다면 어떻게 인덱스를 구현해야 할까.

학생 relation의 인덱스를 구현한다고 하자.
가장 먼저 생각할 수 있는 건 학생 ID 목록을 정렬된 순서로 유지해서 학생 relation의 인덱스를 구현하는 방식이다. 하지만, 이 방식은 크기가 매우 큰 DB에 적합하지 않다.

왜냐하면,

1) 인덱스 자체가 매우 크고
2) 정렬된 순서로 인덱스를 유지하면 검색 시간은 줄어들겠지만 특정 ID값을 찾는데 여전히 많은 시간이 걸리고
3) 새로운 학생 record가 추가되거나 삭제될 때 정렬된 목록을 갱신하기 위한 비용이 많이 발생한다.

그래서 더 복잡한 인덱스 기술이 필요한데 14장에서는 이런 기술(technique)에 대해서 살펴볼 것이다.

기본적으로 인덱스는 3가지 종류가 있다.

• 순서 인덱스(Ordered indices) : 값에 대해 정렬된 순서로 되어 있음
• B+ 트리 인덱스
• 해시 인덱스(Hash indices) : bucket의 범위 안에서 값이 일정하게 분배되어 있다. bucket의 어디에 저장될 지는 hash function에 의해서 결정된다.

하나의 파일에 한 개 이상의 인덱스가 필요할 수 있다. 예를 들면, 저자, 주제, 제목과 같이 3개의 인덱스를 가지고 record를 검색할 수도 있다. 이와 같이 하나의 파일에서 record를 찾는데 사용되는 속성이나 속성들의 집합을 검색 키(search key)라고 한다.
(여기서의 key는 primary key, super key와는 다른 개념이다)