[DB 기초] 5. 인덱스

0. 인덱스(Index)

:: DB에 대한 검색 쿼리 효율 향상을 위해 생성하는 별개의 테이블(자료구조)

:: 대체로 B-트리(Balanced Tree) 또는 해시(Hash) 자료 구조 기반

항목	내용
장점	1. 빠른 검색 2. 정렬 및 집합 연산 최적화(order By / group By / join)
단점	1. 쓰기 성능 저하 2. 추가 자료구조에 의한 저장 공간 증가 3. 불필요한 인덱스 생성 시의 DB성능 저하

---

1. 인덱스의 효율적인 검색 원리

1.1. Sorting을 위한 자료구조(= 순서가 있는 자료구조)

종류	내용
- Array	순차적 접근에 유리하나 삽입과 삭제에서 비효율적
- Linked List	삽입과 삭제가 효율적이나 순차 탐색이 필요해 검색 속도 느림
- Tree 등등	효율적인 검색, 삽입, 삭제가 가능하여 대용량 데이터에서 유리

---

1.2. Binary Search 검색 방법

종류	내용
1. Binary Search	:: 정렬된 데이터를 반으로 나누어 탐색하는 "알고리즘" :: 소거 방식을 통해 효율적으로 데이터 탐색 :: O(log N)의 시간 복잡도
2. Binary Search Tree (BST)	:: Binary Search 검색 방법 + Sorting 나열을 위한 자료구조 :: 이진트리 구조로,  O(log N)의 시간 복잡도 :: 부모 노드 기준, 자식 노드가 작으면 왼쪽 / 크면 오르쪽에 위치

---

출처 : https://youtu.be/bqkcoSm_rCs?si=SF9i60C-ibhf1Zs8 (좌) / (우) : 귀여운 나

 

3. B-Tree

:: B-Tree는 Binary Search Tree(이진 검색 트리)를 확장한 다항 트리(Polynomial Tree) 형태 :: 최소한 2개의 노드를 지님  :: O(log N)의 시간 복잡도로 효율적인 검색, 삽입, 삭제 가능 :: 리프 노드는 같은 높이에 위치하여, 정렬된 키를 기반으로 이진 검색 방식으로 빠른 검색 가능

 

---

출처 : https://www.youtube.com/watch?v=yLe7_3cGSeU

 

4. B+ Tree

:: B+ Tree는 B-Tree를 개선한 자료 구조, 범위 검색 및 순차 검색에 최적화 :: 내부 노드는 키 저장 / 모든 데이터는 리프 노드에 저장 :: 리프 노드는 연결 리스트로 연결되 효율적인 범위 쿼리 / 순차적 접근 가능 :: B+ Tree는 O(log N) 시간 복잡도로 검색, 삽입, 삭제 작업을 처리하며, 디스크 I/O 효율성과 범위 쿼리에 유리

---

5. B-Tree VS B+ Tree

특징	B-Tree	B+Tree
데이터 저장 위치	데이터가 내부 노드와 리프 노드에 저장	데이터는 리프 노드에만 저장
리프 노드 연결	연결 X.	Linked List로 연결
검색 성능	내부 / 리프 노드에서 모두 데이터를 검색	범위 검색에 더 효율적
디스크 효율성	- 모든 노드에 데이터가 저장 - 디스크 I/O가 많을 수 있음	- 내부 노드는 키만 저장 - 실제 데이터는 리프 노드에 저장, I/O가 적음
주요 용도	일반적인 검색 및 데이터 처리	범위 검색과 정렬된 데이터 조회

---

2. 인덱스의 종류

2.1 클러스터형 인덱스(Clustered Index)

항목	내용
정의	:: 데이터 베이스의 물리적 순서를 인덱스의 순서에 맞춰 정렬하는 방식
특징	1. 하나의 테이블에는 하나의 클러스터형 인덱스만 존재 2. 데이터를 인덱스 순서대로 물리적으로 정렬하여 저장 (데이터의 물리적 순서  == 인덱스 순서) 3. 인덱스 페이지가 데이터 페이지를 갖고있기에 Clustered (리프 페이지 = 데이터 페이지)
사용 경우	:: 범위 검색 및 정렬된 데이터를 자주 조회할 경우 유리(검색에 유리, 삽입 / 삭제에는 영.. ) Ex) 고객 ID, 주문 번호 등의 기본키
페이지 특징	- 루트 페이지 :: 어떤 PK가 어떤 리프 페이지에 있는지 - 리프 페이지 / 데이터 페이지 :: 본 데이터(정렬된 데이터 값을 의미)

---

2.2 비클러스터형 인덱스 (Non-Clustered Index / Secondary Index) 

