[DB] 인덱스 index

1. 인덱스란?

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

👉 index는 데이터의 주소값을 저장하는 자료 구조. index를 활용해서 빠르게 원하는 데이터를 찾을 수 있음

• WHERE절에 사용할 컬럼에 대한 효율화라고 볼 수 있음

 

---

 

2. 인덱스의 필요성

 

- table에 index가 걸려 있지 않다면?

SELECT * 
FROM customer 
WHERE first_name = "Jeongyoon";

👉 원하는 데이터를 찾고 싶을 때 table 전체를 full scan 해야 함

 

full scan이란?

• row를 하나씩 모두 확인하는 것을 의미함
• 시간복잡도는 O(N)
• 시간이 오래 걸리기 때문에 서비스에 좋지 않은 영향을 끼침

 

---

 

-table에 index가 걸려 있다면

• 시간복잡도: O(logN) (B-tree based index)
• full scan에 비해 조회 시간이 줄어듦

 

---

 

- index를 쓰는 이유

• 조건을 만족하는 튜플을 빠르게 조회하기 위해서
• 빠르게 정렬(order by)하거나 그룹핑(group by)하기 위해서

 

---

 

3. Multi Column Index

 

- 고려사항

 

Q1. 어떤 경우에 생성해야 할까?

• 👉 WHERE 절에서 AND 연산자에 의해 자주 같이 질의되는 칼럼인 경우
• 예시) WHERE team_id = 105 and back_number = 7
• 만약 team_id에만 index가 걸려있다면 team_id가 105인 데이터 중에서 back_number를 찾는 것은 team_id=105은 데이터 중에서 full scan이므로

 

Q2. 어떻게 정렬될까?

• 👉 index를 생성할 때 칼럼의 순서에 따라 정렬됨
• INDEX(team_id , back_number)라고 하면 team_id  back_number 칼럼 순으로 index가 걸려 있음

 

Q3. WHERE back_number = 7
조건문이 들어오면 성능은 어떨까?

• 👉 현재 multi column index는 우선 team_id를 기준으로 정렬되어 있음
• 👉 성능이 full scan과 같거나 더 좋지 않을 수도 있음
• 👉 back_number만 single column index를 생성하여 조회하거나 인덱스를 타지 않는 방법 有
• 👉 multi column index를 생성할 때 순서에 따라 성능이 달라질 수 있음을 고려해야 함

 

---

 

- 장점: Covering Index

INDEX(team_id, back_number)이 걸려 있을때, 아래와 같은 쿼리가 들어옴

SELECT team_id, back_number 
FROM player 
WHERE team_id = 5;

• 모든 Attribute를 가져오는 것 X
• team_id, back_number 두 가지 정보만 가지고 옴
• 👉 인덱스에서 검색한 이후 물리적인 데이터 블록을 읽을 필요가 없음

 

- 정리

• 조회하는 attribute를 index가 모두 cover할 때 조회 성능이 더 빠름
• 사용되는 쿼리에 맞춰서 적절하게 index를 설정해야 쿼리가 빠르게 처리될 수 있음
• 👉 index의 구조와 동작 방식 이해하는 것이 중요

 

---

 

4. Index 구조

 

- Single-Level Ordered Indexes

• 각 엔트리는 탐색 키, 레코드에 대한 포인터(주소)로 이루어짐
• 엔트리들은 탐색 키 값의 오름차순으로 정렬됨

 

Primary Index
기본 인덱스
sparse index

• 탐색 키가 데이블의 기본 키인 인덱스

Dense index vs Sparse index

• Dense index: 모든 key value에 대해 index entry를 줌 👉 모든 레코드에 대해 색인을 만듦
• Sparse index: 몇몇 값에 대해서만 entry를 만듦. 대부분 기본적으로 이것을 사용함

 

Clustering index
클러스터링 인덱스
sparse index

• 많은 레코드가 ordering field에 대한 공통된 값을 가질 경우 사용할 수 있음
• 영어 사전과 같은 형태(데이터가 순서대로 정렬됨)

 

Secondary index
보조 인덱스 
dense index

• 다른 인덱스를 돕는 보조 인덱스이며 레코드가 어디 위치한지만 알려주는 역할
• 주키가 아니라 보조 키를 이용하여 추가적인 방법으로 원하는 값을 가져올 수 있음
• 일반 책 뒤에 있는 <찾아보기>와 같은 형태

 

---

 

- Multi-level Indexes

• 인덱스 자체가 큰 경우 인덱스를 탐색하는 시간도 오래 걸릴 수 있음
• 인덱스 엔트리를 탐색하는 시간을 줄이기 위해서 Single-Level Ordered Indexes를 디스크 상의 하나의 순서 파일로 생각하고, 이것에 대해 다시 인덱스를 정의할 수 있음
• 가장 상위 단계 인덱스를 마스터 인덱스라고 함
• 대부분은 B+ 트리를 사용함

 

---

 

5. 인덱스 동작 방식 (자료구조)

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

 

- B-tree

