INDEX 란?
Index는 DB 분야에 있어서 테이블에 대한 동작의 속도를 높여주는 자료 구조를 일컫는다. Index는 테이블 내 1개의 컬럼, 혹은 여러 개의 컬럼을 이용하여 생성될 수 있다. 고속의 검색 동작뿐만 아니라 레코드 접근과 관련 효율적인 순서 매김 동작에 대한 기초를 제공한다.
추가적인 쓰기 작업과 저장공간을 활용하여 DB테이블의 검색 속도를 향상시키기위한 자료구조이다.
책의 목차?, 색인과 같다.
EX) FULL SCAN 시 당연히 처리 속도가 떨어질 것이다.
인덱스의 관리
DBMS는 인덱스를 항상 최신의 정렬된 상태를 유지해야 원하는 값을 빠르게 탐색할 수 있다. 인덱스가 적용된 DML(INSERT, UPDATE,DELETE)등이 수행된다면 추가적인 연산이 필요하며, 그에 따른 오버헤드가 발생한다.
INSERT: 새로운 데이텉에 대한 인덱스를 추가함.
DELETE: 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행한다.
UPDATE: 기존의 인덱스를 사용하지 않음을 처리하고, 갱신된 데이터에 대해 인덱스를 추가함.
인덱스의 장단점
| 장점 | 단점 |
|---|---|
| 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬수 있다. | 관리를 위해 10%에 해당하는 공간이 필요하다 |
| 전반적인 시스템의 부하를 줄일수 있다. | 관리를 위한 추가작업이 필요하다. |
| 잘못사용할 경우오히려 성능이 저하되는 역효과가 발생한다. |
인덱스의 자료구조
인데스를 구현하기 위한 다양한 자료구조 중 대표적인 두가지를 소개한다.
해시 테이블
KEY,VALUE 쌍으로 데이터를 저장하는 자료구조중 하나로 빠른 데이터 검색이 필요할때 유용하다.
KEY 값을 통해 고유한 INDEX를 생성하여 INDEX의 값을 가져오는 구조이다.
내부에 버켓이라는 배열이 존재하는데, 해시 함수를 통해 KEY를 고유한 해시값으로 변환 -> 이를 버켓 배열의 인덱스로 사용하며 해당 인덱스에 VALUE를 저장.
◻ 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현, 시간복잡도는 0(1)이며, 매우 빠르다.
◻ 해시테이블이 사용되는 경우는 제한적인데, 등호('=')연산에 특화되어 값이 1이라도 달라지면 다른 해시 값을 생성한다. =>부등호('>,<') 연산에 어울리지 않는다.
EX) 해시 충돌 등등
B+TREE
DB인덱스를 위해 자식 노드가 2개 이상인 B-TREE를 개선시킨 자료구조이다.
모든 노드에 데이터를 저장하지 않는다.
◻ 리프노드(데이터 노드)만 인덱스와 함께 VALUE를 가지며, 나머지 노드들은 데이터를 위한 인덱스(KEY)만 갖는다.
◻ LINKED LIST로 연결되어 있다.
◻ 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.
B-TREE
자식 노드가 2개 이상인 트리, 이진검색트리처럼 각 KEY의 왼쪽자식은 KEY보다 작은값을, 오른쪽은 큰값을가진다.
B-TREE 기반 인덱스는 특정 컬럼의 값에 해당하는 노드에 VALUE를 저장한다(데이터 위치)
◻ B-TREE의 KEY-VALUE 값은 항상 키를 기준으로 오름차순
◻ 균형트리로 최상위 루트노드에서 리프노드까지의 거리가 동일하므로 시간복잡도는o(logN)이다.
◻ 데이터 갱신 반복으로 인해 균형이 깨지면 성능이 악화된다.
◻ B-Tree가 해시 테이블보다 부등호를 이용한 검색 연산 성능이 좋지만, 순차 검색의 경우 중위 순회를 하기 때문에 효율이 좋지 않다.
참고
