DB 인덱스(Index)

Index의 필요성

DB Index의 필요성을 위해 Full Table Scan을 알아보겠습니다.

 

Full Table Scan(순차 접근)

• Full Table Scan이란 데이터베이스의 한 릴레이션에서 데이터를 찾거나 재배열하기 위해 데이터가 저장된 목록 중 모든 데이터 요소를 순차적으로 조사하여 원하는 것을 찾아내는 것을 말합니다.

• 이런 순차 접근에 의한 검색은 Tuple의 수가 많아질수록 검색 시간이 매우 오래 걸립니다.

DB는 Index가 설정되어 있지 않으면 Full Table Scan 방식으로 데이터를 찾음으로써 속도가 매우 느려지게 됩니다. 이 문제를 해결하기 위해 DB에서 Index 기능을 제공합니다.

 

Index란?

Index는 RDBMS에서 검색도를 높이기 위해 사용하는 기술입니다.

 

특정 Table의 칼럼을 색인화(파일로 저장) 하여 검색시 해당 Table의 레코드를 Full Table Sacn 하는 게 아니라 색인화 되어있는 Index파일을 검색하여 검색 속도를 빠르게 합니다.

 

해당 테이블의 칼럼의 값과 해당 레코드가 저장된 주소를 Key-Value 쌍으로 Index를 만들어 두고, 이렇게 지정한 칼럼의 값을 주어진 순서로 미리 정렬해서 보관합니다.

 

그렇기 때문에 데이터가 저장될 때마다 값을 항상 정렬해야 하므로 저장 과정이 복잡하고 느리지만, 이미 정렬돼 있어서 아주 빨리 원하는 값을 찾아올 수 있습니다.

 

즉, Index는 INSERT, UPDATE, DELETE 성능을 희생하고, SELECT 성능을 향상시키는 기능입니다. 그렇기 때문에 테이블에 Index를 추가할지 말지는 데이터의 저장 속도를 어디까지 희생할 수 있는지, 읽기 속도를 얼마나 더 빠르게 만들어야 하는지에 따라 결정돼야 합니다.

 

INSERT

• index split 현상이 발생할 수 있습니다.

  • Index split: 인덱스의 페이지들이 하나에서 두 개로 나누어지는 현상

• 기존 페이지에 여유 공간이 없는 상황에서 그 페이지에 새로운 데이터가 입력되는 경우 발생합니다

• 이렇게 되면 기존 페이지의 내용 중 일부를 새 페이지에다가 기록한 후 기존 페이지에 빈 공간을 만들어 새로운 데이터를 추가하게 됩니다.

• 즉, 새로운 페이지를 할당받고 key를 옮기는 복잡한 작업을 수행합니다.

 

DELETE

• 테이블에서 데이터가 delete될 경우: 데이터가 지워지고, 다른 데이터가 그 공간을 사용 가능합니다.

• index에서 데이터가 delete될 경우: 데이터가 지워지지 않고, 사용 안 됨 표시만 해둡니다.

• 즉, 테이블에서 데이터가 1만 건이 있는 경우, 인덱스에는 2만 건의 데이터가 있을 수 있습니다.

 

UPDATE

• 테이블에 update가 발생할 경우 인덱스에서는 delete가 먼저 발생한 후 새로운 작업의 insert가 발생합니다.

• 즉, delete와 insert 두 개의 작업이 인덱스에 동시에 일어나 더 큰 부하를 주게 됩니다.

B-Tree 인덱스

B-Tree 인덱스는 DB의 인덱싱 알고리즘 중 가장 일반적으로 사용되는 알고리즘입니다. 여기서 B는 Binary가 아니고, Balanced를 의미합니다.

B-Tree 인덱스 구조

B-Tree는 최상위에 하나의 루트 노드와 하위의 자식 노드가 붙어 있는 형태입니다.

탐색 순서는 Root -> Branch -> Leaf 순으로 진행되며, 실제 데이터 레코드를 찾아가기 위한 주소 값은 는 Leaf Node가 알고 있습니다.

B-Tree 인덱스 사용에 영향을 미치는 요소

1. 인덱스 키값의 크기

인덱스는 페이지 단위로 관리됩니다. 위 B-Tree 그림에서 각각의 노드를 구분한 기준이 바로 페이지 단위입니다. B-Tree의 자식 노드의 개수는 가변적인 구조로, 페이지의 크기와 키 값의 크기에 따라 결정됩니다.

 

InnoDB의 모든 페이지 크기는 16KB로 고정돼 있습니다. 만약 인덱스의 키가 16byte라고 가정하고 자식 노드 주소가 12byte로 구성된다고 가정해 보겠습니다. 이 경우 하나의 인덱스 페이지에 몇 개의 키를 저장할 수 있을까요?

 

16*1024/(16+12) = 585개 저장할 수 있습니다. 만약 여기서 인덱스 키 값이 32byte로 늘어났다고 가정하면 한 페이지에 인덱스 키를 16*1024(16+12) = 372개 저장할 수 있습니다.

 

만약 SELECT 쿼리가 레코드를 500개 이상 읽어야 한다면 전자는 한 번, 후자는 두 번 이상 디스크로부터 읽어야 하기 때문에, 그만큼 느려진다는 것을 의미합니다.

 

결론적으로 키 값이 커질수록 해당 페이지에 저장할 수 있는 인덱스 개수가 적어지기 때문에, 인덱스 크기가 커질수록 성능 저하가 일어날 수 있습니다.

 

2. 인덱스 칼럼 기준

만약 1개의 칼럼만 인덱스를 걸어야 한다면, 해당 칼럼은중복 수치가 가장 낮은 것으로 잡아야 합니다. 또한, 다중 칼럼으로 인덱스를 잡는다면 중복 수치가 낮은 -> 높은 순으로 구성하는게 좋습니다.

• ex) 중복 수치가 높은 것: 성별, 학년

• ex) 중복 수치가 낮은 것: 주민등록번호, 계좌번호

중복 수치가 낮은 것으로 잡는 이유는 인덱스로 최대한 효율을 뽑아내려면, 해당 인덱스로 많은 부분을 걸러내야 하기 때문입니다.

 

예를 들어 10,000개의 데이터가 있다고 가정해 보겠습니다. 이중 인덱스로 설정한 칼럼의 유니크 값이 10개일 때, 해당 인덱스로 값을 검색하면 1000건(10,000/10)이 일치할 것을 예상할 수 있습니다.

 

만약, 인덱스로 설정한 칼럼의 유니크 값이 1,000개일 때, 해당 인덱스로 값을 검색하면 10건(10,000/1,000)이 일치할 것을 예상할 수 있습니다.

 

이처럼 인덱스에서 유니크한 값의 개수는 인덱스나 쿼리의 효율성에 큰 영향을 미치게 됩니다.

 

참고

• jojoldu.tistory.com/243
• lalwr.blogspot.com/2016/02/db-index.html
• Real MySQL