• 시간복잡도: O(logN)
• B-Tree란 자식 노드가 2개 이상인 트리
• 균형 트리로서, 최상위 루트 노드에서 리프 노트까지의 거리가 모두 동일함

 

- B+tree

• B+tree는 B-tree를 확장 및 개선한 자료 구조
• 데이터의 빠른 접근을 위한 인덱스 역할만 하는 비단말 노드 not Leaf가 분리되어 있음
• 관계형 DB에서 가장 많이 사용함

 

- Hash Table

• 시간복잡도: O(1)
• B-Tree보다 빠른 결과를 도출할 수 있음

 

Hash Table이 B-Tree보다 빠른데
왜 B-Tree 계열을 사용할까?

• 해시는 등호 연산에만 특화되어 있음. 부등호 연산이 자주 사용되는 DB 검색에는 적합 X
  • equality 비교만 가능하고 range 비교는 불가능함
• multi column index의 경우, 전에 attributes에 대한 조회만 가능함
  • 위의 B-트리 기반의 인덱스에서는 INDEX(team_id, back_number)는 상황에 따라 team_id 칼럼만으로 조회를 할 수 있었음
  • 하지만 hash index는 무조건 두 칼럼 모두 사용해서 조회해야 함

 

---

 

6. 인덱스로 B tree 계열이 사용되는 이유

 

- Secondary storage (SSD or HDD)

• 데이터를 처리하는 속도가 가장 느림
• 디스크 I/O가 많이 발생하면 느림
• 데이터를 저장하는 용량이 가장 큼
• block 단위로 데이터를 읽고 씀
• DB는 여기에 저장됨

 

이진트리, 레드 블랙 트리를 사용하지 않고
B-트리 계열을 사용하는 이유는?

• B-트리 계열을 사용하면 데이터를 찾을 때 다른 트리보다 탐색 범위를 빠르게 좁힐 수 있음
• B-트리 노드는 여러 개의 데이터를 저장할 수 있음(= 여러 개의 자녀 노드를 가질 수 있음)

 

---

 

7. 인덱스를 설정할 때 고려할 사항

 

- 성능 저하

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

 

---

 

- Full scan이 성능이 더 좋은 경우

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

 

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

• 인덱스는 큰 테이블에서 소량 데이터를 검색할 때 사용함. 온라인 트랜잭션 처리 시스템에서는 소량 데이터를 주로 검색하므로 인덱스 튜닝이 무엇보다 중요함
• 전체 데이터의 5~10% 정도로 걸러지는 경우 index를 사용했을 때 좋은 효율을 낼 수 있음
• 전체 데이터의 20%가 넘어가는 경우 오히려 full scan이 빠를 수 있음
• 인덱스 손익분기점
  • Table Full Scan: 시퀀셜 액세스(순차 접근), 멀티 블록 I/O
  • Index Range Scan: 랜덤 액세스, 싱글블록 I/O
• 인덱스를 튜닝한다는 것은 테이블에 액세스를 줄이는 것

 

• 랜덤 액세스
  • 인덱스를 이용해서 데이터가 있는 주소를 보고, 해당 장소로 이동해서 데이터를 가져오는 것
  • 추출할 데이터가 적을 경우 필요한 장소에만 이동하면 되므로 효과적
  • 하지만 대부분의 장소를 들린다면 오고 가는 시간이 계속 소요됨
• 시퀀셜 액세스(순차 접근)
  • 블록별로 순차적으로 접근함
  • 오고가는 시간이 줄어들어 접근비용이 감소

 

---

 

- Index 설정 기준

1) 카디널리티 Cardinality

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

 

2) 선택도 Selectivity

• 선택도가 낮을수록 인덱스 설정에 좋은 칼럼임 5~10%가 적당
• 선택도가 낮다는 것: 한 칼럼이 갖고 있는 값 하나로 적은 row가 찾아지는 것
• 데이터에서 특정 값을 얼마나 잘 선택할 수 있는지에 대한 지표
• 선택도 계산법
  • 전체 레코드 중에서 조건절에 의해 선택되는 레코드 비율
  • 칼럼의 특정 값의 row 수  / 테이블의 총 row 수 * 100

 

3) 활용도

• 활용도가 높을수록 인덱스 설정에 좋은 칼럼
• 해당 컬럼이 실제 작업에서 얼마나 활용되는지에 대한 값
• 수동 쿼리 조회, 로직과 서비스에서 쿼리를 날릴 때 WHERE절에 자주 활용되는지를 판

 

4) 수정 빈도

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

 

---

 

출처

https://github.com/devSquad-study/2023-CS-Study/blob/main/DB/db_index.md

2023-CS-Study/DB/db_index.md at main · devSquad-study/2023-CS-Study

https://yurimkoo.github.io/db/2020/03/14/db-index.html

유림's Blog

https://www.fun-coding.org/post/mysql_advanced5.html#gsc.tab=0

잔재미코딩 온라인 강의 사이트입니다

https://www.brainkart.com/article/Types-of-Single-Level-Ordered-Indexes_11524/

Types of Single-Level Ordered Indexes