RDB 성능 이슈 3. INDEX의 원리와 종류

RDB 성능 이슈 #3. INDEX의 원리와 종류

#왜 index를 생성하는데 b-tree를 사용하는가?

데이터에 접근하는 시간복잡도가 O(1)인 hash table이 더 효율적일 것 같은데?

SELECT 질의의 조건에는 등호(<>) 연산도 포함이 된다. hashtable을 사용하게 된다면 = 연산이 아닌 등호 연산의 경우에 문제가 발생한다. 동등 연산(=)에 특화된 hashtable은 데이터베이스의 자료구조로 적합하지 않다. 

#B(alanced)-Tree에 대해서

B-Tree 인덱스는 디스크 I/O를 고려하여 관계형 데이터베이스에서 가장 일반적으로 사용되는 인덱스이다. 이 인덱스도 크기가 커저 보조 기억 장치에 저장되게 되는데 이 또한 디스크 I/O가 발생하게 되는 것이다. 따라서 B-Tree의 깊이를 줄여야 디스크 I/O를 줄일 수 있기 때문에 B-Tree를 사용한다.

Root block을 기준으로 Branch block 들이 존재하며 Branch block들의 depth는 모두 동일하다. 이것은 모든 Leaf block들이 같은 높이에 위치하도록 유지시켜준다. 즉, 데이터를 가진 block에 탐색 시간을 동일하게 유지하는 효과가 있다.

B-tree의 검색 속도는 트리의 깊이에 비례하지만 d의 값은 별로 크지 않다. 왜냐하면 브랜치 블록 노드에 저장하는 key 값의 수를 늘리기 때문이다. 브랜치 블록이 200개이고 깊이가 3인 B-tree에는 200^3 인 800만개의 데이터를 저장할 수 있다.

http://egloos.zum.com/sweeper/v/896423

#B-Tree와 B+-Tree의 차이

B-Tree

Key와 관련된 정보(satellite information)를 key를 포함하는 node에 저장한다. 즉 각 노드에 데이터가 저장되는 것이다. 그렇기 때문에 리프 노드를 읽기 전에 원하는 값을 찾을 수 있고 탐색 시간이 탐색 키 수의 로그에 비례한다.

B+-Tree

B+-Tree는 Key와 관련된 정보(satellite infomation)는 모두 leaf node에 저장되고 internal node(branch block)에는 key와 child pointer만 저장한다. 즉, 인덱스 노드와 데이터가 저장된 리프노드가 분리되어 존재한다. 각각의 Leaf block들은 sorting되어 있으며 내림차순, 오름차순 두 상황에 대비해 서로 연결되어 있어서(Linked List 형태) 임의 접근과 순차접근 모두 성능이 우수하다. 그리고 탐색 시에는 항상 루트노드부터 탐색을 시작한다. 즉 B+-Tree는 기존의 B-Tree에 리프노드 끼리의 연결리스트 구조가 추가된 것이라고 할 수 있다.

#클러스터드 인덱스 vs non  클러스터드 인덱스의 차이를 알자

클러스터(Cluster)란 여러 개를 하나로 묶는다는 의미로 주로 사용되는데, 클러스터드 인덱스도 크게 다르지 않다. 인덱스에서 클러스터드은 비슷한 것들을 묶어서 저장하는 형태로 구현되는데, 이는 주로 비슷한 값들을 동시에 조회하는 경우가 많다는 점에서 착안된 것이다. 여기서 비슷한 값들은 물리적으로 인접한 장소에 저장되어 있는 데이터들을 말한다.

클러스터드 인덱스는 테이블의 프라이머리 키에 대해서만 적용되는 내용이다. 즉 프라이머리 키 값이 비슷한 레코드끼리 묶어서 저장하는 것을 클러스터드 인덱스라고 표현한다. 클러스터드 인덱스에서는 프라이머리 키값에 의해 레코드의 저장 위치가 결정되며 프라이머리 키 값이 변경되면 그 레코드의 물리적인 저장 위치 또한 변경되어야 한다. 그렇기 때문에 프라이머리 키를 신중하게 결정하고 클러스터드 인덱스를 사용해야 한다.

