[Database] 1. Index

1. Database Index(DB성능을 높이는 핵심)

 인덱스란 추가적인 쓰기작업과 저장공간을 활용하여 DataBase 테이블의 검색속도를 향상시키기 위한 자료구조이다. 책에서 원하는 내용을 찾을 때 책의 맨 앞 목록을 찾아보는 것과 같은 원리이다. 모든 데이터를 대상으로 검색하면 시간이 오래 걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조를 생성하여 빠르게 조회할 수 있도록 하는 것이다.

데이터 베이스에 있어서 데이터를 검색할 때 성능을 최적화 하기 위한 유용한 도구이다.

 인덱스를 사용하면 데이터 조회(SELECT)뿐만 아니라 수정(UPDATE), 삭제(DELETE)의 성능까지 좋아진다. 각 연산에는 모두 대상에 대한 조회가 선행되야 하기 때문이다.

 

만일 INDEX를 사용하지 않은 컬럼을 조회해야 하는 상황이면 테이블 전체를 탐색하는 Full Scan을 수행하는데 전체를 비교하여 탐색해야 하므로 처리속도가 떨어진다.

-Index

• 읽기 성능을 향상하기 위한 일종의 자료구조
• 테이블과 별도로 저장되며 Index로 설정한 컬럼값이 변경/추가되면 Index도 업데이트가 된다.
• Index에는 B+ -Tree알고리즘이 사용됨
• Primary Key에는 Database가 자동으로 Index 기능을 성정하여 관리함

-Full table scan

• row 값을 순차적으로 scan하며 값을 비교한다.
• 가장 느린 scanning방법이며 많은 자료가 담긴 Disk를 읽기 위한 I/O를 사용하며 자원을 잡아먹음.
• 속도도 느리고 자원도 많이 쓰기 때문에 좋지 않은 방법이다.

1) 관리

 DBMS는 인덱스를 항상 최신의 정렬상태로 유지해야 원하는 값을 빠르게 탐색할 수 잇다. 때문에 컬럼에 INSERT, UPDATE, DELETE가 수행되면 다음과 같은 연산을 추가적으로 해주어야 하며 그에 따른 오버헤드가 발생한다.

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

2) 장점

• 데이터 조회 속도와 성능 향상
• 시스템의 부하를 줄일 수 있음

3) 단점

• DB의 약 10%의 공간을 인덱스를 관리하는데 사용해야함
• 인덱스를 관리하기 위한 오버헤드
• 잘못사용할 경우 오히려 성능이 저하될 수 있음

CREATE, DELETE, UPDATE와 같은 생성, 삭제, 수정이 빈번한 속성에 인덱스를 걸게되면 인덱스의 크기가 매우 커져 성능이 오히려 저하될 수 있다. 그 이유는 DELETE와 UPDATE 연산이 인덱스를 삭제, 수정하지 않고 사용하지 않음 처리를 하기 때문이다. 이런 과정이 반복된다면 실제 데이터에 비해 인덱스가 더 커지며 성능이 오히려 커질 수 있다.

 

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

• 규모가 큰 테이블
• INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
• JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼(조회를 자주하는 컬럼)
• 데이터 중복도가 낮은 컬럼(ex) 성별X, 생년월O 등등..)

 

2. 알고리즘

인덱스를 구현하은 알고리즘은 여러가지가 있는데 가장 대표적인 Hash Table과 B+Tree에 대해서 알아보겠다.

>Hash Table(해시테이블)

Hash Table [출처]https://mangkyu.tistory.com/96

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

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

 하지만 DB인덱스에서 해시 테이블이 사용되는 경우는 제한적이다. 그 이유는 해시가 등호(=)연산에만 특화되어있기 때문이다. 즉, 부등호연산(>,<,<=,>=, LIKE 등)이 사용되는 Query를 할 때 불리하다.

 

B+Tree 구조 [출처]https://mangkyu.tistory.com/96

 > B+Tree 인덱스 알고리즘

 리프노드에 이르기 까지 자식 노드에 대한 포인터가 저장되어 있어 매우 효율적인 알고리즘이다. 

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

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

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

 

인덱스 컬럼은 부등호를 사용한 순차검색 연산이 발생 할 수 있기 때문에 B+Tree는 B-Tree의 리프노드끼리 LinkedList로 연결하여 순차검색을 용이하게 하여 Index에 맞게 최적화 했다. (B-Tree는 Best Case에 경우 리프노드 까지 가지 않아도 되지만 B+Tree는 무조건 리프노드까지 가야하는 단점이 있다.)

 이런 이유로 해시테이블 보다 인덱싱에 더 적합한 자료구조가 된다.

