Appearance
Index(인덱스)
목적
추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조테이블의 칼럼을 색인화한다.
마치, 두꺼운 책의 목차와 같다고 생각하면 편하다.
데이터베이스 안의 레코드를 처음부터 풀스캔하지 않고, B+ Tree로 구성된 구조에서 Index 파일 검색으로 속도를 향상시키는 기술이다.
파일 구성
인덱스와 테이블의 실제 저장 방식은 DBMS와 스토리지 엔진마다 다르다.
- 과거 MySQL
MyISAM은.frm,.MYD,.MYI파일 구조를 사용했다. - 현재 MySQL 기본 엔진인
InnoDB는 데이터와 인덱스를 tablespace(.ibd등)에 저장하고, MySQL 8.0부터는.frm도 data dictionary로 대체되었다.
즉, "인덱스는 항상 별도 파일(MYI)로 저장된다"는 설명은 MyISAM 기준의 옛 설명이며, 현대 MySQL 기본값인 InnoDB에는 그대로 적용되지 않는다.
단점
- 인덱스를 만들면 추가 저장 공간이 필요하다.
- 쓰기 시 인덱스도 함께 관리해야 하므로 INSERT/UPDATE/DELETE 비용이 증가한다.
- 인덱스 된 Field에서 Data를 업데이트하거나, Record를 추가 또는 삭제시 성능이 떨어진다.
- 데이터 변경이 잦으면 페이지 분할(page split), 단편화, 추가 I/O가 발생할 수 있다.
상황 분석
사용하면 좋은 경우
(1) Where 절에서 자주 사용되는 Column
(2) 외래키가 사용되는 Column
(3) Join에 자주 사용되는 Column
Index 사용을 피해야 하는 경우
(1) Data 중복도가 매우 높아 단독 인덱스 선택도가 낮은 Column
(2) DML이 자주 일어나는 Column
DML이 일어났을 때의 상황
INSERT
인덱스 페이지에 여유 공간이 부족하면 page split이 일어나 추가 I/O와 재배치 비용이 발생할 수 있다.
이 과정에서 쓰기 성능이 떨어지고 단편화가 심해질 수 있다.
DELETE
<Table과 Index 상황 비교>
행이 삭제되면 인덱스 엔트리도 함께 정리되어야 한다.
다만 실제 공간 회수와 병합(coalesce) 시점은 엔진마다 다르며, 즉시 물리적으로 정리되지 않아 단편화가 남을 수 있다.
UPDATE
특히 인덱스가 걸린 컬럼 값이 바뀌면 많은 엔진에서 기존 키 삭제 + 새 키 삽입과 유사한 비용이 발생한다.
인덱스 관리 방식
B-Tree 자료구조
이진 탐색트리의 개념을 일반화한 다원 탐색 트리(multi-way search tree)로, 하나의 노드에 여러 개의 키와 자식 포인터를 가질 수 있다
자식 노드를 둘이상 가질 수 있고 Balanced Tree 라는 특징이 있다 → 즉 탐색 연산에 있어 O(log N)의 시간복잡도를 갖는다.
모든 노드들에 대해 값을 저장하고 있으며 포인터 역할을 동반한다.
B+Tree 자료구조
B-Tree를 개선한 형태의 자료구조
값을 리프노드에만 저장하며 리프노드들 끼리는 링크드 리스트로 연결되어 있다 → 때문에 부등호문 연산에 대해 효과적이다.
리프 노드를 제외한 노드들은 포인터의 역할만을 수행한다.
HashTable 자료구조
해시 함수를 이용해서 값을 인덱스로 변경 하여 관리하는 자료구조
일반적인 경우 탐색, 삽입, 삭제 연산에 대해 O(1)의 시간 복잡도를 갖는다.
다른 관리 방식에 비해 빠른 성능을 갖는다.
최악의 경우 해시 충돌이 발생하는 것으로 탐색, 삽입, 삭제 연산에 대해 O(N)의 시간복잡도를 갖는다.
해시 기반 인덱스는 동등 비교(
=)에 강하지만, 범위 조회(<,>,BETWEEN)나 정렬에는 적합하지 않다.