클러스터드 인덱스를 적용할 것인가, non 클러스터드 인덱스를 적용할 것인가의 문제는, 인덱스를 추가하였을 때, 발생하는 선택률에 있다. 조회 결과의 약 30% 정도가 선택되는 경우라면 이 데이터를 클러스터드 인덱스를 적용하고, 3%내외라면 클러스터링 인덱스의 효과가 없으므로 non 클러스터링 인덱스를 적용한다.

주의할 점은 몇 가지가 더 있다.

클러스터드 인덱스는 테이블 당 한 개만 생성할 수 있다. 프라이머리 키에 대해서만 적용되기 때문이다, 이에 반해 non 클러스터드 인덱스는 테이블 당 여러 개를 생성할 수 있다. 그리고 클러스터드 인덱스를 추가하게 되면 물리적으로 행을 재배열하게 된다. 때문에 INSERT, DELETE 연산이 많은 경우에는 부적절할 인덱스가 되겠다.

#결합 인덱스(Composite Index)의 경우

인덱스로 설정하는 필드의 속성이 중요하다. title, author 이 순서로 인덱스를 설정한다면 title을 search하는 경우, index를 생성한 효과를 볼 수 있지만, author만으로 search하는 경우, index를 생성한 것이 소용이 없어진다. 따라서 SELECT 질의를 어떻게 할 것인가가 인덱스를 어떻게 생성할 것인가에 대해 많은 영향을 끼치게 된다.

Tip> 복합 인덱스를 설정할 때, 두 필드를 복합 인덱스로 설정한다고 하면, 두 필드의 데이터 타입이 합친 것의 총 바이트가 3072 byte를 넘지 않아야 한다. 그래야 에러가 발생하지 않는다!

#인덱스 개수와 성능

SELECT 쿼리의 성능을 월등히 향상시키는 INDEX 항상 좋은 것일까?

쿼리문의 성능을 향상시킨다는데, 모든 컬럼에 INDEX를 생성해두면 빨라지지 않을까?

결론부터 말하자면 아니다. 

우선, 첫번째 이유는 INDEX를 생성하게 되면 INSERT, DELETE, UPDATE 쿼리문을 실행할 때 별도의 과정이 추가적으로 발생한다. INSERT의 경우 INDEX에 대한 데이터도 추가해야 하므로 그만큼 성능에 손실이 따른다. DELETE의 경우 INDEX에 존재하는 값은 삭제하지 않고 사용 안한다는 표시로 남게 된다. 즉 row의 수는 그대로인 것이다.

이 작업이 반복되면 어떻게 될까?

실제 데이터는 10만건인데 데이터가 100만건 있는 결과를 낳을 수도 있는 것이다. 이렇게 되면 인덱스는 더 이상 제 역할을 못하게 되는 것이다. UPDATE의 경우는 INSERT의 경우, DELETE의 경우의 문제점을 동시에 수반한다. 이전 데이터가 삭제되고 그 자리에 새 데이터가 들어오는 개념이기 때문이다. 즉 변경 전 데이터는 삭제되지 않고 insert로 인한 split도 발생하게 된다.

하지만 더 중요한 것은 컬럼을 이루고 있는 데이터의 형식에 따라서 인덱스의 성능이 악영향을 미칠 수 있다는 것이다. 즉, 데이터의 형식에 따라 인덱스를 만들면 효율적이고 만들면 비효율적인 데이터의 형식이 존재한다는 것이다.

어떤 경우에 그럴까?

이름, 나이, 성별 세 가지의 필드를 갖고 있는 테이블을 생각해보자. 이름은 온갖 경우의 수가 존재할 것이며 나이는 INT 타입을 갖을 것이고, 성별은 남, 녀 두 가지 경우에 대해서만 데이터가 존재할 것임을 쉽게 예측할 수 있다. 이 경우 어떤 컬럼에 대해서 인덱스를 생성하는 것이 효율적일까? 결론부터 말하자면 이름에 대해서만 인덱스를 생성하면 효율적이다.

왜 성별이나 나이는 인덱스를 생성하면 비효율적일까? 10000레코드에 해당하는 테이블에 대해서 2000 단위로 성별에 인덱스를 생성했다고 가정하자. 값의 range가 적은 성별은 인덱스를 읽고 다시 한 번 디스크 I/O가 발생하기 때문에 그 만큼 비효율적인 것이다.

https://lalwr.blogspot.kr/2016/02/db-index.html

3. end