[DB] 인덱스(INDEX)

인덱스(INDEX)란?

데이터베이스 테이블에 대한 검색의 속도를 높여주는 자료 구조

데이터베이스에서 특정 컬럼에 인덱스를 생성하면 해당 컬럼의 데이터들을 정렬하여 컬럽값과 실제 데이터가 저장된 주소를 <키값,주소값> 형태로 저장한다.
책에 있어서 목차,색인 과 같다고 생각하면 된다. 책에서도 목차를 통해서 쉽게 원하는 키워드를 찾을 수 있듯이 데이터 베이스에서도 인덱스를 통해서 원하는 데이터를 빠르게 찾을 수 있다.
→ 데이터 = 내용 , 인덱스 = 목차 , 데이터주소 = 페이지

인덱스의 장단점

<장점>

인덱스에 의해 데이터들이 항상 정렬된 상태를 갖는다.

• where 조건 절 검색이 효율적이다.
• order by에 의한 sort 과정을 피할 수 있다.
• Min, Max의 효율적인 처리가 가능하다.

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

<단점>

• 인덱스를 관리하기 위하여 추가적인 공간(데이터베이스의 약 10%)과 비용이 발생한다.
• select를 제외한 DML에 취약하다.

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

→ 기존의 인덱스를 삭제하지 않고 사용하지 않음 처리를 해서 자료가 비대해져 오히려 성능저하를 일으킴.

인덱스의 자료구조

Hash

해시 인덱스는 검색하고자 하는 값을 입력한 후 그 결과와 Bucket의 내용을 비교하여 해당 데이터 레코드의 위치를 찾을 수 있는 기법이다.
해시 테이블은 키(Key), 해시함수(Hash Function), 해시(Hash), 값(value), 저장소(Bucket, Slot)로 이루어져 있다.

장점

• 검색 방법 중 속도가 가장 빠름
• 각각의 레코드를 비교해 찾는 번거로움을 피할 수 있음.
• 이진 탐색보다 조금 많은 기억 장소를 차지하나 기억 공간이나 속도면에서 우수.
• Overflow 가 없으면 한번에 원하는 레코드에 접근.
• ISAM보다 세 배나 빠른 검색 속도를 지니고 있다.
• 데이타에 대한 입력이나 삭제가 쉽다.
• 검색 시간(retrieval time)이 데이타의 양과 상관없이 일정하게 유지된다

단점

• 연속적인 데이터 검색에는 비효율적이다.
• 디스크 공간이 비효율적으로 사용된다.
• 정형 해슁의 경우, 데이터가 꽉 차서 디스크 공간을 늘리고 재구조화를 하게 되면, O(n)번에 해당하는 디스크 검색을 해야 하므로 시간이 많이 걸리게 된다.
• Collision 현상이 많이 생길 경우 Overflow 처리가 많아지고, 기억 장소가 낭비된다.
• 모든 데이터를 수치 형태로 바꾸어야 한다.
• 적당한 해싱 함수 선정에 문제가 있다.
• 기억 공간 할당 크기를 알 수 없으므로 해쉬표를 위한 기억장소 할당의 어렵다.

B+tree

B-tree를 개선 시킨 tree

leaf 노드를 데이터 엔트리라고 부르며, 그 외의 노드들은 인덱스 엔트리라고 불린다.데이터 엔트리는 <key,rid> 쌍으로 이루어져 있으며 rid는 record id의 약자이며, 실제 데이터 레코드의 주소를 갖고 있다.
데이터 레코드는 디스크에 있는 실제 데이터를 의미하고, 데이터 엔트리는 인덱스에 존재하는 하나의 노드라이다.
인덱스 엔트리는 <key,다음노드의포인터>로 구성되어 있다.

B-tree와의 차이점

• 모든 key, data가 리프노드에 모여있다. B트리는 리프노드가 아닌 각자 key마다 data를 가진다면, B+트리는 리프 노드에 모든 data를 가진다
• 모든 리프노드가 연결리스트의 형태를 띄고 있다. B트리는 옆에있는 리프노드를 검사할 때, 다시 루트노드부터 검사해야 한다면, B+트리는 리프노드에서 선형검사를 수행할 수 있어 시간복잡도가 굉장히 줄어든다.
• B+트리 는 특정 노드를 찾기 위해서는 반드시 leaf node 까지 가야하지만
  B-트리는 루트 노드에서도 찾을 수 있다.

