데이터베이스에서 인덱스라 함은 search key를 가지고 원하는 data를 빠르게 찾을 수 있도록하는 도구이다.
index는 data entry를 포함하고 있으며 주어진 key 값을 이용해 data entry를 빨리 찾을 수 있게해준다.
참고로, data entry는 search key로 data record를 찾을 수 있도록 하는 정보를 포함한다.
data entry를 구성하는 방법은 아래의 3가지로 나뉜다.
1. value를 이용해서 구성
2. <value, reference> 형태로 구성
3. <value, list of reference> 형태로 구성
1번과 2,3번을 구분해서 이해할 필요가 있는데, 1번은 인덱스 파일내에 레코드 contents가 저장되어 있는 구조로 포인터 같은게 필요 없는 반면, 2,3,번은 필요하다.
data record의 순서와 data entry의 순서가 거의 같거나 비슷하면 clustered index라 한다. 위의 case에서 1번의 경우는 clustered index라고 생각할 수 있다. index는 내부적으로 hash를 이용할 수도 있고 B+ tree로 구현될 수도 있는데 B+가 일반적인 듯하다. 아래 링크로 어떻게 동작하는지 확인해보는 것도 괜찮을듯 하다.
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
B+ Tree Visualization
www.cs.usfca.edu
leaf page는 data entry를 가지고 있고 서로 chaning된 형태이며 leaf page가 아니면 index entry로 구성된다.
index는 search가 빨라진다는 장점이 있는 반면 memory를 더 사용하며, update의 추가비용이 더 발생한다는 trade-off가 있다. 내가 자주 사용하는 query가 뭔지 정말 index가 필요한지, 필요하다면 어느 key로 할지를 깊이 생각해보고 사용해야 한다.
참고
https://www.youtube.com/watch?v=4aCkt3yeiiU