Database

Chapter 5. Index

MoYoungmin 2021. 2. 18. 14:41

1. Index란?

인덱스는 임의의 규칙대로 정렬된 인덱스 테이블을 만들고, 이 테이블을 참조하여 빠른 검색을 제공하는 기법을 말한다.

 

예를 들어, 페이지가 10,000 쪽인 책에서 'Transaction' 키워드를 찾는다고 가정해보자. 처음부터 끝까지 하나하나 비교하며 (Full Scanning) 키워드를 찾는 것은 너무 오래 걸리고, 이런 작업을 자주 반복한다면 효율은 급격히 감소할것이다. 따라서 우리는 키워드를 찾을 때 맨 끝 페이지에 '색인'을 참조하여 원하는 페이지를 찾게된다. 이때, 색인은 보통 'a', 'b', 'c' 등 일련의 순서로 표기하고 'T' 이후에 값들은 탐색할 필요도 없다. 이때 Clustered Index는 알파벳 순으로 책도 정렬된 상태를 말하고, Non-Clustered Index는 알파벳 순이 아닌 원하는 순서대로 책이 뒤죽박죽된 상태를 의미한다.

 

DB도 같은 예이다. 원하는 컬럼에 인덱스를 설정하면, 컬럼 값 기준으로 정렬된 인덱스 테이블이 생성된다. 이후 해당 컬럼에 걸린 데이터를 조회할 때 인덱스 테이블을 참조하여 'Random Access' 한 후, 빠르게 데이터를 조회한다. 물론, 인덱스 테이블은 항상 정렬된 상태를 유지하기 때문에 '조회' 성능은 좋아졌지만 삽입, 삭제, 수정의 경우 인덱스 테이블 정렬 연산이 추가적으로 필요한 단점이 있다. 무엇보다 'Join' 연산을 통해 원하는 값을 추출하는 SQL 특성상 Index의 성능이 굉장히 중요할 때가 많다.  

2. Index를 무작정 많이 사용하는 것이 좋을까?

인덱스를 무작정 많이 사용할 경우 아래와 같은 문제가 발생할 수 있다.

  • 인덱스를 사용하면, 인덱스 테이블을 추가적으로 생성하기 때문에 공간의 낭비가 발생할 수 있다.
  • 인덱스 설정 컬럼을 기준으로 인덱스 테이블을 정렬하기 때문에 Insert, Update, Delete시 데이터가 밀리고, 끌어당기는 등의 추가 연산이 발생할 수 있다. Insert시 실 데이터 이외에 Index Table에 관련 데이터를 추가하는 과정이 생기고, Delete시 Index Table에 존재하는 값을 삭제하지 않고 표시만 남겨, 사용 데이터는 10만건인데 남아있는 데이터는 100만건일 수도 있다.
  • 추가적으로, Clustered Index의 경우 인덱스 테이블 뿐만 아니라, 데이터가 담긴 실제 테이블도 인덱스 컬럼 기준으로(PK) 정렬되어 있어 삽입, 삭제, 업데이트 연산 성능이 저하될 수 있다.

3. Index 설정 기준

무작정 인덱스를 늘리는 것이 아니라, 조회 시 자주 사용되고, 고유한 값 위주로 설정하는 것이 좋다. 이를 위해 ‘Cardinality‘ 값을 이용한다. 즉, Cardinality가 높은 컬럼을 인덱스로 잡는 것이 좋다. 컬럼 값들의 중복도가 낮으면 Cardinality는 높다고 표현한다. 즉, 중복된 값이 적은 컬럼을 인덱스로 선정해야한다.

예를 들어, 남/녀 2가지로 구분되는 성별은 카디널리티 값이 낮기 때문에 인덱스로 만들어봤자 효율이 적다. 하지만 주민번호, 계좌 번호 등은 각각 유일한 값을 가지므로 Cardinality가 높다. 따라서 인덱스를 설정할 경우 효율적으로 데이터를 찾을 수 있다. 보통 테이블당 3-5개의 인덱스 설정을 진행한다.

4. Clustered Index

