[DB] Index - 개념, 장단점, B+ Tree

zioo·2022년 7월 25일

인덱스가 무엇인지 인덱스를 모든 컬럼에 걸면 항상 좋은지 알아보자.

인덱스(index)란?

인덱스(Index)는 데이터베이스의 테이블에 대한 검색 속도를 향상 시켜주는 자료구조이다.

테이블의 특정 컬럼(Column)에 인덱스를 생성하면, 해당 컬럼의 데이터를 정렬한 후 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다. 컬럼의 값과 물리적 주소를 (key, value) 키, 값 의 한 쌍으로 저장한다.

데이터베이스의 index는 책의 색인과 같다. 만약 우리가 책에서 원하는 내용을 찾는다고 하면, 책의 모든 페이지를 찾아 보는것은 오랜 시간이 걸린다. 그렇기 때문에 책의 저자들은 책의 맨 앞 또는 맨 뒤에 색인을 추가한다.
마찬가지로 테이블에서 원하는 데이터를 찾기 위해 인덱스를 이용하면 빠르게 찾을 수 있다.
그러므로 데이터 = 책의 내용, 인덱스 = 책의 목차, 물리적 주소 = 책 페이지 번호라고 생각할 수 있다.

인덱스(index)의 장점과 단점

[장점]

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

핵심은 인덱스에 의해 데이터들이 정렬된 형태를 갖는다는 것이다. 기존엔 Where문으로 특정 조건의 데이터를 찾기 위해서 테이블의 전체를 조건과 비교해야 하는 '풀 테이블 스캔(Full Table Scan)' 작업이 필요했는데, 인덱스를 이용하면 데이터들이 정렬되어 있기 때문에 조건에 맞는 데이터를 빠르게 찾을 수 있다.
또 ORDER BY 문이나 MIN/MAX 같은 경우도 이미 정렬이 되어 있기 때문에 빠르게 수행할 수 있다.

[단점]

인덱스가 항상 정렬된 상태로 유지되어 오는 장점도 있지만, 그에 따른 여러 단점도 존재한다.

DB의 약 10%에 해당하는 추가 저장공간이 필요
인덱스를 관리하기 위해 추가 작업이 필요
잘못 사용할 경우 검색 성능 저하

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

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

이처럼 인덱스의 수정도 추가적으로 필요하기 때문에 데이터의 수정이 잦은 경우 성능이 낮아진다. 또 데이터의 인덱스를 제거하는 것이 아니라 '사용하지 않음'으로 처리하고 남겨두기 때문에 수정 작업이 많은 경우 실제 데이터에 비해 인덱스가 과도하게 커지는 문제점이 발생할 수 있다. 별도의 메모리 공간에 저장되기 때문에 추가 저장 공간이 많이 필요하게 된다.

또한 인덱스는 전체 데이터의 10 ~ 15% 이상의 데이터를 처리하거나, 데이터의 형식에 따라 오히려 성능이 낮아질 수 있다. 예를 들어 나이나 성별과 같이 값의 range가 적은 컬럼인 경우, 인덱스를 읽고 나서 다시 많은 데이터를 조회해야 하기 때문에 비효율적이다.

인덱스(index)를 사용하면 좋은 경우

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

규모가 큰 테이블
INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼
데이터의 중복도가 낮은 컬럼

인덱스를 사용하는 것 만큼이나 생성된 인덱스를 관리해주는 것도 중요하다. 그렇기 때문에 사용하지 않는 인덱스는 바로 제거를 해주어야 한다.

인덱스(Index)의 자료구조

인덱스는 여러 자료구조를 이용해서 구현할 수 있는데, 대표적으로 해시 테이블(Hash Table)과 B+Tree가 있다.

1. Hash Table

해시 테이블은 key와 value를 한 쌍으로 데이터를 저장하는 자료구조이다. (key, value)로 쌍을 표현하며, key값을 이용해 대응되는 value값을 구하는 방식이다. 해시 충돌이라는 변수가 존재하지만 평균적으로 O(1)의 매우 빠른 시간만에 원하는 데이터를 탐색할 수 있는 구조이다.

Hash Table은 인덱스에서 잘 사용되지 않는다.

해시 테이블은 등호(=) 연산에 최적화 되어 있다.
Database에서는 부등호 연산(<,>)이 자주 사용되는데, 해시 테이블 내의 데이터 들은 정렬되어 있지 않으므로 특정 기준보다 크거나 작은 값을 빠른 시간 내에 찾을 수 없다.

2. B+Tree

B+Tree는 오직 leaf node에만 데이터를 저장하고 leaf node가 아닌 node에서는 자식 포인터만 저장한다.
그리고 leaf node끼리는 Linked list로 연결되어있다.
또, B+Tree에서는 반드시 leaf node에만 데이터가 저장되기 때문에 중간 node에서 key를 올바르게 찾아가기 위해서 key가 중복될 수 있다.