7. 인덱스

인덱스(Index)

: 추가적인 쓰기 작업과 저장 공간을 활용하여 DB 테이블의 검색 속도를 향상시키기 위한 자료구조

- Index는 데이터의 주소값을 저장하는 별도의 자료구조

- Index를 활용해여 빠르게 원하는 데이터를 찾을 수 있음

DB테이블에 Index가 필요한 이유

- 원하는 데이터를 찾고 싶을 때 테이블 전체를 full scan해야 함

- 시간 복잡도 : O(N)

- 시간이 오래 걸리기 때문에 서비스에 좋지 않은 영향을 끼침

- IF ) Index가 있다면

• 시간복잡도 : O(LogN)
• 조건을 만족하는 튜플들을 빠르게 조회하기 할 수 있음
• 빠르게 정렬하거나 그룹핑하기 위해서 사용

Multi Column Index

- Where 절에서 AND 연산자에 의해서 자주 같이 질의되는 칼럼인 경우 

- Index를 생성할 때 칼럼의 순서에 따라 정렬됨

- 순서에 따라서 성능이 달라질 수 있기 때문에 이를 고려해서 개발해야 함

- 장점 )

• Covering Index
  • 특정 쿼리의 모든 필요한 데이터를 인덱스에서 직접 얻을 수 있게 하는 인덱스
  • 인덱스를 검색한 이후 물리적인 데이터 블록을 읽을 필요가 없음
  • 조회 성능이 빠름
  • 테이블 자체에 접근할 필요없이 인덱스에서 쿼리의 모든 필요한 데이터를 찾을 수 있게 함
  • 인덱스에서 충족하는 데이터를 갖고 있어 디스크 I/O를 줄이고, 테이블 락을 줄임으로써 DB의 전반적인 부하를 감소시켜 성능을 향상시킴

Index 구조

1. Single-Level Ordered Indexes

- 각 엔트리는 <탐색 키, 레코드에 대한 포인터>

- 엔트리들은 탐색 키 값의 오름차순으로 정렬

 

1) Primary Index(기본 인덱스) / sparse index

- 탐색 키 값에 따라 정렬된 데이터 파일에 대해 정의

- 탐색 키가 테이블의 기본키인 인덱스

 

cf) 

Dense Index

: 모든 key, value에 대해 index entry를 줌

- 모든 레코드에 대해 색인을 만듦

 

Sparse Index

: 몇몇 값에 대해서만 entry를 만듦

- 기본적으로 sparse index를 사용함

- primary index도 sparse index임

 

2) Clustering Index(클러스터링 인덱스) / sparse index

: 탐색 키 값에 따라 정렬된 데이터 파일에 대해 정의

- 많은 레코드가 ordering field에 대한 공통된 값을 가질 경우 사용할 수 있음

 

3) Secondary Index(보조 인덱스) / dense index

: 다른 인덱스를 돕는 보조 인덱스이며 레코드가 어디 위치 한가지만 알려주는 역할

- 주키가 아니라 보조 키를 이용하여 추가적인 방법으로 원하는 값을 가져올 수 있음

 

2. Multi-Level Indexes

- 인덱스 자체가 큰 경우 인덱스를 탐색하는 시간도 오래 걸릴 수 있음

- 인덱스 엔트리를 탐색하는 시간을 줄이기 위해서 Single-Level Ordered Indexes를 디스크 상의 하나의 순서 파일로 생각하고, 이것에 대해 다시 인덱스를 정의할 수 있음

- 가장 상위 단계 인덱스를 마스터 인덱스

- 대부분 B+Tree를 사용함

 

동작 방식(자료 구조)

- DB Index에서 자주 쓰이는 자료구조는 B-Tree, B+Tree, Hash Table

 

1. B-Tree

- 시간 복잡도 : O(LogN)

- 자식 노드가 2개 이상인 트리

- 균형 트리로서, 최상위 루트 노드에서 리프 노드까지의 거리가 모두 동일

 

2. B+Tree

- B-Tree를 확장 및 개선한 자료구조

- 데이터의 빠른 접근을 위한 인덱스 역할만 하는 비단말 노드가 분리되어 있음

- 관계형 DB에서 가장 많이 사용함

 

3. Hash Table

- 시간 복잡도 : O(1)

- 단점 )

