index가 중요한 이유
- full scan: O(N)
- index: O(logN)
=> 더 빠르게 조회를 하기 위해 index를 사용한다.
index 동작 방식
- binary search를 통해서 빠른 검색이 가능
- 만약 index가 포함되지 않은 값을 조회하면 full scan이 일어남
- a,b를 동시에 index를 걸면 b만 조회할 경우 full scan보다 더 안 좋은 성능을 보여줄 수 있다.
- a기준으로 idx가 정렬을 했기 때문에 b는 뒤죽박죽이 되어있음.
- hash table을 사용한 방법도 있음
- 장점: O(1)
- 단점: rehashing에 대한 부담 equality비교만 가능, rangex
index 참고사항
- full scan이 더 좋은 경우
- table에 적은 량의 데이터가 있는 경우
- table의 대부분이 같은 값을 갖고 있을 경우
- insert가 많은 경우 index 추가 때문에 성능 저하가 생길 수 있다.