B+tree의 구성 방법
leaf 노드를 어떻게 구성하느냐에 따라 달라진다.

1. leaf노드 = <key,data record>
2. leaf노드 = <key,rid>
3. leaf노드 = <key,list of rid>

1. leaf노드 = <key,data record>
leaf 노드에 데이터 레코드가 직접 들어가 있기 때문에 인덱스파일만 확인해도 데이터를 가져올 수 있다.

2. leaf노드 = <key,rid>
가장 보편적인 b+tree 의 구조
leaf 노드에 rid(record id: 실제 디스크의 어디에 저장되어 있는지 포인터) 가 있어서 rid를 따라가서 원하는 데이터를 가져올 수 있다.

3. leaf노드 = <key,list of rid>
key값에 해당하는 데이터가 여러개 일때 사용한다.

B+tree의 장점

• leaf node를 제외하고 데이터를 저장하지 않기 때문에 메모리를 더 확보할 수 있다.
  하나의 node에 더 많은 포인터를 가질 수 있기 때문에 트리의 높이가 더 낮아지므로 검색 속도를 높일 수 있다. 
• Full scan을 하는 경우 B+Tree는 leaf node에만 데이터가 저장되어 있고, leaf node끼리 linked list로 연결되어 있기 때문에 선형 시간이 소모된다. O(𝑙𝑜𝑔2𝑛)
• 순차 검색에 용이하다.

멀티칼럼 인덱스

멀티 칼럼 인덱스란, 키값이 하나의 필드로 구성되어 있는게 아니라 여러개의 필드로 구성되어 있다는 것이다.
위에서 <key,rid>로 데이터엔트리가 구성된다고 했었는데 여기서 key는 1개의 속성이었다(예를들면, 나이필드)
근데, 나이 필드 뿐만아니라 성별필드도 같이 묶어서 인덱스를 구축할수 있다는 것이다.
이렇게 멀티 칼럼 인덱스를 구축해 놓으면 다음과 같은 질의에 이 인덱스가 도움이 될 수 있다.나이 < 30 AND 성별 = "남자"

ISAM

정적트리구조로 데이터를 추가 삭제 하여도 트리의 구조가 바뀌지 않는다. 페이지가 꽉 차면 오버플로우 페이지를 생성한다.

오버플로우 페이지

ISAM 트리구조에서는 오버플로우 페이지를 생성하는데 오버플로우가 발생 하였을때 삽입,삭제 연산은 B+tree 보다 빠르다.
하지만 오버플로우가 발생 할수록 데이터를 물리적으로 정렬하지 않기 때문에 탐색 연산에서는 느려지게 된다.

인덱스의 종류

Clustered index

책의 페이지를 알고있어서 한번에 펼쳐서 내용을 보는것과 같다.

특징

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

사용하는 곳

• 테이블 데이터가 자주 업데이트 되지 않는 경우
• 항상 정렬 된 방식으로 데이터를 반환해야하는 경우
  → 테이블은 정렬되어있기 때문에 ORDER BY 절을 활용해 모든 테이블 데이터를 스캔하지 않고 원하는 데이터를 조회할 수 있다.
• 읽기 작업이 월등히 많은 경우, 이때 매우 빠르다.

Unclustered index

책의 목차를 보고 페이지를 찾아서 그 페이지로 이동하는것과 같다.

특징

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

사용하는곳

• where절이나 Join 절과 같이 조건문을 활용하여 테이블을 필터링 하고자할 때
  데이터가 자주 업데이트 될 때
• 특정 컬럼이 쿼리에서 자주사용 될 때

참고

https://rebro.kr/167
https://coding-factory.tistory.com/746
https://simsimjae.tistory.com/241
https://velog.io/@emplam27
https://ssoonidev.tistory.com/48
https://junghn.tistory.com/entry/DB-클러스터-인덱스와-넌클러스터-인덱스-개념-총정리