[DB] 인덱스(Index) - 개념, 장단점, 인덱스의 자료구조

1. 인덱스(Index)란

출처 :  https://mangkyu.tistory.com/96

• 데이터베이스의 테이블에 대한 검색 속도를 향상시켜주는 자료구조
• 테이블의 특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터를 정렬한 후 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장
• 컬럼의 값과 물리적 주소를 key, value 의 한 쌍으로 저장
• 목차, 색인이라고 생각하면 됨
  • 데이터 = 책의 내용, 인덱스 = 책의 목차, 물리적 주소 = 책의 페이지 번호
  • 책에서 원하는 내용을 찾을 때 목차나 색인을 이용하면 훨씬 빠르게 정보를 찾을 수 있다.
  • 이처럼 테이블에서 원하는 데이터를 찾기 위해 인덱스를 이용하면 빠르게 찾을 수 있다.

 

 

2. 인덱스(Index)의 장단점

장점

• 테이블을 검색하는 속도와 성능이 향상
• 시스템의 전반적인 부하를 줄일 수 있다.

 

: 핵심은 인덱스에 의해 데이터들이 정렬된 형태를 갖는다.

: 기존에는 Where 문으로 특정 조건의 데이터를 찾기 위해 테이블의 전체를 조건과 비교해야하는 ‘풀 테이블 스캔(Full Table Scan)’ 작업이 필요했다.

: 하지만 인덱스를 이용하면 데이터들이 정렬되어 있기 때문에 조건에 맞는 데이터를 빠르게 찾을 수 있다.

: 또 ORDER BY 문이나 MIN/MAX 같은 경우도 이미 정렬이 되어 있기 때문에 빠르게 수행할 수 있다.

 

단점

• 인덱스를 관리하기 위한 추가 작업 필요
• 추가 저장 공간 필요
• 잘못 사용하는 경우 오히려 검색 성능 저하

 

: 인덱스를 항상 정렬된 상태로 유지해야 하기 때문에 인덱스가 적용된 컬럼에 삽입, 삭제, 수정 작업을 수행하면 다음과 같은 추가 작업이 필요

• INSERT : 새로운 데이터에 대한 인덱스를 추가
• DELETE : 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업 수행
• UPDATE : 기존의 인덱스를 사용하지 않음 처리, 갱신된 데이터에 대한 인덱스 추가

 

이처럼 인덱스의 수정도 추가적으로 필요해서 데이터의 수정이 잦으면 성능이 낮아진다.

또 데이터의 인덱스를 제거하는 것이 아니라 ‘사용하지 않음’으로 처리하고 남겨두기 때문에 수정 작업이 많은 경우 실제 데이터에 비해 인덱스가 과도하게 커지는 문제점이 발생할 수 있다.

별도의 메모리 공간에 저장되기 때문에 추가 저장 공간이 많이 필요하게 된다.

 

 

3. 인덱스를 사용하면 좋은 경우

• 규모가 큰 테이블
• 삽입, 수정, 삭제 작업이 자주 발생하지 않는 컬럼
• WHERE 절이나 ORDER BY, JOIN 등이 자주 사용되는 컬럼
• 데이터의 중복도가 낮은 컬럼

 

⇒ 인덱스를 효율적으로 사용하기 위해서는 데이터의 range 가 넓고 중복이 적을수록, 조회가 많거나 정렬된 상태가 유용한 컬럼에 사용하는 것이 좋다.

 

 

4. 인덱스의 자료구조

해시 테이블 - Hash Table

• key 와 value 를 한 쌍으로 데이터를 저장하는 자료구조
• key 값을 이용해 대응되는 value 값을 구하는 방식
• 해시 충돌이라는 변수가 존재하지만 평균적으로 O(1) 의 매우 빠른 시간만에 원하는 데이터 탐색 가능한 구조
• 해시 테이블을 이용한다면 인덱스는 (key, value) = (컬럼의 값, 데이터의 위치) 로 구현
• 하지만 해시 테이블은 실제로 인덱스에서 잘 사용되지 않음
  • 이유는 해시 테이블은 등호(=) 연산에 최적화 되어 있어서이다.
  • 데이터베이스에서는 부등호(<, >) 연산이 자주 사용되는데, 해시 테이블 내의 데이터들은 정렬되어 있지 않으므로 특정 기준보다 크거나 작은 값을 빠른 시간 내에 찾을 수 없다.

 

 

B+Tree

DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조

B+Tree는 모든 노드에 데이터(Value)를 저장했던 B-Tree와 다른 특성을 가지고 있다.

기존의 B-Tree는 어느 한 데이터의 검색은 효율적이지만, 모든 데이터를 한 번 순회하는 데에는 트리의 모든 노드를 방문해야 하므로 비효율적이다. 이러한 B-Tree의 단점을 개선시킨 자료구조가 B+Tree이다.

 

• 리프노드(데이터노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스노드)들은 데이터를 위한 인덱스(Key)만을 갖는다.
• 리프노드들은 LinkedList로 연결
• B+Tree에서는 반드시 leaf node에만 데이터가 저장되기 때문에 중간 node에서 key를 올바르게 찾아가기 위해 key가 중복될 수 있다.

 

• 이로 인한 장점
  1. leaf node를 제외하고 데이터를 저장하지 않기 때문에 메모리를 더 확보할 수 있다. 따라서 하나의 node에 더 많은 포인터를 가질 수 있기 때문에 트리의 높이가 더 낮아지므로 검색 속도를 높일 수 있다.
  2. Full scan을 하는 경우 B+Tree는 leaf node에만 데이터가 저장되어 있고, leaf node끼리 linked list로 연결되어 있기 때문에 선형 시간이 소모된다. 반면 B-Tree는 모든 node를 확인해야 한다.

데이터베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있다.

이러한 이유로 B-Tree의 리프노드들을 LinkedList로 연결하여 순차검색을 용이하게 하는 등 B-Tree를 인덱스에 맞게 최적화하였다.

(물론 Best Case에 대해 리프노드까지 가지 않아도 탐색할 수 있는 B-Tree에 비해 무조건 리프노드까지 가야한다는 단점도 있다.)

이러한 이유로 비록 B+Tree는 O(𝑙𝑜𝑔2𝑛log2n) 의 시간복잡도를 갖지만 해시테이블보다 인덱싱에 더욱 적합한 자료구조가 되었다.

 

 

 

참고 블로그

[DB] 11. 인덱스(Index) - (1) 개념, 장단점, B+Tree 등

[Database] 인덱스(index)란?