1) 구성

• 루트노드 :  경로의 출발점
• 논리노드 : 리프노드까지의 경로 역할을 하는 노드
• 리프노드 : 실제 데이터가 저장되는 노드

 

 

3. Index 종류

인덱스 기존 DB 테이블과 달리 데이터 중복성을 가질 수 있다. 따라서 다양한 종류의 인덱스가 있다. 인덱스를 사용할 때에는 목적에 따라 적절한 인덱스를 선택하여 사용해야한다.

 

- 키에 따른 분류

• 기본 인덱스 : 기본키를 포함하는 인덱스 ( 키의 순서가 레코드의 순서를 결정함 - 키(인덱스)의 순서대로 저장됨 )
• 보조 인덱스 : 기본인덱스를 제외한 다른 모든 인덱스 ( 키의 순서가 레코드의 순서를 의미하지 않음 )

- 파일 조직에 따른 분류

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

• 클러스터형 인덱스(Clustered Index) 
  • 테이블당 1개씩 허용
  • 물리적으로 행을 재배열
  • PK설정 시 그 칼럼은 자동으로 클러스터드 인덱스가 만들어짐
  • 인덱스 자체의 리프 페이지가 곧 데이터임. 즉, 테이블 자체가 인덱스임.
  • 데이터 입력, 수정, 삭제 시 항상 정렬 상태를 유지
  • 비 클러스터형 인덱스보다 검색속도는 빠르다. 하지만 입력, 수정, 삭제는 느리다.

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

• 넌 클러스터형 인덱스(Noncnlustered Index) 
  • 테이블당 약 240개 인덱스를 만들 수 있다.
  • 레코드 원본은 정렬되지 않고, 인덱스 페이지만 정렬됨
  • 인덱스 자체의 리프 페이지는 데이터가 아니라 데이터가 위치하는 포인터(RIP)이기 때문에 클러스터형보다 검색속도는 더 느리지만 데이터의 입력, 수정, 삭제는 더 빠름.
  • 인덱스를 생성할 때 데이터 페이지는 그냥 둔 상태에서 별도의 인덱스 페이지를 따로 만들기 때문에 용량을 더 차지한다.

쉽게 책에 비유하면

클러스터형은 페이지를 알고 있어 그 페이지를 바로 펴는 것이다.

넌 클러스터형은 목차에서 찾고자 하는 페이지를 찾고 그 페이지로 이동하는 것이다.

테이블 스캔(Full Scan)은 한장씩 넘어가며 확인하는 것

- 데이터 범위에 따른 분류

밀집 인덱스 [출처] https://velog.io/@rlcjf0014/Database-Indexing

• 밀집 인덱스(Dense) 
  • 모든 Search Key마다 레코드가 생긴다. -> 레코드마다 대응되는 인덱스가 있다.
  • 검색을 빠르게 할 수 있지만 인덱스정보를 기록하기 위해 많은 저장공간이 필요하다.
  • 한번의 디스크 검색으로 어떤 레코드던 찾을 수 있다.
  • 키 값들이 정리되어 있어 이진탐색을 사용할 수 있다.

희소 인덱스 [출처] https://velog.io/@rlcjf0014/Database-Indexing

• 희소 인덱스(Spare)
  • 하나의 인덱스가 특정 데이터 블록의 주소를 저장하고 있다.
  • 몇개의 Search key 값을 기록하기 때문에 저장 공간이 덜 필요하고 overhead를 추가하거나 제거할 때 신경쓸 부분이 줄어드는 장점이 있다.
  • 원하는 레코드를 찾아올 때는 값 자체가 아니라 블럭만을 가져오기 때문에 덴스 인덱싱보다 레코드를 찾아오는 부분에서 느리다.
  • 서치 키 값과 같거나 작은 값중 가장 큰 값을 찾아 검색한다.(위 그림에서 20을 Search Key라고 했을 때 10).
  • 값이 정렬되어 있어 이진 탐색이 가능하다.
  • 블록을 찾은 후 레코드를 찾기위해 블록을 탐색한다.

 

 

참조

--- INDEX ---
https://mangkyu.tistory.com/96
https://nesoy.github.io/articles/2017-07/DBIndex
https://brunch.co.kr/@skeks463/25
https://junghn.tistory.com/entry/DB-클러스터-인덱스와-넌클러스터-인덱스-개념-총정리
https://velog.io/@rlcjf0014/Database-Indexing 

 

 

참고 자료

 

https://jojoldu.tistory.com/243(MySql 인덱스 정리 팁)