[데이터베이스] 인덱스(Index)

1. 인덱스란?

(http://www.btechsmartclass.com/data_structures/b-trees.html)

 

인덱스(Index)란 색인을 의미한다. 색인이란 책에서 중요한 단어나 항목, 고유명사 등을 쉽게 찾을 수 있도록 그것들을 일정 순서에 따라 배열한 목록이다. 데이터베이스 분야에서 말하는 인덱스는 테이블에 대한 동작의 속도를 높여주는 자료 구조를 일컫는다.

 

만약 색인이 없다면 원하는 내용을 찾을 때 일일이 책장을 넘기며 찾아야 하는 것처럼 데이터베이스에서도 인덱스가 없다면 Full Table Scan을 해야 한다.

 

(http://www.btechsmartclass.com/data_structures/b-trees.html)

인덱스는 기본적으로 <키 값, 주소>의 쌍으로 구성된다. 데이터 레코드에 접근하기 위해선 키 값을 통해 해당하는 인덱스를 찾고, 그 인덱스가 가리키는 주소를 따라가 원하는 레코드에 접근하면 된다.

 

2. 인덱스의 구조

1) B-Tree

• 데이터가 정렬된 상태로 유지
• 한 노드 당 자식 노드가 2개 이상
• 어떤 연산을 수행하더라도 균형을 유지함
• key값을 이용해 데이터를 찾음
• 하나의 노드는 하나의 디스크 페이지에 저장 -> key + value(= data, record address)

(http://www.btechsmartclass.com/data_structures/b-trees.html)

장점

• 언제나 균등한 탐색속도(log N)를 보장한다.
• 자주 접근되는 노드를 루트 노드에 가까이 배치하면 검색 속도가 향상됨

단점

• 순차접근시 과도한 디스크 I/O 발생 (중위순회)

 

2) B+Tree

• B Tree의 단점을 보완
• 내부 노드에는 key만 저장, 리프 노드에 key+value를 함께 저장
• 리프 노드는 연결리스트 형태로 연결되어 있음
• 인덱스 세트: 내부 노드로 구성, 리프 노드에 있는 키들에 대한 경로만 제공
• 순차 세트: 리프 노드로 구성, 모든 키 값들을 저장, 순차적으로 연결

(https://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/)

장점

• 순차접근 속도가 빠름
• 디스크 I/O가 적음

단점

• 리프 노드까지 가야 데이터 존재

 

3) 해시 테이블

• key와 value의 쌍으로 데이터 저장
• 해싱 함수를 이용해서 매핑
• 해싱 함수: key -> value

(https://en.wikipedia.org/wiki/Hash_table)

장점

• 매우 빠른 검색 속도(O(1))

단점

• 등호 연산에만 특화, 부등호 연산에는 부적합

 

3. 인덱스의 종류

기본 인덱스(Primary Index) vs 보조 인덱스(Secondary Index)

• 기본키에 대한 인덱스인가?

집중 인덱스(Clustered Index) vs 비집중 인덱스(Non-Clustered Index) -> 참고

• 데이터 레코드가 키 값 순으로 정렬되어 있는가?

밀집 인덱스(Dense Index) vs 희소 인덱스(Sparse)

• 모든 키에 대하여 인덱스 엔트리가 있는가?

 

 

4. 인덱스의 장단점

장점

• SEARCH 연산 속도 향상
• 정렬 속도 향상

단점

• 인덱스를 생성하는 데 추가적인 메모리 소요
• INSERT, UPDATE, DELETE 연산 시 시간 추가 소요

 

5. 그렇다면 인덱스를 언제, 어떻게?

• 테이블에 데이터가 많을 때
• INSERT, UPDATE, DELETE 연산이 자주 발생하지 않는 테이블
• JOIN, WHERE, ORDER BY에 자주 사용되는 칼럼
• 데이터의 중복도가 낮은 칼럼 (= 카디널리티가 높은 칼럼)

 

6. 참고

• 데이타베이스 시스템(이석호 저)
• https://mangkyu.tistory.com/96
• https://zorba91.tistory.com/293
• https://brunch.co.kr/@skeks463/25