인덱스에 대하여! -쉬움

데이터베이스에서는 테이블의 검색 속도를 향상 시키기 위해 인덱스라는 개념을 사용한다.

 

우리가 DB(Database)에 데이터를 저장해 놓고 원하는 데이터를 뽑아내기 위해 쿼리를 사용하여 

저장된 자료를 추출하는데 데이터가 많아질수록 이 쿼리를 사용하여 테이블 내 레코드를

스캔하여 찾는 것(full scan)이 느려진다. 따라서 우리가 책에서 필요한 부분을 쉽게 찾기 위해

색인이 있는 것처럼, 데이터베이스에도 이러한 색인(index)를 만들어 빠르게 찾도록 도울 수

있다.

 

이해를 돕기 위해

책 권이 있다고 생각하자

 

1. 인사말

2. 인트로

3. 인트로

.

.

.

501. 제 1막 사랑에 대하여

502. 제 1막 사랑에 대하여

503. 제 1막 사랑에 대하여

.

.

.

2032. 제 3막 절정

2033. 제 3막 절정

2034. 제 3막 절정

.

.

.

10002 에필로그

10003 에필로그

10004 에필로그

 

의 책이 있다고 생각해보자

총 페이지가 10004 페이지 인것을 확인 할 수 있는데 만약 우리가 색인 없이

제 3막의 시작을 찾으려고 했다면 우리는 처음부터 2032페이지 까지를 모두 읽어봐야 알수 있을

것이다. 이것이 DB에서 Full Scan한다고 한다.

그러나 우리가 색인이 있다면 색인만 보고 2032페이지 부터 시작이라는 것을 알수 있을 것이다.

그래서 데이터가 많아지면 인덱스가 필요하다.

 

그러나 인덱스에는 장점만 있는 것이 아니다.

일단 인덱스를 관리하는 법을 알아보자.

인덱스= 색인이 있고 책이 존재한다. 그리고 책 내용이 계속 바뀔 수 있다고 가정해보자.

만약 책의 내용이 추가되거나 삭제되면 인덱스도 추가되거나 삭제되어야 한다.

그래서 

• INSERT: 새로운 데이터에 대한 인덱스를 추가함
• DELETE: 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행함
• UPDATE: 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대해 인덱스를 추가함

인덱스를 사용하기 위해선 위의 과정들이 필요하다.

즉 DB에서 데이터를 조회하기 위한 처리만 필요한 것이 아니라 인덱스를 관리하기 위한

처리도 필요한 것이다.

따라서 부가적인 작업이 필요하고 리소스가 필요하다.

인덱스를 안 썼을 때는 필요하지 않았을 작업들 말이다.

 

따라서 인덱스는 장단점을 가진다.

 

장점

• 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다.
• 전반적인 시스템의 부하를 줄일 수 있다.

단점

• 인덱스를 관리하기 위해 따로 저장공간이 필요하다.
• 인덱스를 관리하기 위해 추가 작업이 필요하다.
• 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.

책을 생각해보더라도 색인이 추가된다면 몇페이지라 할지라도 책이 조금 더 두꺼워 질수밖에 없다

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

또한 책 내용이 바뀔경우 인덱스 페이지를 수정해야 하는 일이 발생한다.

1. 만약 책이 10페이지 밖에 안되는 얇은 책이거나

2. 100페이지 중 50페이지 이상이 비슷하거나 같은 내용 일 경우

3. 책의 내용이 삭제되었지만 아예 빠지는 게 아니라 삭선처리만 되었을 경우

등등

 

인덱스를 사용하는 것보다 안 사용하는 것이 효율이 더 높을 수도 있다.

 

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

• 규모가 작지 않은 테이블
• INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
• JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼
• 데이터의 중복도가 낮은 컬럼 (고유한 값 위주로)
• 기타 등등

 

따라서 여기서 카디널리티라는 개념이 나오는데

