인덱스 (feat. 인덱스의 구조 및 내부작동)

TIL. 인덱스 학습 키워드

---

# Keyword

1. 인덱스란 무엇인가?

2. 인덱스의 종류

3. 인덱스의 자료구조

4. 인덱스의 내부작동

5. 클러스터형 인덱스와 보조 인덱스의 구조

6. 마무리 정리

# Reference

이것이 MySQL이다 (책)

망나니 개발자 (블로그)

 

1. 인덱스(Index)란?

---

[ 인덱스(index)란? ]

인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다. 만약 우리가 책에서 원하는 내용을 찾는다고 하면, 책의 모든 페이지를 찾아 보는것은 오랜 시간이 걸린다. 그렇기 때문에 책의 저자들은 책의 맨 앞 또는 맨 뒤에 색인을 추가하는데, 데이터베이스의 index는 책의 색인과 같다.

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

 

인덱스를 비유해 보자면 "검색기능"과 같다고 생각한다. 한 행사에 1000명의 선수가 참가한다. 우리는 1000명의 선수중 "메시"를 찾으려면 처음부터 끝까지 다 찾아야 한다. 하지만 검색기능이 있다면 메시를 검색하고 몇번째에 있는지 확인한다면 금방찾을 수 있다. 물론 책의 색인도 좋은 예시이다!

 

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

// Mang이라는 이름을 업데이트 해주기 위해서는 Mang을 조회해야 한다.
UPDATE USER SET NAME = 'MangKyu' WHERE NAME = 'Mang';

 

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

 

 

[ 인덱스(index)의 관리 ]

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

 

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

 

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

 

장점

• 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다. (단 항상 그런것은 아니다. 뒤에서 추가 설명!)
• 쿼리의 부하가 줄어들어, 전반적인 시스템의 부하를 줄일 수 있다.

단점

• 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다.
• 인덱스를 관리하기 위해 추가 작업이 필요하다.
• 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.
• 데이터의 변경작업 Insert, Update, Delete가 자주 일어날 경우에는 오히려 성능이 많이 나빠질 수도 있ㄷ.

만약 CREATE, DELETE, UPDATE가 빈번한 속성에 인덱스를 걸게 되면 인덱스의 크기가 비대해져서 성능이 오히려 저하되는 역효과가 발생할 수 있다. 그러한 이유 중 하나는 DELETE와 UPDATE 연산 때문이다. 앞에서 설명한대로, UPDATE와 DELETE는 기존의 인덱스를 삭제하지 않고 '사용하지 않음' 처리를 해준다고 하였다. 만약 어떤 테이블에 UPDATE와 DELETE가 빈번하게 발생된다면 실제 데이터는 10만건이지만 인덱스는 100만 건이 넘어가게 되어, SQL문 처리 시 비대해진 인덱스에 의해 오히려 성능이 떨어지게 될 것이다. 

 

 

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

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

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

 

 

 

 

2. 인덱스(Index)의 종류

---

[ 클러스트형 인덱스 vs 보조 인덱스 ]

# 클러스트형 인덱스

• 클러스트형 인덱스는 영어 사전처럼 책의 내용 자체가 순서대로 정렬되어 있어서 인덱스 자체가 책의 내용과 같은 것을 말한다. (나는 이 말을 이해하기 어려웠다. 이해하기 어렵다면 그냥 넘어가자. 뒤에서 다시 설명을 하기 때문!)
• 클러스트형 인덱스는 테이블당 하나만 생성가능하다. 

 

# 보조 인덱스

• 보조 인덱스는 책의 <찾아보기>가 별도로 있고, <찾아보기>를 찾은 후에 그옆에 표시된 페이지로 가면 실제 찾는 내용이 있는것이다.
• 보조인덱스는 테이블당 여러 개를 생성가능하다.

 

[ 인덱스 자동생성 ]

인덱스는 우선 테이블의 열(컬럼) 단위에 생성된다.

 

# 클러스트형 인덱스

• SQL문이 Primary Key로 지정하면 자동으로 기본키 열에 클러스트형 인덱스가 생성된다.
• 기본키는 테이블당 하나만 생성이 가능하기 때문에 클러스트형 인덱스도 테이블당 하나만 생성이 가능하다.
• Unique Not Null로 지정한 열은 클러스트형 인덱스가 생성된다. 

 

# 보조 인덱스

• SQL문이 Unique를 지정하면 보조 인덱스가 생성된다.
• Unique는 여러 개 생성이 가능하기 때문에 보조 인덱스는 테이블당 여러번 생성이 가능하다.
• Unique or Unique Null로 지저한 열은 보조 인덱스가 생성된다.

 

 

 

