인덱스(INDEX)

Btree 추가 해야함

인덱스란

인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다. 즉 데이터베이스의 index는 책의 색인과 같다.

 

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

 

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

 

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

 

장점

테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다.

전반적인 시스템의 부하를 줄일 수 있다.

 

단점

인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다.

인덱스를 관리하기 위해 추가 작업이 필요하다.

인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.

 

인덱스를 잘못 사용하는 경우

CREATE, DELETE, UPDATE가 빈번한 속성에 인덱스를 걸게 되면 인덱스의 크기가 비대해져서 성능이 오히려 저하되는 역효과가 발생할 수 있다.

 

그러한 이유 중 하나는 UPDATE와 DELETE는 기존의 인덱스를 삭제하지 않고 '사용하지 않음' 처리를 하는 것 때문이다. 만약 어떤 테이블에 UPDATE와 DELETE가 빈번하게 발생된다면 실제 데이터는 10만건이지만 인덱스는 100만 건이 넘어가게 되어, SQL문 처리 시 비대해진 인덱스에 의해 오히려 성능이 떨어지게 될 것이다.

 

인덱스를 사용하면 좋은 경우

규모가 작지 않은 테이블

INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼

JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼

데이터의 중복도가 낮은 컬럼

 

인덱스를 구현하기 위해 사용하는 자료구조

 

인덱스의 동작순서

1. Index Table에서 Where에 포함된 값 찾음

2. 해당 값의 테이블 ID(PK)를 가져와서

3. 그 ID로 원본 테이블에서 값을 조회함

 

B+ Tree

DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조

일반적으로 사용되는 알고리즘 이다.

 

B+ Tree의 구성

 

리프 노드: 실제 데이터가 저장되는 노드

논리 노드: 리프노드까지의 경로 역할을 하는 노드

루트 노드: 경로의 출발점 노드

 

B+Tree는 모든 노드에 데이터(Value)를 저장했던 BTree와 다른 특성을 가지고 있다.

- 리프노드(데이터노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스노드)들은 데이터를 위한 인덱스(Key)만을 갖는다.

- 리프노드들은 LinkedList로 연결되어 있다.

- 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.

- 주로 실시간 시스템에서 사용

 

해시

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용하다. 해시 테이블은 Key값을 이용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조이다.

 

해시 테이블 기반의 DB 인덱스의 특징