클러스터란 “여러 개를 하나로 묶는다”는 의미로, Clustered Index는 기준 값이 비슷한 레코드끼리 묶어서 저장한다. 즉, 인덱스 테이블도 설정된 컬럼 값 기준으로 정렬되어 있고, 실제 테이블도 설정된 컬럼 값 기준으로 정렬되어 있다. 이러한 특징으로 테이블 당 하나의 Clustered Index가 가능하고, 데이터 '조회' 특히 '범위 탐색'에서 큰 장점을 가지고 있다. 하지만 데이터 삽입, 삭제, 수정시 데이터가 밀리고 당기는 등의 추가 연산이 발생하는 단점이 있다. SQL은 굉장히 많은 Join(특히 Nested Loop Join)연산이 이루어지고 이때 Index의 효과는 굉장히 큰것으로 알려져있다.

 

예를 들어, 어떤 학생 테이블에서 학번이 '10'으로 시작하는 학생들 찾고싶다고 해보자. 이때 이 테이블은 학번이 PK고, B+Tree로 인덱스가 구현되있다고 해보자. 먼저 B+Tree로 Random Access를 수행한다. 이후에 차례로 데이터를 탐색하면된다. 이때 Non-Clustered Index와 달리 실 데이터 역시 PK로 정렬되있어 현재 기준 다음 학번을 탐색하고 싶어도 보통 같은 Block에 있는 경우가 많아 속도가 빠른 장점이 있다. I/O 연산 횟수를 줄인다.

[그림 1] Clustered Index

5. Non Clustered Index

인덱스 테이블은 설정된 인덱스 컬럼 기준으로 정렬 되있지만, 실제 테이블의 레코드는 PK(Clustered Index)순으로 정렬되있다. 즉, 실제 테이블은 Non-Clustered Index 기준으로 정렬되있지 않다. 따라서 한 테이블에 여러개의 인덱스 설정이 가능하고 범위 검색에 성능이 좋지 않다.

예를 들어, 상품 구입 테이블의 가격 컬럼에 Index가 B+ Tree로 구현되있고, Non-Clustered Index로 설정되있다고 가정해보자. 만약 10,000원에 해당 하는 상품 품목을 알기 위해 B+ Tree로 탐색을 한 후, 접근 해야하는 부분에 Random Access를 수행한다. 당연히 Index 설정 전과 비교할 때 불 필요한 (Full Scanning) I/O 연산이 줄어들어 빠르게 접근할 수 있다. 그런데 10,000원 ~ 20,000원 즉, 범위 검색을 수행한다면 실제 데이터는 뒤죽박죽 섞여 있어 성능이 Clustered Index보다는 느리다. 왜냐하면 정렬된 상태의 다음 값이 같은 Block에 없는 경우가 많아 다른 Block에서 가져오는 횟수가 증가하기 때문이다.

 

[그림 2] Non Clustered Index

※ 참고

Primary Index : 기본 키를 포함하는 인덱스로 키의 순서가 레코드의 순서를 결정한다.

Secondary Index : 기본 인덱스 이외의 인덱스로 키의 순서가 레코드의 순서를 의미하지 않는다.

6. 인덱스 구현 방식

1. B-Tree

  • 각 노드는 Key와 Data로 구성된 Pair들로 구성되고, 노드의 크기는 보통 Block의 크기와 동일하다.
  • 노드 안에 Key값들은 정렬된 상태이며, 자신의 Key 보다 작은것은 왼쪽 혹은 왼쪽 자식에 있고 자신의 Key보다 크면 오른쪽 혹은 오른쪽 자식에 존재한다.
  • 모든 Leaf Node는 동일한 Depth를 갖고 있어 탐색의 성능이 우수하다.

 

예를 들어, 아래 사진에서 '56' Key를 탐색하는 과정을 살펴보자.

  1. Root부터 차례로 탐색한다. '56'은 '30'과 '70' 사이에 존재하여 해당 자식 노드로 이동한다.
  2. '56'은 '40', '50'보다 크니 맨 오른쪽의 자식 노드로 이동한다.
  3. '52', '56'을 차례로 비교하여 탐색을 종료한다.

[그림 3] B Tree