3. 인덱스(Index)의 자료구조

---

인덱스를 구현하기 위해서는 여러 가지 자료구조를 사용할 수 있다. 아래에서는 가장 대표적인 해시 테이블과 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)를 저장했던 BTree와 다른 특성을 가지고 있다.

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

데이터베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있다. 이러한 이유로 BTree의 리프노드들을 LinkedList로 연결하여 순차검색을 용이하게 하는 등 BTree를 인덱스에 맞게 최적화하였다. (물론 Best Case에 대해 리프노드까지 가지 않아도 탐색할 수 있는 BTree에 비해 무조건 리프노드까지 가야한다는 단점도 있다.)

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

 

 

 

아래의 그림은 InnoDB에서 사용된 B+Tree의 구조이다.

InnoDB에서의 B+Tree는 일반적인 구조보다 더욱 복잡하게 구현이 되었다. InnoDB에서는 같은 레벨의 노드들끼리는 Linked List가 아닌 Double Linked List로 연결되었으며, 자식 노드들은 Single Linked List로 연결되어 있다.

 

 

 

4. 인덱스의 내부작동

---

[ B+Tree ]

인덱스를 구현하기 위해서는 여러 가지 자료구조를 사용할 수 있다. 아래에서는 가장 대표적인 해시 테이블과 B+Tree에

B-Tree 구조는 데이터를 검색할 때 (SELECT) 뛰어난 성능을 발휘한다.  B-Tree 구조가 아니라면 루트 페이지 및 연결은 존재하지 않고 리프 페이지만 있게 된다. 만약 B-Tree 없이 MMM을 찾게 된다면 AAA-BBB-DDD-FFF-HHH-JJJ-LLL-MMM을 수행한다. 즉, Full Table Search가 일어난다. 

 

반면 B-Tree를 사용한다면 AAA-FFF-LLL-LLL-MMM 5번으로 끝나게 된다. B-Tree의 성능은 데이터가 많을수록 뛰어난 성능을 보인다.

[ 페이지 분할 ]

앞에서 데이터를 검색하는 데는 B-Tree가 효율적임을 확인했다. 이 말은 인덱스를 구성하면 SELECT의 속도가 급격히 향상될 수 있다는 것을 뜻한다.

 

반면, 인덱스를 구성하면 INSERT, UPDATE, DELETE 시에 성능이 나빠지는 단점이 있다. 득히 INSERT 작업이 일어날 때 성능이 급격히 느려질 수 있다. 그 이유는 페이지 분할이 발생하기 때문이다.

 

위 사진에서 III를 삽입 한다면 JJJ가 한칸 아래로 내려가고 III가 삽인된다. 여기까지는 큰 작업이 일어나지 않는다.

여기서 GGG를 입력한다면 큰 작업이 일어나게 된다. 더 이상 두번째 리프페이지에는 빈 공간이 없어 페이지 분할이 일어난다. 이 작업을 이해 한다면 INSERT, UPDATE, DELETE는 작업이 느려지는지 이해할 수 있다.

 

 

 

 

5. 클러스터형 인덱스와 보조 인덱스 구조

---

[ 클러스터형 인덱스 ]

기본키(userID)를 Primary Key로 지정하면 클러스터형 인덱스로 구성된다고 앞에서 설명했다. userID는 오름차순으로 정렬되고 B-Tree 형태의 인덱스가 형성된다. 

앞에서 클러스터형 인덱스는 영어사전과 같다고 했었다. 영어사전은 책 자체가 알파벳 순서의 찾아보기(인덱스)로 구성되어 있기 때문에 찾아보기의 끝(리프 레벨)이 바로 영어 단어(데이터 페이지)이다.

 

클러스터형 인덱스는 루트 페이지와 리프 페이지로 인덱스가 구성되어 있으면 리프페이지는 데이터 그 자체라는 것을 확인할 수 있다. 클러스터형 인덱스는 데이터 검색 속도가 보조 인덱스 보다 거의 빠르다. 클러스터형 인덱스에서 SELECT를 하게 될 경우 루트 페이지와 리프 페이지 한 개씩, 총 2개 페이지를 읽으면된다. 반면 보조 인덱스는 루트 페이지, 리프 페이지, 데이터 페이지 총 3개 페이지를 읽어야 한다.

 

 

 

[ 보조 인덱스 ]

보조 인덱스는 데이터 페이지를 정렬하는 것이 아니므로, 그냥 데이터 페이지 뒤쪽 빈 부분에 삽입된다. 리프 페이지에서도 약간의 위치가 조정될 뿐 페이지 분할은 일어나지 않는다. 즉, 데이터 입력(INSERT)에서는 성능에 주는 부하가 클러스터형 인덱스보다 적다. 

 

 