항목	내용
정의	:: 테이블이 물리적으로 정렬되는게 아니라, 별도로 정렬된 인덱스로 간접 정렬 방식
특징	1. 테이블당 여러 개의 인덱스를 만들 수 있으며, 실제 데이터는 인덱스의 포인터를 통해 접근 2. 디스크 공간을 상대적으로 적 사용 3. 인덱스 페이지와 데이터 페이지가 구분되어 있어서 Non-Clustered
사용 경우	:: 특정 값 조회가 빈번한 컬럼에 대해 최적화  (단일 값 조회 / 삽입 / 삭제, 전체 강점, 전체조회 영..) Ex) 고객 ID, 주문 번호 등의 기본키
페이지 특징	- 루트 페이지 :: 어떤 PK가 어떤 리프 페이지에 있는지 - 리프 페이지 :: 어떤 PK가 어떤 데이터 페이지에 있는지(중간에 정렬을 하는) - 데이터 페이지 :: 본 데이터(비정렬, 리프에 의한 포인터로 지정)

---

2.3 클러스터형 인덱스와 비클러스터형 인덱스의 혼합

:: 현실적으로는 하나의 테이블에 클러스터형 인덱스 + 비클러스터형 인덱스인 경우가 많음

:: PK 는 기본적으로 존재(클러스터형 인덱스)하고, 추가로 조회가 자주 발생하는 컬럼에 대해 인덱스 추가하기 때문

출처 : https://hudi.blog

=> 비클러스터형 인덱스로 조건에 맞는 데이터 탐색 후, 클러스터형 인덱스를 통해 데이터 조회가 빠름

---

3. 최적화 고려 사항

3.1 인덱스의 생성 시 고려 사항

- 검색 시간 효율 ↑, 공간 효율 ↓ (트레이드오프)

문제	상세
1. 인덱스가 데이터베이스 용량에 미치는 영향	:: 인덱스 또한 DB용량을 차지함 - 관리 비용과 사용 디스크 공간의 증가 의미 Ex) B-Tree 인덱스는 트리구조 저장되어 여러 인덱스 생성 시, 각각의 인덱스가 DB내에서 별도의 테이블처럼 저장 -> 사용량 증가
2. 재인덱스(Reindex)의 영향	:: DDL / DML에서의 CUD 시, 재인덱스 발생 :: 많은 인데스가 존재할 경우, 재인덱스 시간 증가 :: DDL에서 재인덱스가 걸릴 때, 테이블에 락(lock) -> DML 작업이 실행X :: 전체적인 성능 저하를 불러옴 - 대용량 실시간 서비스에서 치명적

---

3.2 효율적인 인덱스 컬럼 구성 : Cardinality, Selectivity

• 고효율 인덱스
  :: 최대한 많은 데이터가 걸러져 검색 성능이 향상되는 인덱스 - 높은 카디널리티
  :: 필요한 데이터를 포함하는 가장 작은 범위로 탐색 필요 - 좋은 / 높은 선택도 == 여러 컬럼을 조합해 인덱싱 
  :: 만약 인덱스가 반환하는 데이터가 많아지면, Full Scan과 비슷해져 의미X

종류	내용
1) Cardinality (카디널리티)	:: 컬럼 내에서 고유값의 개수, 중복의 정도를 나타냄(SELECT DISTINCT 컬럼 시, 낮은 값) :: 고유값이 많을수록 높고, 중복된 값이 많을수록 낮음 :: 높은 카디널리티를 사용한 검색 필요
2) Selectivity (선택도)	:: 쿼리가 원하는 데이터에 대한 필터링 정도 :: Selectivity = Cardinality / Total Number Of Records :: 쿼리 조건에 맞는 데이터가 매우 적고, 검색된 결과가 정밀하면 좋은 것(1에 가까울수록)  :: 좋은 선택도를 가진 컬럼은 필터링 효과가 뛰어나므로 인덱싱에 유리 :: 여러 컬럼을 조합해 높은 선택도를 구성할 수 있음 - 이때, 높은 카디널리티의 컬럼부터 선택

---

4. 그래서 어케 적용함

4.1 인덱스를 적용하는 절차 : EXPLAIN → Query Plan

[DB] MySQL 인덱스 최적화와 효율적인 활용 방법

 

 

 

알잘딱깔센 참조하기 

4.2 Query Optimization

:: EXPLAIN 을 통해 SCAN 종류 및 비용 계산

:: 간단하게는 Full Table Scan or Index Scan인지에 따른 효율성 판단

:: Index Scan 시, 적합한 인덱스 스캔을 수행하는지 조사 필요

 

=> 이후 작업은 

:: 느린 쿼리의 경우 EXPLAIN 을 통해 Scan 종류들을 분석하여 성능저하의 근거들을 찾아낸 뒤,

1. 필요하다면 특정 컬럼에 대해 인덱스를 생성하거나
2. JOIN 의 순서를 바꾸거나 거꾸로 JOIN 을 없애어 De-normalization 을 하거나
3. Aggregate Table (pre-populating tables) 을 만들거나 등으로 최적화를 진행한다.

---

참조

ASAC 수업자료 

 

 

 

 

 

위의 링크된 자료들..