Clustered Index와 Secondary Index

Index란?

Index란, 테이블에 대한 동작속도를 높여주는 자료구조이다.

 

조금 더 자세히 설명하자면, Disk에서 발생하는 I/O 시간은 Main Memery에서 발생하는 I/O에 비해 매우 크다. 따라서, DB를 통해 데이터를 검색시 Disk I/O가 빈번히 일어나지 않도록 하는 것이 유리할 것 같다. 이를 위해 Index를 사용한다. Index를 통해 Disk I/O의 횟수를 최대한 줄여 DB의 성능을 높일 수 있는 것이다. 따라서, Index는 DB에서 뿐만 아니라, random access를 할 때 사용하면 적합하다.

 

아래 그림은 id=106번 학생을 검색하는 과정이다. Disk I/O에 비해, block 내의 탐색 시간은 매우 적게 걸리므로 일단 무시한다. 순서대로 정렬되어 있는 key인 경우, 이진탐색을 한다면 꽤 빠를 것이다.  

• Index를 이용한다면,
  [index block1 -> (index block2) -> data block3-> 2 번째 레코드] 이렇게 탐색하게 되면 총 I/O는 2~3번 일어난다. 다른 레코드를 검색한다고 해도 총 2~3번이 보장될 것이다. 
• index를 이용하지 않으면,
  최선의 경우 바로 data block3에 random access 하게 되어 1번의 I/O만으로 id=106을 검색성공 하겠지만, 최악의 경우는 data block1, data block2, ... data block N 이렇게 모든 N개의 disk block을 scan 해야 할 수도 있다. 

 

그림1. Index를 통해 data를 검색하는 과정 예

Index는 data와 별개로 저장된다. data 파일 레코드를 저장하는 것에 비해 공간을 덜 차지해 하나의 디스크 블록에 더 많은 데이터가 담길 수 있어서 한 번의 I/O 발생시, Index는 데이터 파일 레코드에 비해 더 많은 데이터를 읽을 수 있다. 따라서, index block에 데이터가 더 많이 저장되기 때문에 index를 fully scan 하는 것이 data를 fully scan 하는 것 보다 부담이 덜하다. 

 

Index를 통해 data를 검색을 하는 것은 Index가 없는 것 보다 시간이 적게 걸리겠지만 새로운 data를 insert 하는 경우는 index 와 data를 순차적으로 정렬해야 하는 경우가 발생할 수도 있기 때문에 좋은 성능을 내지 못 할 수가 있어서 항상 Index를 사용하는 것은 올바르지 않다. 또한, Index는 Clustered Index와 Secondary Index로 보통 종류가 나뉘는데 둘의 특징을 잘 구분해서 사용해야 더 좋은 성능을 낼 수 있을 것이다.

 

Spatial Index(Spatial Index는 R-Tree)를 제외하고는 보통 B-Tree로 구현된다. B-Tree로 구현되기 때문에 Binary Tree에 비해 child가 많아 Block 단위로 I/O가 일어날 수 있도록 구현한다면 I/O를 최소화 할 수 있어 Binary Tree에 비해 유리한 것 같다. Memory DB의 경우 Index로써 Hash Table로 구현되는 경우도 있다. 이 경우 access time은 B-Tree보다 빠르겠지만 크기를 비교하는데는 사용할 수 없다. 

 

Index에 대해 다룰 주제는 많겠지만 오늘은 Clustered Index와 Non Clustered Index의 탐색 방법에 초점을 맞춰서 차이점을 비교해 보고자 한다.  

Clustered Index

특징

• InnoDB 엔진에서 table의 Primary Key를 정의하면 Clustered Index가 된다. 
• 테이블당 하나만 가질 수 있다.
• Insert시 data가 정렬되고 index는 data block의 첫 번째 레코드의 주소값을 갖게 된다. index가 곧 바로 data block에 접근해서 Secondary Index보다 동작이 빠른 편이다.
• data가 정렬되어 저장되므로, Secondary Index에 비해 범위로 질의를 하는 것에 유리하다. 빈번한 I/O가 덜 발생할 것이기 때문이다. 

사실 위에서 나타낸 그림이 Clustered Index 이다. 그림을 보면 알겠지만 id=106인 Brian을 찾기 위해 우선 index block을 scan(1~2번의 I/O 발생) 하고, data block3번 에서(1번의 I/O 발생) id=106 Brian을 총 2~3번의 I/O로 찾을 수 있다.  

 

범위로 검색하는 경우를 보자. 만약 id=101~104번의 학생을 fetch 한다고 생각해보자. 그러면, index block을 scan 한 후(1~2번의 I/O 발생) data block1를 가져오고(I/O 1번 발생), data block2(I/O 1번 발생)를 가져오면 범위 검색을 할 수 있다. 총 3~4번의 I/O가 발생하게 된다. 

 

그림 2. Clustered Index

Secondary Index

특징

• Primary Key 이외에 필요한 정렬 기준이 있을 경우 사용한다. 
• 테이블당 여러 개 가질 수 있다.
• data record가 정렬되어 있지 않다. 
• index가 data record의 모든 주소값을 가지고 있어야 한다. 
• unique 하지 않아도 된다. 
• 데이터 레코드가 index 순서대로 정렬 되어 있지 않기 때문에 범위 조건으로 검색하게 되면 많은 I/O가 발생할 수 있다. 그러면 좋은 성능을 내지 못 할 것이다. 
• index는 모든 레코드에 대한 색인 데이터를 들고 있어야 하고 정렬된다. 따라서, update, delete, insert시 오래 걸릴 수 있고, clustered index에 비해 더 많은 공간을 차지하게 된다. 

학생의 경우 id는 Primary Key로써 clustered index가 되지만 name으로 검색 조건을 더 빠르게 하고 싶을 수 있다. 이런 경우 Secondary Index를 사용한다. 아래 그림이 그 예이다. 

 

name이 Jane인 학생을 찾는 과정은 id=105로 Jane을 찾는 것과 비슷하다. 하지만 ASCII Code, 알파벳 순서대로 Bill~James의 범위의 레코드를 가져오려면 index block1로부터 data block1, data block2, data block3, data block4를 모두 읽어야 하므로 그림상 I/O가 5~6번 정도 발생할 것임이 보인다. 이처럼 범위로 데이터를 검색하는 경우는 clustered index에 비해 불리하고, 모든 data의 entry에 대해 색인을 갖고 있어야 해서 더 많은 공간을 차지하게 된다.   

 

그림 3. Secondary Index 

 

결론

index에 대해 간략히 알아봤고, 그 중 clustered index, secondary index의 차이와 동작방식에 대해 조금 정리를 해 보았다. 아직 실제로 인덱스로 DB를 튜닝해본 경험이 거의 없지만 나중에 실제로 튜닝해보면서 성능이 얼마나 차이가 나는지 실험하여 내용을 추가하면 좋을 것 같다.