[ 정리 ]

• 클러스터형 인덱스는 생성 시에는 데이터 페이지 전체가 다시 정렬된다. 따라서 이미 대용량 데이터가 입력된 상태라면 클러스터형 인덱스를 생성하는 것은 심각한 시스템 부하를 줄 수 있다.
• 클러스터형 인덱스는 리프 페이지가 곧 데이터이다. 따라서 인덱스 자체에 데이터가 포함되어 있다고 볼 수도 있다.
• 클러스터형 인덱스는 보조 인덱스보다 검색 속도는 빠르지만 데이터 입력/수정/삭제는 더 느리다.
• 클러스터형 인덱스는 테이블에 한 개만 생성할 수 있다. 또한 어느 열에 클러스터형 인덱스를 생성하는지에 따라서 시스템 성능이 달라질 수 있다. 

 

• 보조 인덱스의 생성시 에는 데이터 페이지는 그냥 둔 상태에서 별도의 페이지에 인덱스를 구성한다.
• 보조 인덱스의 리프 페이지는 데이터가 아니라 데이터가 위치하는 주소값이다.
• 보조 인덱스는 크러스터형 인덱스보다 검색은 느리지만 데이터 입력/수정/삭제는 더 빠르다.
• 보조 인덱스는 여러개 생성할 수 있지만, 남용하는 경우에는 오히려 시스템 성능을 떨어뜨리는 결과를 초래하기 때문에 꼭 필요한 열에만 생성하는 것이 좋다.

 

 

 

 

6. 결론

---

[ 인덱스를 생성해야 하는 경우와 그렇지 않은 경우 ]

인덱스는 잘 사용하면 쿼리의 성능이 급격히 향상되지만 그렇지 않은 경우에는 오히려 쿼리의 성능이 떨어지며 전반적인 MySQL의 성능이 나빠질 수 있다.

1. 인덱스는 열 단위에 생성된다

하나의 열에만 생성되는 것이 아니라 두 개 이상의 열을 조합해서 인덱스를 생성할 수 있다.

 

2. WHERE절에서 사용되는 열에 인덱스를 만들어야 한다.

테이블 조회 시에 인덱스를 사용하는 경우 WHERE절의 조건에 해당 열이 나오는 경우에만 주로 사용된다. WHERE절에 사용되더라도 자주 사용해야 가치가 있다. SELECT문은 가끔사용하고 INSERT작업만 일어나거나 WHERE절에 기본키가 사용되고 클러스터형 인덱스가 사용된다면 클러스터형 인덱스에서 데이터가 입력되는 과정에서 매번 테이블 분할이 일어나 오히려 성능이 떨어진다.

 

3. 데이터의 중복도가 높은 열은 인덱스를 만들어도 별 효율이 없다.

테이블에 셩별(gender) 열 처럼 데이터의 종류가 별로 없다. Male, Female 두 종류 라면 인덱스를 만들고 관리하는 비용이 오히려 더 많이 든다.

 

4. 외래 키를 지정한 열에는 자동으로 외래 키 인덱스가 생성된다.

5. JOIN에 자주 사용되는 열에는 인덱스를 생성해 주는 것이 좋다.

6. INSERT/UPDATE/DELETE가 얼마나 자주 일어나는지를 고려해야 한다.

 

7. 클러스트형 인덱스는 테이블당 하나만 생성할 수 있다.

클러스트형 인덱스는 데이터 페이지를 읽는 수가 최소화 되어서 성능이 아주 우수하므로 조건에서 가장 많이 사용되는 열에 생성하는 것이 바람직하다. 또한 ORDER BY절에 자주 나오는 열도 클러스트형 인덱스가 유리하다. 클러스트형 인덱스의 데이터 페이지는 이미 정렬되어 있기 때문이다.

 

8. 클러스트형 인덱스가 테이블에 아예 없는 것이 좋은 경우도 있다.

CREATE TABLE 나죽나강
( userID CHAR(8) NOT NULL PRIMARY KEY,
  ...

위 같은 상태에서 클러스트형 인덱스가 생성되고 데이터가 입력된다면 정렬이 계속 수행되고 페이지 분할이 끊임없이 일어나 시스템 성능에 문제가 심각해진다.

 

9. 사용하지 않는 인덱스는 제거하자

공간 확보 뿐만 아니라 데이터 입력시에 발생되는 부하도 많이 줄어든다.

 

 

Reference

https://mangkyu.tistory.com/96?category=761304