Index
인덱스(index)의 원래 뜻은 색인. 데이터베이스에서 조회 및 검색을 더 빠르게 할 수 있는 방법/기술,
혹은 이에 쓰이는 자료구조 자체를 의미하기도 한다.
사용 이유 와 특징
특정 조건을 만족하는 데이터 조회를 위해 인덱스를 사용한다.
인덱스가 없다면 full scan을 해야한다.
join, order by, group by 에서도 인덱스를 활용할 수 있다.
인덱스는 정렬이나 그룹화 작업에서도 사용될 수 있다.
기본키에 대해서는 자동적으로 인덱스를 생성한다.
하지만 DBMS에 따라 외래키의 경우 index가 자동 생성되지 않을 수도 있다.MySQL 은 자동으로 생성한다.
사용 예시
- primary key에서는 index가 자동으로 생성된다.
- 여려 개의 속성을 그룹지어서 index를 걸수도 있는데
이를 multicolum index 또는 composite index 라고한다.
만들어진 인덱스 보는법
SHOW INDEX FROM [Table name]으로 확인할 수 있다.
동작 방식
인덱스가 있는 속성만 조건에 사용된 경우
MEMBERS 테이블에서 속성 a 에 대해 인덱스를 만들면
다음과 같이 INDEX 테이블이 만들어진다.INDEX 테이블은 속성값을 정렬한 상태로 저장되며
각각의 인덱스가 실제 테이블 레코드의 참조값(ptr)을 가진다.
이외에도 여러 정보들을 가진다.
만약 where 절로 index를 가진 속성의 값을 찾는다면
인덱스 테이블에서 Binary Search 로 해당 조건의 값을 찾는다.
Binary Search의 첫 단계인 mid 가 5로 설정된 모습이다.
Binary Search로 조건 값인 9를 찾는다.위 예제의 경우 9라는 값이 하나만 존재하는데
9 값이 여러개 존재할 수 있다.이 경우 BS로 찾아진 값을 기준으로 아래, 위를 탐색해서
조건에 만족하는 모든 index 값을 찾는다.
인덱스가 있는 속성과 인덱스가 없는 속성이 같이 조건에 사용된 경우
조건이 두 개 이상 있는 경우이다.
b의 인덱스는 존재하지 않는다.BS 로 인덱스에서 a 값이 7인 것들을 모두 찾고
찾아진 대상들(3개)을 기준으로 Full Scan이 일어난다.즉, 성능적 개선이 필요한데
이러한 경우 multicolunm index 를 만들어서 성능적 개선을 일으킬 수 잇다.
multicolunm index가 있는 경우
속성을 그룹화해서 index가 생성된 경우,
먼저 선언된 속성을 우선적으로 정렬해서 인덱스 테이블을 생성한다.
WHERE a = 7 AND b = 95의 경우
a 조건의 대상을 먼저 BS 로 찾은 다음
이 대상으로 다시 b 조건을 대상으로 BS 로 다시 찾는다.최종적으로 찾아진 대상을 ptr를 통해 실제 데이터 베이스에 접근한다.
만약 multicolunm index 이 있고 최우선 순위가 아닌 속성만 조건 절에 사용된 경우
문제가 발생한다.b 속성을 살펴보면 전체적으로 정렬이 되어있지 않다.
이 경우, BS 가 불가능하기 때문에 이 인덱스 테이블을 사용할 수 없다.
따라서 DBMS는 인덱스 테이블을 무시하고 Full Scan이 일어나거나
일부 Full Scan이 일어나더라도 인덱스 테이블을 사용할 수도 있다.
즉 multicolunm index를 만들때 우선 순위가 매우 중요함을 알 수 있다.
이 현상을 해결하려면 b에 해당하는 인덱스 테이블을 추가적으로 생성하면 된다.
DBMS가 사용한 index
SELECT * FROM player WHERE backnumber = 7의 경우,
backnumber가 후순위 우선순위이기 때문에 인덱스를 사용할 수 없어서 Full Scan 이 일어난다.
SELECT * FROM play WHERE team_id = 110 OR backnumber = 7의 경우
team_id는 인덱스 테이블에서 정렬되어있지만 backnumber의 경우 정렬되어 있지 않아서
muticolumn 인덱스를 사용하지 않거나 team_id에서만 BS가 실행될 것이다.
DBMS 가 사용한 index를 알 수 있는 방법은 다음과 같다.
SELECT * FROM play WHERE team_id = 110 OR backnumber = 7의 문제점을 해결하기 위해
backnumber의 index를 하나더 만든 상태이다.쿼리문 최상단에
EXPLAIN문을 붙이면 사용할 수 있는 인덱스(possible_keys) 와
그 중에 사용된 인덱스(key) 가 출력된다.사용되는 인덱스는 DBMS의 optimzer에 의해서 선택된다.
직접 사용할 인덱스 선택하기
USE INDEX: 인덱스를 사용할때 붙이라고 권장되는 사항이다. 안붙이면 Full Scan이 일어날 수 있다.
FORCE INDEX: 강제적으로 사용할 인덱스를 지정한다.
구현 및 사용 알고리즘
DBMS는 인덱스를 HashTable, B+Tree 등 다양한 알고리즘으로 관리를 하고 있는데
일반적으로 사용되는 알고리즘은 B+ Tree 알고리즘이다.
인덱스 생성 남발 금지
인덱스는 따로 테이블의 형태로 관리가 된다.
자원을 소모한다는 의미이다.
즉, 무분별한 인덱스의 사용은 성능에 부정적인 영향을 미칠 수 있다.
인덱스 생성시 참조 값 같은 추가적인 데이터가 필요하기 때문에 추가적인 공간이 필요해지는
오버헤드가 발생한다.
검색과 조회의 속도를 향상시킬 수 있지만
잦은 데이터의 변경(삽입, 수정 삭제)가 된다면
인덱스 데이블을 변경과 정렬에 드는 오버헤드 때문에 오히려 성능 저하가 일어날 수 있다.
INSERT: 테이블에는 입력 순서대로 저장되지만, 인덱스 테이블에는 정렬하여 저장하기 때문에 성능 저하 발생
DELETE: 테이블에서만 삭제되고 인덱스 테이블에는 남아있어 쿼리 수행 속도 저하
UPDATE: 인덱스에는 UPDATE가 없기 때문에 DELETE, INSERT 두 작업 수행하여 부하 발생
데이터의 중복이 높은 컬럼(카디널리티가 낮은 컬럼)은 인덱스로 만들어도 무용지물 (예: 성별)
다중 컬럼 인덱싱할 때 카디널리티가 높은 컬럼->낮은 컬럼 순으로 인덱싱해야 효율적
Covering Index
조회하고자 하는 속성들이 모두 index 테이블에 있는 경우,
참조값을 통해서 실제 데이터베이스에 접근하지 않고
인덱스 테이블에서 바로 반환한다.참조하는 과정이 사라지게 되므로 조회 성능 향상이 가능하다.
이를 위해서 의도적으로 만든 index를 Covering Index 라고 한다.
Hash Index
앞에서 설명한 인덱스들은 B+Tree로 구현되어 있다.
Hash Index는 Hash Table 로 구현되어있는 인덱스이다.
특징
Hash Table 로 구현
시간 복잡도 O(1)
rehashing에 대한 부담
hash table에 추가가 계속된다면 table 사이즈를 늘려줘야하는데 여기서 오버헤드가 발생한다.
이 작업을 rehashing 이라고 한다.
해쉬값으로 값을 관리하기 때문에 범위 연산은 불가능
multicolumn index의 경우 전체 속성에 대한 조회만 가능하다.
즉 일반 index에서 처럼 부분 사용이 불가능하다는 것이다.
Full Scan이 더 좋은 경우
데이터가 조금 있는 경우
인덱스를 사용하거나 안사용하거나 성능차이가 별로 없다
오히러 인덱스를 사용하면 공간을 더 차지한다.
조회하려는 데이터가 테이블의 상당 부분을 차지하는 경우