카디널리티(cardinality)란? 중복도가 '낮으면' 카디널리티가 '높다'고 표현한다. 중복도가 '높으면' 카디널리티가 '낮다'고 표현한다. 

즉 인덱스는 카디널리티가 높을수록 효과가 좋다.

 

주의* 여기서 부터 컬럼, 시간복잡도, 노드, Linked List의 단어가 나올 수 있음

모르는 단어라면 찾아보고 오길 추천 *

 

인덱스의 자료구조

인덱스의 자료구조는 대표적으로 해시테이블과 B+Tree가 있다.

 

해시 테이블(Hash Table)

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

해시 테이블 기반의 DB 인덱스는 (데이터=컬럼의 값, 데이터의 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현하였다. 해시 테이블의 시간복잡도는 O(1)이며 매우 빠른 검색을 지원한다.

하지만 DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적인데, 그러한 이유는 해시가 등호(=) 연산에만 특화되었기 때문이다. 해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이러한 특성에 의해 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.

즉, 예를 들면 "나는"으로 시작하는 모든 데이터를 검색하기 위한 쿼리문은 인덱스의 혜택을 전혀 받지 못하게 된다. 이러한 이유로 데이터베이스의 인덱스에서는 B+Tree가 일반적으로 사용된다.

B+Tree 

B+Tree는 DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조이다. B+Tree는 모든 노드에 데이터(Value)를 저장했던 BTree와 다른 특성을 가지고 있다.

• 리프노드(데이터노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스노드)들은 데이터를 위한 인덱스(Key)만을 갖는다.
• 리프노드들은 LinkedList로 연결되어 있다.
• 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.

데이터베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있다. 이러한 이유로 BTree의 리프노드들을 LinkedList로 연결하여 순차검색을 용이하게 하는 등 BTree를 인덱스에 맞게 최적화하였다. (물론 Best Case에 대해 리프노드까지 가지 않아도 탐색할 수 있는 BTree에 비해 무조건 리프노드까지 가야한다는 단점도 있다.)

이러한 이유로 비록 B+Tree는 O(log2nlog2n) 의 시간복잡도를 갖지만 해시테이블보다 인덱싱에 더욱 적합한 자료구조가 되었다.

B+ Tree는 B-Tree를 업그래이드 시켜서 +일까?

B+Tree는 Balanced Tree이다. 즉 균형이 잡혀있다는 뜻이다.

이런식으로 Binary Tree인 이진트리는 한쪽으로 치우침이 발생할 수 있다.

그러면 DB에서 데이터를 찾는 효율적인 부분에서 일관성이 떨어질 수가 있기 때문에

우리는 균형이 잡혀 양쪽이 균등한 나무의 잎사귀 모양을 한 B-Tree를 개선해 인덱스 개념이

들어간  B+Tree를 인덱스에서 사용한다.

 

즉

Binary Tree : 이진트리

B-Tree : 이진트리를 기본으로 하되 균현을 갖춘 트리

B+Tree : B-Tree 을 개선해 리프노드에만 값을 가지고 인덱스노드에는 인덱스 키만 가지는 트리

정도로 요약할 수 있겠다. 

 

 

Primary Index (클러스터링 인덱스)

 

순차적으로 정렬된 파일에서 검색 키가 파일의 순차 순서를 지정하는 인덱스

클러스트형 인덱스를 구성하려면 행 데이터를 해당 열로 정렬한 후에 루트 페이지를 만들게 된다. 즉 데이터 페이지는 리프 노드와 같은 것을 확인할 수 있다.

 

• 테이블당 1개씩만 허용된다.
• 물리적으로 행을 재배열한다.
• PK설정 시 그 칼럼은 자동으로 클러스터드 인덱스가 만들어진다.
• 인덱스 자체의 리프 페이지가 곧 데이터이다. 즉 테이블 자체가 인덱스이다. (따로 인덱스 페이지를 만들지 않는다.)
• 데이터 입력, 수정, 삭제 시 항상 정렬 상태를 유지한다.
• 비 클러스형 인덱스보다 검색 속도는 더 빠르다. 하지만 데이터의 입력. 수정, 삭제는 느리다.
• 30% 이내에서 사용해야 좋은 선택도를 가진다.

 

Secondary Index(넌 클러스터링 인덱스)

 

검색 키가 파일의 순차 순서와 다른 순서를 지정하는 인덱스

넌 클러스트형 인덱스는 데이터 페이지를 건들지 않고 , 별도의 장소에 인덱스 페이지를 생성합니다. 우선 인덱스 페이지의 리프 페이지에 인덱스로 구성한 열을 정렬하고 데이터 위치 포인터를 생성한다. 데이터의 위치 포인트는 클러스터형 인덱스와 달리 '페이지 번호 + #오프셋'이 기록되어 바로 데이터 위치를 가리킨다. indexTest2로 예를 들면 102번 페이지의 두 번째(#2)에 데이터가 있다고 기록하게 된다. 그러므로 이 데이터 위치 포인터는 데이터가 위치한 고유한 값이 된다

 

• 테이블당 약 240개의 인덱스를 만들 수 있다.
• 인덱스 페이지는 로그파일에 저장된다.
• 레코드의 원본은 정렬되지 않고, 인덱스 페이지만 정렬된다.
• 인덱스 자체의 리프 페이지는 데이터가 아니라 데이터가 위치하는 포인터(RID)이기 때문에 클러스터형보다 검색 속도는 더 느리지만 데이터의 입력, 수정, 삭제는 더 빠르다.
• 인덱스를 생성할 때 데이터 페이지는 그냥 둔 상태에서 별도의 인덱스 페이지를 따로 만들기 때문에 용량을 더 차지한다
• 3% 이내에서 사용해야 좋은 선택도를 가진다.

출처:

https://junghn.tistory.com/entry/DB-클러스터-인덱스와-넌클러스터-인덱스-개념-총정리

 

(이 부분은 말들이 달라서 삭제)

레코드 사이에 정렬되지 않은 키를 기반으로 데이터를 조회사는 경우 동일한 블록에 있는 인덱스 항목 사이의 레코드에는 의존할 수없음으로 각 특정 레코드에 대해 인덱스 항목이 필요하고 그래서 Dense 인덱스여야 한다.

보조 인덱스는 필요에 따라 Dense나 Sparse 인덱스일 수 있다.

 

Dense Index(조밀한 인덱스)

한 index에 원하는 record가 바로 매칭된다.

 

색인 레코드는 파일의 모든 검색 키 값에 대해 나타납니다.

저장공간을 많이 사용한다.

 

 

Sparse Index(희소 인덱스)

index에 data block이 매칭된다.

 

일부 검색 키 값에 대한 색인 레코드만 포함합니다.

Dense보다 저장공간이 덜 필요하지만 느릴 수 있다.

• 느슨한 인덱스
• block 속에서 진짜 자기가 원하는 값을 찾아야 한다.
• data를 fragnation이 일어나지 않고, 효율성을 높이기 위해서 블록 단위로 놓는 것이다.

Composite Index

결합 인덱스란 인덱스를 생성할 때 두 개 이상의 컬럼을 합쳐서 인덱스를 만드는 것을 말한다.

인덱스 테이블은 메인 메모리에 저장되고 메인 메모리는 크기가 작고, 희소 인덱스도 크기가 크므로 보조 인덱스를 구축해야 한다.

보조 인덱스는 인덱스를 다단계로 관리한다.

Indexing, Dense primary, Sparse, Clustered and secondary index in DBMS | T4Tutorials.com

 

[면접 대비] 데이터베이스 - 인덱스

[db index 1편] index 란? (single level index, dense index, sparse index, composite index, multilevel index )

 

[Database] 인덱스(index)란?

 

[데이터베이스] 클러스터 인덱스와 넌클러스터 인덱스/ 개념 총정리