[DB] Index 색인

1. Index(색인)란?

데이터베이스의 테이블에 대한 검색속도를 향상시켜주는 자료구조

 

• 테이블의 특정 컬럼에 인덱스를 생성
  • → 해당 컬럼의 데이터를 정렬한 후 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장됨
• 해당 테이블의 레코드를 full scan 하지 않음
• 컬럼값과 물리적 주소를 (key, value)의 한쌍으로 저장

💡 책으로 비유

데이터 = 책의 내용 인덱스 = 책의 목차 물리적 주소 = 책의 페이지 번호

2. index의 장단점

❤️ 장점 : 인덱스를 사용하는 이유

데이터들이 정렬되어 있음 → 조건 검색의 영역에서 큰 장점이 됨

(1) 조건 검색 WHERE절의 효율성

⚠️ 기존의 문제점 (인덱스 사용X)

• 테이블 안 레코드는 내부적으로 순서없이 뒤죽박죽
  • → WHERE절에 특정 조건에 맞는 데이터 조회 시 레코드의 처음부터 끝까지 다 읽어 검색조건과 맞는지 비교해야함

✅ 해결책 (인덱스 사용O)

• 인덱스 테이블 스캔 (Index Table Scan)
  • 데이터들이 정렬되어 저장되어 있음
    • → 해당 조건(WHERE)에 맞는 데이터들을 빠르게 찾아낼 수 있음

(2) 정렬 ORDER BY절의 효율성

⚠️ 기존의 문제점 (인덱스 사용X)

• ORDER BY는 정렬과 동시에 1차적으로 메모리에서 정렬이 이루어짐
• 메모리보다 큰 작업이 필요하다면 디스트 I/O도 추가적으로 발생됨

✅ 해결책 (인덱스 사용O)

• ORDER BY에 의한 정렬(sort) 과정을 피할 수 있음
  • 기존 문제와 같은 전반적인 자원의 소모를 피함

(3) MIN, MAX의 효율적인 처리

⚠️ 기존의 문제점 (인덱스 사용X)

• 테이블을 모두 뒤져서 작업

✅ 해결책 (인덱스 사용O)

• MIN, MAX값을 레코드의 시작값과 끝값을 한 개 씩 가져옴

💙 단점

정렬된 상태를 계속 유지시켜줘야함 → 레코드 내에 데이터 값이 바뀌는 부분에 악영향

(1) 인덱스는 DML에 취약 (인덱스 관리를 위한 추가 작업 필요)

• INSERT, UPDATE, DELETE를 통해 데이터가 추가되거나 값이 바뀜
  • → 인덱스 테이블, 원본 테이블 2군데에서 데이터 수정 작업을 해줘야함
  • → 인덱스 테이블 내에 있는 값들을 다시 정렬해야함

💡 인덱스 추가작업 / 테이블과 인덱스 비교

INSERT : 새로운 데이터에 대한 인덱스 추가

• 기존 블록에 여유가 없을 때 새로운 데이터 입력→ 해당 블록의 key값에 대해서 DML이 블로킹됨 (대기이벤트 발생)
• → 새로운 블록 할당, KEY를 옮기는 작업 (많은 양의 Redo가 유발)

DELETE : 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업 수행

• 테이블 : 데이터가 삭제되고 다른 데이터가 그 공간을 사용
• 인덱스 : 데이터가 지워지지 않고 사용 안 됨 표시만 함
  • → 테이블의 데이터 수 ≠ 인덱스의 데이터 수

UPDATE : 기존의 인덱스를 사용하지 않음 처리, 갱신된 데이터에 대한 인덱스 추가

• 테이블 : 업데이트 발생하면 인덱스는 업데이트 불가능
• 인덱스 : DELETE 발생 후 새로운 INSERT 작업
  • → 2배의 작업이 소요됨

(2) index 스캔을 잘못 사용하는 경우 검색 성능 저하

• 인덱스는 전체 데이터 중 10~15% 이하의 데이터를 처리하는 경우에만 효율적
• 그 이상의 데이터를 처리할 땐 인덱스를 사용하지 않는 것이 나음
• 나이나 성별과 같이 값의 range가 적은 컬럼은 인덱스를 읽고나서 다시 많은 데이터를 조회해야하므로 비효율적

(3) 추가 저장 공간이 필요

• 인덱스 관리를 위해서는 데이터베이스의 약 10%에 해당하는 저장공간이 추가로 필요
• 속도향상에 비해 단점의 cost를 만들지 말지 정해야함

3. index를 사용하면 좋은 경우

데이터의 범위가 넓고 중복이 적을수록, 조회가 많거나 정렬된 상태가 유용한 컬럼에 사용하는 것이 좋음

• 규모가 큰 테이블
• INSERT, UPDATE, DELETE 작업이 자주 발생하지 않는 컬럼
• WHERE, ORDER BY, JOIN 등이 자주 사용되는 컬럼
• 데이터의 중복도가 낮은 컬럼
• 항상 =으로 비교되는 컬럼

4. index의 자료구조

1) 해시 테이블

key와 value를 한 쌍으로 데이터를 저장하는 자료구조

• (key,value)로 쌍을 표현, key값을 이용해 대응되는 value값을 구하는 방식
• 평균적으로 **O(1)**의 매우 빠른 시간만에 원하는 데이터를 탐색할 수 있는 구조
• 해시테이블에서 (key, value)=(컬럼의 값, 데이터의 위치)
  • 등호(=)연산에 최적화 되어있으므로 인덱스에서 잘 사용되지 않음
    • 데이터베이스에선 부등호 연산이 자주 사용되는데 해시 테이블 내의 데이터들은 정렬되어 있지 않음
    • → 특정 기준보다 크거나 작은 값을 빠른 시간 내에 찾을 수 없음

2) B+ Tree

오직 leaf node에만 데이터를 저장하고 leaf node가 아닌 node에서는 자식포인터만 저장 leaf node끼리는 연결리스트로 연결되어있음

• leaf node에만 데이터 저장되므로 중간 node에서 key를 올바르게 찾아가기위해 key가 중복 될 수 있음

(1) 장점

1. leaf node를 제외하고 데이터를 저장하므로 메모리를 더 확보할 수 있음
   • 하나의 node에 더 많은 포인터를 가질 수 있으므로 트리의 높이가 낮아져 검색속도를 높일 수 있음
2. Full scan을 하는 경우 선형 시간이 소모됨
   • leaf node에만 데이터가 저장되어있고 leaf node끼리 연결리스트로 연결되어있으므로

(2) 단점

• 특정 key에 접근하기위해 반드시 leaf node까지 가야함

(3) 사용하는 이유

• 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생
  • → B+ tree의 연결리스트를 이용하면 순차 검색을 효율적으로 가능

 

---

출처

https://rebro.kr/167

[DB] 11. 인덱스(Index) - (1) 개념, 장단점, B+Tree 등

https://coding-factory.tistory.com/746

[DB] 데이터베이스 인덱스(Index) 란 무엇인가?

 

https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/

해싱, 해시함수, 해시테이블 · ratsgo's blog