인덱스(index)란?

인덱스란?

(출처: 데이터베이스 배움터)

• 인덱스는 데이터를 논리적으로 정렬해 검색과 정렬 작업 시 속도를 높이는 데 사용된다.
• 인덱스는 책의 목차와 비슷한다.
  • 예를 들어 책에서 사용된 ‘사용자’라는 문자열이 쓰인 페이지를 모두 찾는다고 가정하면, 일반적인 상황에서는 모든 책의 페이지를 넘겨가면서 ‘사용자’라는 문자열이 쓰인 페이지를 모두 찾아야 하지만, 백과사전과 같은 책에서는 보통 책의 맨 뒷부분에 ‘찾아보기’라는 기능을 제공하기 때문에 특정 단어가 쓰인 페이지를 찾고 싶을 떄 빠르게 찾을 수 있다.

기본 키(PK)는 항상 정렬되어 있어서 빠르게 검색할 수 있지만, 기본 키로 해당 테이블을 조회하지 않을 때는 모든 데이터 검색을 해야 하기 떄문에 효율적이지 않다.
-> 해결책은 인덱스를 사용하는 것이다.

인덱스의 특징

• 인덱스는 검색 성능은 개선해주지만, 삽입, 수정, 석제의 성능은 저하된다.
  -> 삽입, 수정, 삭제 시 DBMS는 인덱스를 동적으로 정렬된 상태로 업데이트해야 하기 떄문이다.
• 인덱스 데이터는 저장 공간은 많이 차지한다.
• 여러 열을 인덱스로 정의할 수 있다.
• 인덱스 데이터는 정렬되어 있다.
  • 그렇기 때문에 삽입, 수정, 삭제 시 인덱스 데이터가 변경되기 때문에 재정렬하는 과정을 거쳐야 한다.
• 보통 인덱스는 B+Tree로 구현된다.

장점	단점
검색 성능을 개선해준다.	삽입, 수정, 삭제 시 성능이 저하된다.

인덱스를 어느 컬럼에 사용하는 것이 좋을까?

• 인덱스는 자주 조회하고, 수정, 삭제, 데이터 중복이 적은 컬럼을 선택하는 것이 좋다.
• 또한 인덱스는 데이터의 양이 많을수록 인덱스 성능 향상이 커진다.
  추가적으로 인덱스는 성능 향상을 위해 사용하기 때문에 인덱스를 남발해서 오히려 성능이 저하되지 않는지, 지속적인 관찰이 필요하다.

데이터 검색 시 hash table의 시간 복잡도느 O(1)이고 B+Tree는 O(logN)으로 더 느린데 왜 Index는 B+Tree로 구현될까?

결론적으로 크게 세 가지의 이유가 있다.

1. 항상 정렬된 상태로 특정 값보다 크고 작은 부등호 연산이 가능하다.
   • 가장 큰 이유는 hash table의 경우 평균적으로 O(1)의 시간 복잡도로 데이터의 조회와 삽입을 할 수 있지만, 우리가 데이터베이스에서 조회 작업을 할 때 ‘=’ 연산자만 사용하지 않고, ‘<=’, “>” 와 같은 연산자도 함께 사용하기 때문에 hash table은 이 경우에 적절하지 않다.
2. 그렇다면 Tree 종류는 다양한데 왜 굳이 B+Tree일까?
   • Red-Black Tree도 가능하지만, 레드 블랙 트리는 이진 트리로 최대 자식을 두 개만 가질 수 있으며, 결국 이는 포인터 참조를 통해 데이터 탐색을 해야하는 경우가
     B+Tree에 비해 훨씬 많기 때문에, 탐색 속도 면에서 B+Tree가 더 유리하다.
3. 마지막으로, 데이터 검색뿐만 아니라 저장, 수정, 삭제에도 항상 O(logN)의 시간 복잡도를 갖기 때문이다.

references

https://ko.wikipedia.org/wiki/레드-블랙_트리
image link
https://helloinyong.tistory.com/296