• https://github.com/guswns3371/backend-interview-question
• https://mangkyu.tistory.com/96
• https://coding-factory.tistory.com/746
• https://myjamong.tistory.com/184

---

Q. 데이터베이스에서 인덱스를 사용하는 이유 및 장단점을 설명하세요

데이터베이스에서 인덱스를 사용하는 이유는 검색 성능을 향상시키기 위함이다.
(검색 성능을 실질적으로 향상시키기 위해서 해당 쿼리가 index를 사용하는지, 카디널리티 또는 selectivity와 같은 요소들이 고려된 인덱스가 생성되어야 한다.)
인덱스를 사용하여 얻을 수 있는 장점으로는 빠른 검색 성능이 있고, 단점으로는 인덱스를 구성하는 비용 (추가, 수정, 삭제 연산시 인덱스를 형성하기 위해 필요한 추가적 연산)이다.
인덱스를 생성할 때 트레이드 오프 관계에 놓여있는 요소들을 종합적으로 고려하여 생성해야 한다.

---

✅ 인덱스란?

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

• 특정 Column에 인덱스를 생성하면 👉 인덱스를 위한 별도의 메모리 공간에 데이터(key)의 물리적 주소(value)와 함께 저장된다.
  • 인덱스를 활용하여 데이터를 조회하면 👉 인덱스에 저장된 데이터의 물리적 주소를 참조하여 데이터를 조회하므로 검색속도가 향상된다.
  • 인덱스를 활용하면 데이터를 조회하는 SELECT 외에도 UPDATE, DELETE의 성능이 함께 향상된다.
    (UPDATE, DELETE 하기 위해서 SELECT를 해야하기 때문)
• 만약 인덱스를 사용하지 않은 Column을 조회할 경우 전체를 탐색 (Full Scan)해야 한다.

📢장점

• 📌테이블 조회 속도 향상

  • 테이블의 데이터들은 인덱스를 기준으로 정렬되어 있기 때문에 조건 검색시 굉장한 장점을 가진다.
    • ✍조건 검색 WHERE 절의 효율성
      • 인덱스를 사용하지 않으면 조건 검색 (WHERE) 시에 풀 테이블 스캔 (Full Table Scan: 레코드의 전체를 조건과 비교)해야 한다.
      • 인덱스를 사용하면 데이터들이 정렬되어 저장되기 때문에 조건 검색시 빠르게 찾을 수 있다.
    • ✍정렬 ORDER BY 절의 효율성
      • 인덱스를 사용하면 ORDER BY에 의한 SORT 과정을 생략할 수 있다.
      • ORDER BY 작업은 1차적으로 메모리에서 정렬을 하고, 메모리보다 큰 작업은 디스크 I/O를 통해 정렬을 하는 무거운 작업이다.
    • ✍MAX, MIN의 효율적 처리
      • MAX 작업시 레코드의 끝 값을 가져오면 되고, MIN 작업시 레코드의 시작 값을 가져오면 된다.
      • 풀 테이블 스캔 과정이 필요 없다.

📢단점

• 📌인덱스 관리(정렬된 상태 유지)를 위한 추가적 작업이 필요하다.

  • 인덱스가 적용된 Column에
    • INSERT 연산을 수행하면 👉 새로운 데이터에 대한 인덱스를 추가 하는 연산이 필요하다.
    • DELETE 연산을 수행하면 👉 삭제하는 데이터의 인덱스를 사용하지 않는 처리가 필요하다.
    • UPDATE 연산을 수행하면 👉 기존 인덱스를 사용하지 않게 처리하고, 갱신된 데이터에 대한 인덱스를 추가하는 처리가 필요하다.

• 📌전체 테이블의 10~15% 이하의 데이터를 처리하는 경우에만 효율적이다.

  • 인덱스를 관리하기 위해 데이터베이스의 약 10%정도의 추가 저장공간이 필요하다.

• 📌인덱스를 잘못 관리하면 오히려 성능이 저하된다.

  • CREATE, DELETE, UPDATE가 빈번한 속성에 인덱스를 걸게 되면 👉 인덱스의 크기가 비대해져서 성능이 오히려 저하된다
  • 인덱스가 적용된 Column에 DELETE, UPDATE 연산을 하면 기존의 인덱스를 삭제하지 않고 사용하지 않음 처리를 해주기 때문에 인덱스 크기가 비대해진다.

📢효율적인 인덱스 생성 전략

• 고유한 값을 많이 가지는 Column(Primary Key)을 인덱스로 사용한다.
• WHERE절에 자주 사용되는Column을 인덱스로 사용한다
• INSERT, DELETE, UPDATE 가 자주 발생하지 않은 Column을 인덱스로 사용한다
• JOIN, WHERE, ORDER BY 에 자주 사용되는 Column을 인덱스로 사용한다
• 데이터 중복도가 낮은 Column을 인덱스로 사용한다

---

✅ 인덱스의 자료구조

인덱스를 구현하기 위한 대표적인 자료구조로 해시 테이블, B+Tree가 있다.

📢해시 테이블 기반의 DB 인덱스

• 해시 테이블 : key, value로 데이터를 저장하는 자료구조이다.

  • 조회의 경우 시간 복잡도가 O(1)으로 빠른 데이터 검색에 유용한 자료구조이다.
  • 해시 테이블 기반의 DB인덱스는 (key = 데이터, value = 데이터의 위치)를 사용하여 구현되어있다.
  • 해시는 =(등호) 연산에만 특화되어있다. 👉 >, <(부등호) 연산이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.
    • 이러한 이유 때문에 B+Tree가 일반적인 DB 인덱스로 사용된다.

📢B+Tree 기반의 DB 인덱스

• B+Tree : 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조이다.

  • 모든 노드에 value를 저장한 BTree와 다른 특성을 가진다.
    • Leaf 노드(데이터 노드) : (key=인덱스, value=데이터)
    • 나머지 노드(인덱스 노드) : (key=데이터를 위한 인덱스, value=null)
    • Leaf 노드(데이터 노드)들은 LinkedList로 연결되어있다.
      • >, <(부등호) 연산을 이용한 순차 검색 연산이 잦으므로 BTree의 Leaf 노드들을 LinkedList로 연결하여 순차 검색에 용이하게 바꾸었다.
    • Leaf 노드(데이터 노드) 와 나머지 노드(인덱스 노드)의 크기가 다를 수 있다.
  • 시간 복잡도는 O(log2N) 이지만 해시 테이블보다 인덱싱에 적합한 자료구조이다.