db index
index
인덱스란 추가적인 쓰기 작업과 저장 공간을 활용 db 테이블의 검색 속도를 향상시키기 위한 자료구조 이다. 원하는 내용을 찾고자할때 테이블의 모든 데이터를 검색하면 시간이 오래 걸리기 때문에 데이터, 데이터 위치를 포함한 자료구조를 생성하여 빠르게 조회할 수 있도록 돕고 있다.
인덱스를 활용하면 데이터를 조회하는 select update delete의 성능이 함께 향상된다. 그 이유는 update delete 를 하려면 일단 찾아야 하기 때문이다.
index의 관리
index를 항상 최신의 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색이 가능하다. 그렇기 때문에 인덱스가 적용된 컬럼에 insert update delete 가 수행된다면 다음과같은 연상을 추가적으로 해주어야 하며 그에 따른 오버헤드가 발생한다.
- insert : 새로운 데이터에 대한 인덱스 추가
- delete : 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업 진행
- update : 기존의 인덱스를 사용하지 않음 처리, 갱신된 데이터에 대해 인덱스 추가
인덱스 장/단점
장점: 테이블을 조회하는 속도와 그에 따른 성능 향상, 시스템 부하감소
단점: 인덱스 관리위해 db의 약 10% 저장공간 필요, 관리를위한 추가작업, 잘못사용하면 성능저하
위에 언급했듯 추가작업이 필요하므로 create delfet update가 자주 일어나는 곳에 index가 있다면 인덱스의 크기가 커져서 성능이 오히려 저하된다. 왜냐면 인덱스를 삭제하지 않고 사용하지 않음 처리만 하기때문에 빈번하게 일어난다면 index가 지속적으로 쌓일것이고 실제 데이터보다 훨씬더 많은 인덱스가 존재하게 될것이다.
index가 언제 쓰이면 좋을까?
- 규모가 작지 않은 테이블
- insert update delete 같은 데이터들이 지속적인 변화가 자주 발생하지 않는 컬럼
- join이나 where 또는 order by에 자주 사용되는 컬럼
- 데이터의 중복도가 낮은컬럼
사용 하는것만큼이나 생성되 인덱스를 관리해주는 것도 중요 쓰지 않는다면 바로 제거를 해줘야 한다.
index의 자료구조
가장 대표적인 자료구조인 해시테이블과 B+Tree 를 사용한다.
해시테이블
해시테이블
(key,value)로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할때 유용하다. 해시 테이블은 key값을 이용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조이다.
해시 테이블 기반의 DB 인덱스는 (데이터=컬럼의 값, 데이터의 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현하였다. 해시 테이블의 시간복잡도는 O(1)이며 매우 빠른 검색을 지원한다.
하지만 db index에서 제한적으로 사용된다. 해시가 등호(=) 연산에 특화 되어있기 때문에 해시 함수는 값이 1이라도 달라지면 완전히 다른 해시값을 생성하는데, 이러한 특성때문에 부등호 연산이 자주 사용되는 db검색을 위해서는 적합하지 않다.
즉, 특정한 단어(귤, 머리 등)로 시작하는것이 있다면 그단어로 시작하는 모든 데이터를 검색은 하지못할 것이다. 이러한 이유로 B+tree가 일반적으로 사용된다.
B+Tree
기존의 B-Tree는 어느 한 데이터의 검색은 효율적이지만, 모든 데이터를 한 번 순회하는 데에는 트리의 모든 노드를 방문해야하므로 비효율적이다. 이러한 단점을 개선시킨게 B+Tree이다.
B+Tree는 모든 노드에 데이터를 저장했던 BTree와는 다른 특성을 가지고 있다.
- 리프노드(데이터노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스노드)들은 데이터를 위한 인덱스(Key)만을 갖는다.
- 리프노드들은 LinkedList로 연결되어 있다.
- 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.
db의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주발생될 수 있다. 이러한 이유로 BTree의 리프토드들을 LinkedList로 연결하여 순차검색을 용이하게 하는 등 B-Tree를 인덱스에 맞게 최적화 하였다. 이러한 이유로 B+Tree는 O(log2n)(밑2)의 시간 복잡도를 갖지만 해시테이블보다 인덱싱에 더욱 적합한 자료 구조가 되었다
