[DB] 인덱스(index)란? 인덱스 자료구조

인덱스(index)란?

인덱스란 데이터베이스 테이블의 검색 속도를 향상하기 위한 자료구조라고 할 수 있다. 책의 색인(index)을 보면 해당 내용이 어디에 있는지 알 수 있듯이 데이터의 인덱스를 참조하면 데이터가 저장된 레코드의 주소를 알 수 있는 것이다.

 

DBMS는 데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과를 가져오기에는 시간이 너무 많이 걸리므로 칼럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 인덱스를 만들어둔다. 

 

DBMS의 인덱스는 항상 정렬된 상태를 유지하기 때문에 원하는 값을 탐색하는 데는 빠르지만 새로운 값을 추가하거나 삭제, 수정하는 경우에는 쿼리문 실행 속도가 느려진다. 

 

결론적으로 DBMS에서 인덱스는 데이터의 저장 성능을 희생하고 데이터의 읽기 속도를 높이는 기능이다.

 

인덱스의 장점과 단점

장점

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

단점

• 인덱스를 관리하기 위해 DB에 추가적인 저장공간이 필요하게 된다.
• 인덱스를 관리하기 위해 추가 작업이 필요하다.
• 인덱스를 잘못 사용하면 오히려 성능이 저하될 수 있다. 

인덱스의 성능과 고려해야할 사항

인덱스는 잘못 사용하면 오히려 성능이 저하될 수 있다고 하였다. 이는 인덱스를 생성하게 되면 INSERT, DELETE, UPDATE 쿼리문을 실행할 때 별도의 과정이 추가적으로 발생하기 때문이다. INSERT의 경우 인덱스에 대한 데이터를 추가해야 하고, DELETE의 경우 인덱스에 존재하는 값은 삭제하지 않고 사용하지 않는다는 표시만 남게 된다. 즉, ROW의 수가 그대로 남는다. 

 

실제 데이터가 10만인데 테이블에는 100만 개의 데이터가 있을 수 있다는 것이다. UPDATE는 더 큰 문제가 발생한다. 인덱스에 대한 데이터를 추가하는 것은 물론 변경 전 데이터도 사용하지 않음으로 바꿔야 하므로 INSERT, DELETE의 문제가 모두 발생한다.

 

인덱스는 데이터의 형식에 따라서도 성능이 달라질 수 있다. 데이터의 형식에 따라 인덱스를 만들었을 때 효율적인 데이터가 존재한다. 

 

예를 들어 이름,나이, 성별 세 가지의 필드를 갖고 있는 테이블을 생각해보자. 이 경우 이름에 대해서 인덱스를 생성하는 것이 효율적이다. 만약 성별을 기준으로 인덱스를 생성하면 제대로 인덱스의 기능을 할 수 없을 것이다.

 

따라서 인덱스는 다음과 같은 상황에서 사용하는 것이 좋다.

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

인덱스 자료구조

DBMS는 다음과 같은 인덱스 자료구조를 사용한다.

 

Hash 테이블 인덱스

hash table

칼럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘으로 매우 빠른 검색을 지원한다. 하지만 값을 변형해서 인덱싱 하므로 특정 문자로 시작하는 값으로 검색을 하는 전방 일치와 같이 값의 일부만으로 검색하고 할 때는 해시 인덱스를 사용할 수 없다. 주로 메모리 기반의 데이터베이스에서 많이 사용한다.

B+- Tree 인덱스

B+Tree는 DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조이다. B+Tree는 모든 노드에 데이터를 저장했던 B-Tree와 다음과 같이 다른 특성을 가지고 있다.

• 리프 노드(데이터 노드)만 인덱스와 함께 데이터를 가지고 있고, 나머지 노드들은 데이터를 위한 인덱스 만을 갖는다.
• 리프 노드들은 연결 리스트로 연결되어 있다.
• 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.

hash 테이블 방식은 O(1), B+-Tree 방식은 O(logn)의 시간 복잡도를 가지지만 일반적으로 데이터베이스에서는 B+-Tree 방식을 사용한다. 그 이유는 해시 함수는 등호(=) 연산에만 특화되었기 때문에 부등호 연산(<,>)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않기 때문이다.