2. B+ Tree

  • B-Tree와 유사하게 노드 안에 Key값들은 정렬된 상태이며, 자신의 Key 보다 작은것은 왼쪽 혹은 왼쪽 자식에 있고 자신의 Key보다 크면 오른쪽 혹은 오른쪽 자식에 존재한다.
  • B-Tree와 유사하게 모든 Leaf 노드는 동인한 Depth를 갖는다.
  • Inner 노드에는 Key만 저장되고, Leaf 노드에 Key와 Data를 함께 저장한다. 또한 Leaf 노드에만 데이터가 저장되어 Leaf Node들을 포인터로 연결하여 B-Tree보다 쉬운 순회가 가능하다. 즉, 범위 탐색 성능이 우수하다.
  • Inner 노드에 Key 값만 저장되므로 B-Tree보다 더 많은 Key 값을 담을 수 있어 키 값 탐색시 Disk를 읽어오는 횟수가 줄어든다. 즉, 트리의 높이가 낮아진다.
  • 물론, Inner 노드, Leaf 노드의 Key 값 중복의 단점은 존재한다.

예를 들어 키 값이 '48'부터'62'까지 탐색한다고 가정해보자. B-Tree와 유사하게 루트부터 차근차근 비교한다. '48'은 '30'과 '70' 키 사이에 존재하여 다음 자식으로 넘어가고 '48'은 '40'과 '50' 사이에 존재하여 다음 노드로 넘어 간후 '48'의 키 값을 찾는다. 이후 키 값 '62'가 넘어가지 않도록 Leaf 노드에서 차례로 순회한다. (Leaf 노드는 끝에서 링크드 리스트로 연결되어 있기 때문)

[그림 4] B+ Tree

구분 B-Tree B+Tree
데이터 저장 리프 노드, 브랜치 노드 모두 데이터 저장 가능 오직 리프 노드에만 데이터 저장 가능
트리의 높이 높음 낮음(한 노드 당 key를 많이 담을 수 있음)
풀 스캔 시 검색 속도 모든 노드 탐색 리프 노드에서 선형 탐색
키 중복 없음 있음(리프 노드에 모든 데이터가 있기 때문)
검색 자주 access 되는 노드를 루트 노드 가까이 배치할 수 있고, 루트 노드에서 가까울 경우, 브랜치 노드에도 데이터가 존재하기 때문에 빠름 리프 노드까지 가야 데이터 존재
링크드 리스트 없음 리프 노드끼리 링크드 리스트로 연결

 

3. Hashing Index

해싱이란 가변 크기의 인풋에서 -> 가공 및 고정된 크기의 제한된 출력 값으로 변환하는 기법을 의미한다. 해시 인덱스는동등 비교 검색에서 상당히 좋은 이점을 갖고있다. B-Tree, B+Tree는 트리를 순회하며 I/O에 대한 연산이 많지만 해싱 인덱스는 Disk의 할일을 CPU에서 처리하여 보다 빠른 특징을 가지고 있다. 검색하고자 하는 값을 주면 Hash Function을 거쳐서 찾고자 하는 키 값이 포함된 버킷을 찾고, 버킷을 통해 해당 레코드의 주소를 알아낸다.

 

하지만 특정 문자로 시작하는 값의 검색, 범위 검색, 정렬된 경과를 가져오는 등 '범위 검색'에서 성능이 급격히 안좋아 현재 DBMS는 인덱스 구현 방식을 B+Tree를 사용하고있다.

 

※ 인덱스 사용시 왜 B+Tree를 사용할까?

hash index는 SELECT의 조건에서 등호[=]연산에는 적합하지만 부등호 연산 [<, >]에서 성능이 좋지 않기 때문이다.

[그림 5] Hashing Index

 

7. 요약

예를 들어 “배달의 민족”같은 서비스는 주로 사용자가 지역별 배달 음식점을 조회하고 검색하는 기능이 메인이기 때문에 인덱스 기능을 잘 사용한다면 DB의 성능을 최적화시킬 수 있다. 반면에 “페이스북”같은 소셜 미디어는 새로운 게시글들이 사용자들에 의해 끊임없이 생성하기 때문에 인덱스 기능을 사용하는 것이 오히려 성능 저하에 원인이 된다.

결론적으로 인덱스는 “검색”에 최적화된 기능이기 때문에 “삽입”, “삭제”, “수정”이 자주 일어나는 비즈니스 로직 혹은 테이블 사용 용도에 따라 신중히 고민해야 한다.