- 해시 테이블 기반의 DB 인덱스는 (데이터=컬럼의 값, 데이터의 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현하였다.

- 해시 테이블의 시간복잡도는 O(1)이며 매우 빠른 검색을 지원한다.

- 해시가 등호(=) 연산에만 특화되어있는 관계로 DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적이다.

- 위의 특성 때문에 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.

 

bitmap 인덱스

컴퓨터에서 사용하는 최소단위인 비트를 이용하여 컬럼값을 저장하고 이를 이용하여 ROWID를 자동으로 생성하는 인덱스의 한 방법이다.

비트를 직접 관리하므로 저장공간이 크게 감소하고 비트연산을 수행할 수 있다는 이점이 있다.

 

비트맵 인덱스는 B-Tree인덱스가 가지는 문제점을 해결하기 위해서 탄생하였다.

 

B-Tree인덱스의 문제점

B-TREE인덱스에서는 실제 컬럼 값을 인덱스에도 보관하고 있어야 한다는 점이 대용량 데이터를 관리할 때 부담이 된다.

B-TREE인덱스 컬럼값의 분포도가 좋아야 한다는 점

결합인덱스에서 조건을 사용하지 않는 컬럼이나 =조건이 아닌 컬럼이 결합인덱스 중간에 있으면 액세스효율성이 떨어진다는 점

다양한 액세스패턴을 수용하기 위해 많은 인덱스가 필요할 수 있다는 점

NOT이나 NULL을 사용하거나 복잡한 OR조건에서는 인덱스의 성능을 보장받지 못한다는 점

 

저장공간의 낭비

B-Tree Index는 테이블 Column값과 집합 내에서 해당정보의 rowid를 정렬된 형태로 가지는 구조이므로 동일 값에 대해서 물리적 주소가 다른 경우 동일 값을 중복해서 가지고 있어야 함으로 저장공간의 낭비가 발생하게 된다.

또한 테이블 Column값의 길이가 큰 경우 Index의 원시 값을 그대로 가짐으로써 Index의 크기가 증가하게 된다.

 

유연성(Flexibility)의 부족

B-Tree Index에서는 동일한 테이블에 대한 Access시에 두 개 이상의 Index를 병행해서 사용하는 데에 많은 제약사항이 따른다. 그러나 실제 업무 환경에서는 사용자의 요구 사항은 매우 다양하다. 이러한 요구사항을 만족하기 위해서는 테이블의 모든 컬럼의 조합만큼의 B-tree Index를 만들어야 하며, 이렇게 한다고 하면 테이블의 크기보다 오히려 Index의 크기가 더 커지는 기현상을 초래할 수 있다. 또한, 각각의 인덱스를 관리하는 비용이 테이블 자체를 관리하는 비용보다 커질 수 있을 것이다. 따라서 실제 업무에는 거의 적용하기 불가능한 경우라고 할 수 있겠다.

분포도가 좋은 두개의 B-Tree Index가 있을 경우 두개 이상의 인덱스를 동시에 사용하는데 하나만 사용되고 체크조건으로 사용되는 등 두개의 인덱스를 효과적으로 사용하기 위한 제약사항이 있다.

 

 

비트맵 인덱스 구조

인덱스는 키 값에 해당하는 테이블 레코드를 찾아갈 수 있도록 주소 정보를 제공한다.

B*Tree 인덱스는 테이블 레코드를 가리키는 rowed 목록을 키 값과 함께 저장하는 구조이다. 테이블에 100개 레코드가 있으면 인덱스에도 100개의 rowid를 키 값과 함께 저장한다. rowid에는 중복 이 없지만 키에는 중복 이 있을 수 있다.

개념적으로 비트맵 인덱스는 키 값에 중복이 없고, 키 값별로 하나의 비트맵 레코드를 갖는다.

비트맵 상의 각 비트가 하나의 테이블 레코드와 매핑된다. 비트가 1로 설정돼 있으면 상응하는 테이블 레코드가 해당 키 값을 포함하고 있음을 의미한다.

 

key 값의 수가 많은 경우

비트맵 인덱스는 키 값 별로 하나의 레코드를 갖는데, 저장할 키 값의 수가 아주 많을 때는 한 블록에 모두 담지 못한다. 비트맵을 저장하기 위해 두 개 이상 블록이 필요해지면 아래 처럼 B*Tree 인덱스 구조를 사용하며, 값의 수가 많을수록 인덱스 높이도 증가한다

키 값별로 로우 수가 많을 때

한 블록 크기의 비트맵으로 표현할 수 없을 정도로 테이블 로우 수가 많을 때도 두 개 이상 블록이 필요해 진다.

'BLUE' 값 하나에 대한 비트맵을 저장하기 위해 2+1/2 블록만큼의 공간을 필요한다면 아래와 같은 구조로 저장 된다.

한 블록이 단 하나의 비트맵 레코드로 구성될 수 있지만 실제 테스트 해 보면, 한 블록에 적어도 2개 비트맵 레코드가 담기도록 잘라서 저장하는 것을 확인 할 수 있다.

 

비트맵 인덱스 활용

- 비트맵 인덱스는 성별처럼 Distinct Value 개수가 적을 때 저장효율이 매우 좋다. 그런 컬럼이라면 B*Tree 인덱스보다 훨씬 적은 용량을 차지하므로 인덱스가 여러 개 필요한 대용량 테이블에 유용하다.

- 주로 다양한 분석관점(Dimension)을 가진 팩트성 테이블이 여기에 속한다. 반대로 Distinct Value 가 아주 많은 컬럼이면 오히려 B*Tree 인덱스보다 많은 공간을 차지 한다.

- Distinct Value 개수가 적은 컬럼일 때 저장효율이 좋지만 테이블 Random 액세스 발생 측면에서는 B*Tree 인덱스와 똑같기 때문에 그런 컬럼을 비트맵 인덱스로 검색하면 그다지 좋은 성능을 기대하기 어렵다.

- 하나의 비트맵 인덱스 단독으로는 쓰임새가 별로 없지만 여러 비트맵 인덱스를 동시에 사용할 수 있다는 특징 때문에 대용량 데이터 검색 성능을 향상 시키는 데에 큰 효과를 발휘한다.

- 두 개 이상 비트맵을 이용한 Bitwise AND 연산뿐만 아니라 Bitwise OR, Bitwise Not 연산도 가능하다.

 

여기서 ROWID란?

데이터베이스에서 데이터마다의 주소를 의미하는 개념

오브젝트 번호

해당 데이터가 속하는 오브젝트 번호다. 오브젝트별로 유일한 값을 가지고 있다.

 

상대 파일 번호

오라클의 테이블스페이스는 여러 개의 DATAFILE를 생성할 수 있다. 오라클 8i부터는 파일 번호가 10비트이기 때문에 테이블스페이스당 1023개의 DATAFILE을 추가할 수 있다. 여기서 DATAFILE은 해당 테이블스페이스의 상대 파일 번호를 의미하며, 각 데이터별로 유일한 값을 가진다.

 

블록 번호

파일 안에 어느 블록인지를 의미한다.

 

데이터 번호

블록의 HEADER에서 해당 데이터의 위치값을 저장하고 있는 DATA DIRECTORY SLOT을 가르킨다. 오브젝트 번호, 파일번호, 블록 번호가 같으면 데이터 번호는 블록별로 데이터가 저장돼 있는 순서를 뜻한다. 이처럼 ROWID는 해당 데이터의 저장 위치를 가리키는 요소라고 할 수 있다.

 

 

 

참고:

https://mangkyu.tistory.com/96

https://itholic.github.io/database-index/

https://lovefor-you.tistory.com/183

http://wiki.gurubee.net/pages/viewpage.action?pageId=1507452

http://www.gurubee.net/lecture/2927
http://wiki.gurubee.net/pages/viewpage.action?pageId=26740113https://lovefor-you.tistory.com/183