• 해시는 등호 연산에만 특화되어 있어서 부등호연산이 자주 사용되는 DB검색에는 해시 테이블이 적합하지 않음
• Equality 비교만 가능하고 Range 비교는 불가능
• Multi Colmn Index의 경우, 전체 Attributes에 대한 조회만 가능함
  • EX) 위의 B-Tree 기반의 인덱스에서는 INDEX(team_id, back_number)는 상황에 따라 team_id 컬럼만으로 조회를 할 수 있음
  • Hash Index는 무조건 두 칼럼 모두 사용해서 조회해야 함

Index로 B Tree 계열이 사용되는 이유

- DB는 Secondary Storage에 저장됨

 

cf) Sacondary Storage

- 데이터를 처리하는 속도가 가장 느림

- 디스크 I/O가 많이 발생하면 느림

- 데이터를 저장하는 용량이 가장 큼

- Block 단위로 데이터를 읽고 씀

 

- DB에서 데이터를 조회할 때 Secondary Storage에 최대한 적게 접근하는 것이 성능 면에서 좋음

-> DB의 I/O는 디스크를 통해 물리적인 작업을 거치기 때문

- 또한 Block 단위로 읽고 쓰기 때문에 연관된 데이터를 모아서 저장하면 더 효율적으로 읽고 쓸 수 있음

=> B-Tree 계열을 사용하면 다른 트리보다 데이터를 찾을 때, 탐색 범위를 빠르게 좁힐 수 있음

=> B-Tree 노드는 여러 개의 데이터를 저장할 수 있음

 

Index를 성정할 때 고려해야 하는 사항

• 테이블에 write 작업(INSERT, DELETE, UPDATE)을 할 때 Index도 추가적인 연산이 발생
• 추가적인 저장 공간 차지

=> 불필요한 Index는 만들지 않는 것이 좋음

 

1. Full scan이 성능이 더 좋은 경우

1) 테이블에 데이터가 조금 있을 때

2) 조회하려는 데이터가 테이블의 상당 부분을 차지할 때

- 인덱스는 큰 테이블에서 소량 데이터를 검색할 때 사용됨

- 보통 전체 데이터의 5 ~ 10% 정도로 걸러지는 경우 Index를 사용했을 때, 좋은 효율을 낼 수 있음

- 인덱스를 튜닝하는 것 -> 테이블 엑세스를 줄이는 것

- 인덱스에서 레코드 주소를 이용한 테이블 엑세스는 생각보다 고비용 구조임

- 따라서 읽어야 할 데이터가 일정량을 넘는 순간 테이블 전체를 스캔하는 것보다 느려짐

- 읽어야 할 데이터가 많아지면 인덱스 스캔량도 늘고, 테이블 랜덤 엑세스가 늘어가기 때문

=> 인덱스 손익분기점

- 랜덤 엑세스

: 인덱스를 이용해서 데이터가 있는 주소를 보고, 해당 장소로 이동해서 데이터를 가져오는 것

- 추출할 데이터가 적을 경우에는 필요한 장소에만 이동하면 되기 때문에 효과적

- But, 대부분의 장소를 들린다면 오고 가는 시간이 계속 소요됨

 

- 시퀀셜 엑세스(순차 접근)

: 블록별로 순차적으로 접근

- 오고 가는 시간이 줄어들어 접근 비용이 감소함

 

Index 설정 기준

1. 카디널리티(Cardinality)

• 카디널리티가 높을 수록 인덱스 설정에 좋은 칼럼
• 한 컬럼이 갖고 있는 값의 중복 정도가 낮을 수록 좋음
• 인덱스를 통해 불필요한 데이터의 대부분을 걸러낼 수 있음
• WHERE 절로 걸러낸 데이터가 원본 데이터의 대부분을 차지할 경우, 성능이 떨어질 수 있음

2. 선택도(Selectivity)

• 선택도가 낮을 수록 인덱스 설정에 좋은 컬럼임 -> 일반적으로 5 ~ 10%가 적당
• 선택도가 낮다는 의미는 한 컬럼이 갖고 있는 값 하나로 적은 row가 찾아지는 것을 의미
• 선택도 계산법(전체 레코드 중에서 조건 절에 의해 선택되는 레코드 비율) = 컬럼의 특정 값의 row / 테이블의 총 row * 100

3. 활용도

• 활용도가 높을 수록 인덱스 설정에 좋은 컬럼임

4. 수정 빈도

• 수정 빈도가 낮을 수록 인덱스 설정에 좋은 컬럼임
• 인덱스 설정된 컬럼이 값이 바뀌게 된다면 인덱스도 새로 갱신해주어야 하기 때문

 

 

 

 

 

 

 

 

 

 

Reference

https://liltdevs.tistory.com/194