[DataBase] 인덱스 (Index)

이번 포스팅에서는 데이터베이스에서 성능적인 측면에서 중요한 부분인 인덱스(Index)에 대해 알아보도록 하겠습니다. 평소 인덱스란 무엇인지 알고는 있었지만 정확한 개념을 이해하고 정리하기 위해 포스팅을 작성하게 되었습니다.

 

 

 

 

인덱스 (Index)

인덱스는 추가적인 쓰기 작업과 저장 공간을 활용해 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조입니다. 

책에서 원하는 내용을 찾을 때, 모든 페이지를 찾아 보는것은 오랜 시간이 필요하겠죠 ? 그렇기 때문에 책의 저자들은 책의 맨 앞 또는 맨 뒤에 색인을 추가하는데 데이터베이스의 index는 책의 색인과 같다고 할 수 있습니다. 

데이터베이스 역시, 책과 마찬가지로 테이블의 모든 데이터를 검색하면 시간이 오래 걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조를 생성해 빠르게 조회할 수 있도록 인덱스를 지원하고 있어요.

 

 

 

🙋🏻‍♂️ 그럼 인덱스를 사용했을 때 조회 이외의 어떤 부분에서 또 성능이 향상될까요 ?

인덱스를 활용하면 데이터를 조회하는 SELECT 외에도 UPDATE나 DELETE의 성능이 함께 향상됩니다. 이유는 해당 연산을 수행하기 위해서는 해당 대상을 조회해야만 작업을 수행할 수 있기 때문입니다.

// Zero라는 이름을 업데이트 해주기 위해서는 Zero를 조회해야 합니다.
UPDATE USER SET NAME = 'Zerozae' WHERE NAME = 'Zero';​

만약 index를 사용하지 않은 컬럼을 조회해야 하는 상황이라면 전체를 탐색하는 Full Scan을 수행해야 하고, 전체를 비교하여 탐색하기 때문에 처리 속도가 당연히 떨어지게 됩니다.

어라.. 나는 분명 UPDATE와 DELETE 연산은 index를 사용하면 성능이 저하될 수 있다고 알고 있는데 ?...

 

 

[ 인덱스의 관리 ]

DBMS는 index를 항상 최신의 정렬 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있기 때문에 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE가 수행된다면 각각 다음과 같은 연산을 추가적으로 해줘야하고 그에 따른 오버헤드가 발생합니다.

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

 

이에 따라 인덱스의 장점과 단점을 살펴보면 

 

🔍 [ 장점 ]

- 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다.

- 전반적인 시스템의 부하를 줄일 수 있다.

 

 

🔍 [ 단점 ]

- 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다.

- 인덱스를 관리하기 위해 추가 작업이 필요하다.

- 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.

 

 

만약, CREATE & DELETE & UPDATE가 빈번한 속성에 인덱스를 걸게 되면 인덱스의 크기가 비대해져 성능이 오히려 저하되는 역효과가 발생할 수 있게 됩니다. 앞서 설명한대로 UPDATE와 DELETE는 기존의 인덱스를 삭제하지 않고 '사용하지 않음' 처리를 해준다고 했는데요! 만약 어떤 테이블에 UPDATE와 DELETE가 빈번하게 발생된다면 실제 데이터는 10,000건 이지만 인덱스는 훨씬 많이 존재하게 되어 SQL문 처리 시 비대해진 인덱스에 의해 오히려 성능이 떨어지게 됩니다.

 

 

❓ 인덱스를 관리하기 위해 DB의 약 10%의 저장공간이 필요하다는 것은 무슨 말일까

데이터베이스 서버를 껐다 켜도 인덱스는 그대로 남아있다. 물론 메모리에도 저장하겠지만 디스크에도 별도의 저장 공간에 인덱스를 저장해두기 때문인데 따라서 인덱스를 위해 물리적 저장공간이 필요하다. 라고 해석하면 된다.

 

 

 

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

그래서, 인덱스를 언제 사용하면 될까?.. 라는 기준을 다음과 같이 세울 수 있습니다.

 

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

인덱스를 사용하는 것 만큼 생성된 인덱스를 관리해주는 것도 중요하다고 합니다. 그러므로 사용하지 않는 인덱스는 꼭 바로 제거를 해주도록 합시다.

 

 

 

 

인덱스의 자료구조

인덱스를 구현하기 위해서는 다양한 자료구조를 사용할 수 있는데, 가장 대표적인 해시 테이블과 B+Tree에 대해 알아보도록 하겠습니다.

 

 

[ 해시 테이블 ]  - Hash Table

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

해시 테이블 기반의 DB 인덱스는 (데이터 = 컬럼의 값, 데이터의 위치)를 (Key,Value)로 사용해 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현합니다. 시간 복잡도는 O(1)이며 매우 빠른 검색을 지원합니다.

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

즉, 예를 들면 '김'으로 시작하는 모든 데이터를 검색하기 위한 쿼리문은 인덱스의 혜택을 전혀 받지 못하게 되기 때문에 이런 이유로 데이터베이스의 인덱스에서는 B+Tree가 일반적으로 사용됩니다.

 

 

[ B+Tree ]

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

 

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

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

물론, Best Case에 대해 리프노드까지 가지 않아도 탐색이 가능한 B-Tree에 비해 무조건 리프노드까지 가야한다는 단점도 있다. 이러한 이유로 비록 B+Tree는 O(logn)의 시간 복잡도를 갖지만 해시 테이블보다 인덱싱에 더욱 적합한 자료구조가 되었습니다.

 

 

➡️ 예시를 하나 들어보겠습니다.

 

department 테이블에서 10,000개의 레코드를 가지고 이 중 dept_name = '컴퓨터공학과'인 레코드를 검색할 때 인덱스가 없다면 최악의 경우 10,000개의 레코드를 모두 검색하는 상황이 발생합니다. 그런데 dept_name 필드에 차수가 10인 B+Tree 인덱스가 있다면 ?

 

• B+Tree의 높이 = [log10 10000] = 4
• 차수가 10, 검색 키 값의 수가 최대 10,000개이므로 B+Tree의 높이는 최대 4를 넘지 않는다.
• 최대 4개의 노드만 읽으며 원하는 레코드들을 찾을 수 있다.

 

 

 

 

< 참고 자료 >

[Database] 인덱스(index)란?

SQL 데이터베이스(DB) B+ tree 인덱스, 복합 인덱스