3월 2주차 데이터베이스 - 4.5 인덱스

[Mins00oo]

인덱스

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

DB에서 인덱스가 필요한 이유

예를 들어서, 아래와 같은 데이터가 있다면 age = 20인걸 찾으려면?

성	나이
김씨	15
이씨	30
박씨	25
김씨	20
이씨	10

→ 모든 행을 다 찾아야한다. 그렇다면 데이터가 1억개 정도가 있다면?

→ 1억개의 행을 다 뒤져야한다.

B-트리

💡 인덱스를 실제로 구현하는데 있어 대부분의 데이터베이스들은 트리 형태로 인덱스를 생성해놓는다.

ex) 14라는 key를 찾아야한다면?

1. 루트 노드를 먼저 확인한다
2. 7보다 크고 15보다 작기 때문에 바로 아래로 내려간다
3. 9보다 크고 11보다도 크기 때문에 11의 아래로 내려간다.
4. 14 확인!

• Balanced tree를 사용하는 이유는??

  

  • 왼쪽의 트리처럼 트리가 편향된 경우, 최악의 시간복잡도로 O(N)을 갖지만, 일반적인 트리의 경우 평균 시간복잡도로 O(logN)을 갖게 된다.
  • 트리가 편향되지 않도록 밸런스를 잘 유지한다면 최악의 경우에도 O(logN)의 시간이 보장된다.

인덱스 생성하기

MySQL

• Clustered Index
  • PK옵션으로 만든 컬럼은 자동으로 정렬이 되어 있기에 굳이 만들어줄 필요가 없음 → 클러스터형 인덱스라고도 한다.
  • 테이블당 하나만 가진다.
• Secondary Index
  • 테이블당 여러개 가질 수 있다.
  • PK 이외에 필요한 정렬 기준이 있을 경우 사용한다.

MongoDB

• 도큐먼트를 만들면 자동으로 ObjectId가 형성되며, 기본키로 설정
• 세컨더리도 부가적으로 설정해서 복합 인덱스를 설정할 수 있음

인덱스 최적화 기법

1. 인덱스는 비용

• 읽기 비용이 발생한다.

• 균형 있는 트리를 조절하기 위한 비용도 든다

• 인덱스의 단점

  1. 추가 저장공간이 필요
  2. 인덱스를 관리하기 위한 추가 작업이 필요
  3. 잘못 사용하면 오히려 성능 저하

2. 항상 테스팅해라

• 인덱스 최적화 기법은 서비스에 따라 다르다
• 그렇기에 항상 테스트하는게 중요하다

3. 복합 인덱스는 같음, 다중 값, 카디널리티 순서

• 인덱스를 생성할 때는 순서가 있고, 순서에 따라 성능이 달라진다.