8장 storage and indexing Overview

레코드들이 어떻게 파일로 구성되느냐에 따라 DBMS의 성능이 달라진다.
인덱스는 search key로 record id를 찾을 수 있게 해주는 자료구조이다.
버퍼메니져가 disk로 부터 페이지를 메모리로 fetch한다. file, index layer가 버퍼메니저에게 요청.


파일구성 방법
힙 파일:  순서가 렌덤하게 레코드들이 파일에 저장. 모든 레코드들을 스캔할때 적절한 방법.
sorted files: 레코드들을 순서대로 접근할 때 좋은 방법.
인덱스 : 레코드들을 트리나 해쉬로 구성. search key 필드로 검색할 때 효율적인 검색이 가능하다. sorted files보다 레코드 삽입, 수정, 삭제가 빠르다.

인덱스
search key에 의해 파일 접근을 빠르게 할 수 있다.
search key는 relation의 field들의 subset이다.
search key는 key(primary key, candidate key)와는 관련이 없다. 즉 unique하지 않을 수 있다.

data entry
data entry : 인덱스 파일에 저장되어 있고. 이걸로 데이터 레코드를 찾을 수 있다.
data entry를 저장하는 세가지 방법.
1. key value와 data record로 구성.
2. key value와 data record id로 구성.
3. key value와 data record id의 list로 구성.
1번 방법으로는 index를 하나밖에 이용 못한다. 아니면 레코드데이터가 중복되어야 한다. 레코드데이터가 크면 페이지 많이 차지한다.
2번과 3번은 data entry가 데이터레코드의 포인터를 가지고 있기 때문에 파일 구성에 독립적이고, 1번보다 사이즈가 작다. 특히 3번은 2번보다 더 사이즈가 작지만 data entry들의 길이가 가변적이다.(search key가 고정 사이즈이더라도!)

인덱스 분류
primary index : primary key를 포함하는 search key.
secondary index : 그 외 인덱스들
unique index: candidate key를 포함하는 search key.

clustered : 데이터 레코드의 순서가 그 파일의 인덱스의 데이터 엔트리 순서와 비슷하거나 같도록 구성할 때.
1번은 clustered.
2번을 사용했을 때 clustered로 만들어주려면 heap 파일 정렬. 레코드가 삽입될 때 overflow 페이지가 필요할수도 있다. 그래서 data 레코드들이 완전히 sort되어 있다고 말할 수 없고 sort에 가깝다라고 말할 수 있다.

Hash-based index
index는 bucket들의 모임
bucket: primary page하나랑 0개 이상의 overflow pages.
hash function으로 레코드가 속할 버켓을 구한다.
레코드의 search key값을 이용한다.

B+ tree
루트에서 단말 노드에 이르는 모든 경로의 길이가 같은 인덱스 구조.
leaf page는 data entry를 포함하고, 양옆의 leaf들과 연결되어 있다.
non leaf page는 index entry들을 포함하고 찾는 data entry가 어디있는지 알려준다.
fan-out : 비단말노드에서 자식의 평균 수.
fan-out이 클 수록 빨리 찾을 수 있다. index entry 사이즈가 작을 수록 fan-out이 커진다.