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

Index란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상하기 위한 자료구조이다.

우리가 책에서 원하는 내용을 찾는다고 하면, 책의 모든 페이지를 찾아보는 것은 오래걸린다. 그래서 책의 맨 앞이나 두에 색인을 추가하는데, 이와 비슷한 역할을 수행한다.

데이터베이스에서도 테이블의 모든 데이터를 검색하면 시간이 오래걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조를 생성하여 빠르게 조회할 수 있도록 한다.

 

인덱스를 활용하면 데이터를 조회하는 SELECT 외에도 UPDATE나 DELETE의 성능이 함께 향상된다. 만약 Index를 사용하지 않은 컬럼을 조회해야 하는 상황이라면 전체를 탐색하는 Full Scan을 수행해야 한다. Full Scan은 전체를 비교하여 탐색하기 때문에 처리 속도가 떨어진다.

 

Index의 관리

DBMS는 index를 항상 최신의 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다. 그렇기 때문에 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE가 수행된다면 각각 다음과 같은 연산을 추가적으로 해주어야 한다.

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

 

Index의 장점과 단점

장점

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

단점

• 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다.
• 인덱스를 관리하기 위해 추가 작업이 필요하다.
• 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.

 

만약 CREATE, DELETE, UPDATE가 빈번한 속성에 인덱스를 걸면 인덱스의 크기가 비대해져서 성능이 오히려 저하되는 역효과가 발생할 수 있다. 

 

Index를 사용하면 좋은 경우

• 규모가 작지 않은 테이블
• INSERT, UPDATE, DELETE가 자주 발생하지 않는 Column (변경 최소화)
• JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 Column
• 데이터의 중복도가 낮은 Column → 중복도가 높으면 인덱스가 무의미해진다.
• ...

Index의 자료구조

인덱스를 구현하기 위해서는 여러 가지  자료구조를 사용할 수 있는데, 그 중 Hash Table과 B+ Tree가 가장 대표적이다.

 

1. Hash Table

해시 테이블은 Key-Value 형식으로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용하다. 해시 테이블은 Key값을 이용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조이다.

해시 테이블 기반의 DB 인덱스는 key = Column의 값, value = 데이터의 위치로 사용하여 Column의 값으로 생성된 해시를 통해 인덱스를 구현하였다. Hash Table의 시간 복잡도는 O(1)이며 매우 빠른 검색을 지원 한다.

하지만 DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적이다. 왜냐하면 해시가 등호(=) 연산에만 특화되었기 때문이다. 해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이러한 특성에 의해 부등호 연산(>,<)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.

 

2. B+ Tree

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

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

데이터베이스의 인덱스 Column은 부등호를 이용한 순차 검색 연산이 자주 발생할 수 있다. 이러한 이유로 B+Tree의 리프노드들을 LinkedList로 연결하여 순차 검색을 용이하게 하는 등 B+Tree를 인덱스에 맞게 최적화하였다.

만약 최선의 경우 B-Tree를 쓰면 리프노드까지 가지 않아도 탐색할 수 있는데도 B+Tree는 무조건 리프노드까지 가야한다는 단점이 있다...

비록 B+Tree는 $$O(log_2n)$$의 시간 복잡도를 갖지만 Hash Table보다 인덱싱에 더욱 적합한 자료구조이다.🚀

 

Clustered Index

Cluster(클러스터)란 여러 개를 하나로 묶는다는 의미로 주로 사용되는데, Clustered Index(클러스터드 인덱스)도 이와 유사하다. 인덱스에서 비슷한 것들을 묶어서 저장하는 형태로 구현되는데, 이는 주로 비슷한 값들을 동시에 조회하는 경우가 많다는 점에서 착안된 것이다. 여기서 비슷한 값들은 물리적으로 인접한 장소에 저장되어 있는 데이터들을 말한다.

 

클러스터드 인덱스는 테이블의 Primary Key에만 적용되는 내용이다. 즉 Primary Key값이 비슷한 레코드끼리 묶어서 저장하는 것을 클러스터드 인덱스라고 표현한다. 클러스터드 인덱스에서는 Primary Key 값에 의해 레코드의 저장 위치가 결정되며 프라이머리 키 값이 변경되면 그 레코드의 물리적인 저장 위치 또한 변경되어야 한다. 그렇기 때문에 Primary Key를 신중하게 결정하고 클러스터드 인덱스를 사용해야 한다.

클러스터드 인덱스는 테이블 당 한 개만 생성할 수 잇다. Primary Key에 대해서만 적용되기 때문이다. 이에 반해 Non Clustered Index는 테이블당 여러 개를 생성할 수 있다.

 

Composite Index

인덱스로 설정하는 필드의 속성이 중요하다. title, author 이 순서로 인덱스를 설정하면 title을 search하는 경우, index를 생성한 효과를 볼 수 있지만 author만으로 search하는 경우 index를 생성한 것이 소용없어진다. 따라서 SELECT 질의를 어떻게 할 것인가가 인덱스를 어떻게 생성할 것인가에 대해 많은 영향을 끼치게 된다.

 

참고

• https://mangkyu.tistory.com/96
• https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Database