DB의 인덱스

1. 인덱스란?

• 인덱스는 데이터베이스의 테이블에 대한 검색 속도를 향상시키기 위한 자료구조

• 현실세계로 비유하자면 책에서의 목차 혹은 색인

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

• 인덱스를 활용하면 SELECT 이외에도 UPDATE, DELETE의 성능이 함께 향상됨

  • 해당 연산은 SELECT의 과정이 필요하기 때문
  • 인덱스를 사용하지 않은 컬럼을 조회하는 경우, 테이블의 전체를 탐색하는 Full Scan이 수행됨

• 하지만 반대로 DBMS에서는 인덱스를 항상 최신 정렬 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있음
• 그렇기 때문에 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE가 수행된다면 각각 다음과 같은 연산을 추가적으로 해주어야 하며, 그에 따른 오버헤드가 발생함
  • INSERT : 새로운 데이터에 대한 인덱스를 추가
  • DELETE : 삭제하는 데이터의 인덱스를 사용하지 않는다(제외처리)는 작업을 진행
  • UPDATE : 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대해 인덱스를 추가

2. 인덱스의 장점

• 데이터들이 정렬되어 있다는 점 -> 조건 검색에서 유용

1. 조건 검색 WHERE 절의 효율성
   • 위에서 언급한 Full Scan의 문제의 해결
   • 인덱스는 데이터들이 정렬되어 저장되기 때문에 해당 조건에 맞는 데이터들을 빠르게 찾아낼 수 있음
2. 정렬 ORDER BY 절의 효율성
   • 인덱스로 인해 이미 정렬된 상태이기 때문에 따로 정렬을 수행할 필요가 없음
   • 정렬 자체가 부하가 많이 걸리는 작업인데, 인덱스를 통해서 이러한 자원의 소모를 하지 않을 수 있음
3. MIN, MAX의 효율적인 처리가 가능
   • 정렬되어 있기 때문에, MIN 과 MAX 값을 레코드의 시작 값과 끝 값 한 값 씩만 가져오면 되기 때문에 Full Table Scan으로 테이블을 모두 뒤져서 작업하는 것보다 훨씬 효율적

3. 인덱스의 단점

• 인덱스의 가장 큰 문제점은 정렬된 상태를 계속 유지해야 한다는 점

1. 인덱스는 DML 연산에 취약

• INSERT, UPDATE, DELETE를 통해 데이터가 추가되거나 값이 바뀔 경우 인덱스 테이블 내에 있는 값들을 다시 정렬해야 함
• 또한 인덱스 테이블과 원본 테이블 이렇게 두 군데의 데이터 수정 작업을 해줘야 한다는 단점도 발생
• 그렇기 때문에 DML이 빈번한 테이블보다 검색을 위주로 하는 테이블에 인덱스를 생성하는 것이 좋음

2. 무조건 인덱스 스캔이 좋은 것은 아님

• 위에서 검색을 위주로 하는 테이블에서 인덱스가 좋다고 했지만, 무조건 검색 시에도 인덱스가 좋은 것은 아님
• 인덱스는 테이블 전체 데이터 중 10~15% 이하의 데이터를 처리하는 경우에만 효율적이고 그 이상의 데이터를 처리할 땐 인덱스를 사용하지 않는 것이 더 나음
  • 1개의 데이터가 있는 테이블과 100만개의 데이터가 있는 테이블이 있다고 할 때,
    • 100만개의 경우는 인덱스 스캔이 유리하겠지만
    • 1개의 데이터가 있는 테이블은 풀 스캔이 더 빠를 것

3. 속도 향상을 위해 인덱스를 많이 만드는 것도 좋지 않음

• 인덱스는 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장 공간이 추가로 필요
• 속도 향상과 메모리의 코스트를 비교하여 인덱스를 만들지 말지 정해야 함

4. 인덱스 생성 전략

---

1. 조건절에 자주 등장하는 컬럼 (검색의 조건으로 자주 설정되는 컬럼)
2. 항상 = 으로 비교되는 컬럼
3. 중복되는 데이터가 최소한인 컬럼 (분포도가 좋은 컬럼)
4. ORDER BY 절에서 자주 사용되는 컬럼
5. JOIN 조건으로 자주 사용되는 컬럼

5. 인덱스의 자료 구조

---

• 인덱스를 구현하기 위해서는 다양한 자료구조를 사용할 수 있는데, 대표적으로 해시 테이블과 B+ Tree를 사용

해시 테이블(Hash Table)

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

• DB에서 해시 테이블이 사용되는 경우는 제한적인데, 이유는 해시 테이블이 등호(=) 연산에만 특화되었기 때문

• 해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이 때문에 부등호 연산(>, <) 이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않음

• 이러한 이유로 DB의 인덱스는 B+ Tree가 일반적으로 사용됨

B+ Tree

• 기존의 B- Tree는 모든 데이터를 한 번 순회하는 데는 트리의 모든 노드를 방문해야 하므로 비효율적

( B-Tree 예시 )

• B+ Tree는 DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조

  

( B+ Tree 예시)

• B+ Tree의 특징

  • 리프노드(데이터노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스 노드)들은 데이터를 위한 인덱스(Key)만을 갖는다.
  • 리프노드들은 LinkedList로 연결되어 있음
  • 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 됨

• DB의 인덱스는 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있음

• BTree의 리프노드들을 Linked List로 연결하여 순차 검색을 용이하게 하는 등 BTree를 인덱스에 맞게 최적화

• B+ Tree는 O(log2n)의 시간복잡도를 갖지만 해시 테이블보다 인덱싱에 더욱 적합

---

출처

https://mangkyu.tistory.com/96

https://choicode.tistory.com/27

https://rebro.kr/167