추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조
만약, index 를 사용하지 않은 컬럼을 조회해야 되는 상황이라면 전체를 탐색해야 되기때문에 속도가 떨어지게 된다.
•
인덱스를 활용하면 select, update, delete 성능이 함께 향상된다.
인덱스 관리
DBMS 는 인덱스를 항상 최신의 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다. 따라서, 적용된 칼럼에 insert, delete, update 가 수행된다면 다음의 연산을 추가적으로 해주어야 하며 그에 따른 오버헤드가 발생한다.
•
insert : 새로운 데이터에 대한 인덱스를 추가함
•
delete : 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행함
•
update : 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대해 인덱스를 추가
인덱스의 장점과 단점
•
장점
◦
테이블을 조회하는 속도와 성능을 향상시킬 수 있다.
◦
전반적인 시스템 부하를 줄일 수 있다
•
단점
◦
인덱스를 저장하기 위한 DB 의 약 10%에 해당하는 공간이 필요
◦
인덱스를 관리하기 위한 추가 작업이 필요
◦
인덱스를 잘못 관리할 경우 오히려 성능이 저하되는 역효과 발생
역효과에 대해 create, update, delete 가 빈번한 속성에 대해 인덱스를 걸게 되면 인덱스의 크기가 비대해져서 성능이 오히려 저하되는 역효과를 가져올 수 있다.
이유 중 하나는 delete, update 연산 때문인데 , update 와 delete 는 기존 인덱스를 삭제하는 것이 아니라 ‘사용하지 않음’ 처리를 해주기 때문에 빈번하게 update 와 delete 가 발생하게 되면 인덱스가 비대해져서 성능이 저하되는 문제가 발생하는 것이다.
인덱스를 사용하면 좋은 경우
•
규모가 작지 않은 테이블
•
insert, update, delete 가 자주 발생하지 않는 칼럼
•
join 이나 where 또는 order by에 자주 사용되는 칼럼
•
데이터의 중복도가 낮은 칼럼
•
기타 등등
인덱스의 자료구조
인덱스를 구현하기 위해서는 다양한 자료구조가 사용될 수 있는데, 대표적인 것이 해시 테이블과 B+Tree 가 있다.
해시 테이블
해시 테이블은 (key, value) 로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용하다. 해시 테이블은 key 값을 이용해 고유한 index 를 생성해서 그 index 에 저장된 값을 꺼내오는 구조다.
해시 테이블 기반의 DB 인덱스는 (데이터=컬럼 값, 데이터 위치) 를 (key, value) 로 사용해서 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현했다. 해시 테이블의 시간 복잡도는 O(1)이며 매우 빠른 검색을 지원한다.
하지만, DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적인데, 그 이유는 해시가 등호(=)연산에만 특화되었기 때문이다. 해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이런 특성때문에 부등호 연산(> , <) 이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.
예를 들어, “나는” 으로 시작하는 모든 데이터를 탐색하기 위한 쿼리문은 해시 테이블의 인덱스 혜택을 전혀 받지 못한다. 이런 이유로 데이터베이스의 인덱스는 B+Tree 가 더 일반적으로 사용된다.
B+Tree
DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조다. B+Tree 는 모든 노드에 데이터를 저장했던 BTree와 다른 특성을 가지고 있다.
•
리프 노드(데이터 노드)만 인덱스와 함께 데이터를 가지고 있고, 나머지 노드(인덱스 노드)들은 데이터를 위한 인덱스만을 갖는다.
•
리프노드들은 LinkedList 로 연결되어 있다
•
데이터 노드 크기는 인덱스 노드 크기와 같지 않아도 된다.
데이터베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있다. 이러한 이유로 BTree의 리프노드들을 LinkedList로 연결하여 순차검색을 용이하게 하는 등 BTree를 인덱스에 맞게 최적화했다.
(물론 Best Case에 대해 리프노드까지 가지 않아도 탐색할 수 있는 BTree에 비해 무조건 리프노드까지 가야한다는 단점도 있다.)
이런 이유로 B+Tree 는 O(log2n)의 시간복잡도를 갖지만 해시테이블보다 인덱싱에 더욱 적합한 자료구조가 되었다고 한다.