🎯 Index?

Index는 데이터베이스의 테이블에 대한 검색 속도를 향상시켜주는 자료구조이다.
Index는 책에서 목차라고 생각하면 편하며 테이블에서 컬럼의 값과 물리적 주소를 한 쌍으로 저장한다.
주로 큐모가 큰 테이블이나, CUD작업이 자주 발생하지 않고, where,orderby,join등이 자주 사용되는 컬럼에서 사용된다.

장점과 단점

• 장점
  • 테이블을 검색하는 속도와 성능이 향상된다.
  • 시스템 전반적인 부하를 줄일 수 있다.
  • 인덱스에 의해 데이터들이 정렬된 형태를 갖는다.
• 단점
  • 인덱스를 관리하기 위한 추가 작업들이 필요하다.
  • 저장 공간이 크게 필요하기 때문에 추가 저장 곤간이 필요하다.
  • 잘못 사용하는 경우 오히려 검색 성능을 저하할 수 있다.

🎯 Index의 자료구조

해시테이블

해시테이블은 key와 value를 한 쌍으로 데이터를 저장하는 구조이다.

• 장점

  • 시간 효율성이 매우 좋다 (평균적으로 O(1))
  • 등호(=)연산에 최적화되어있다.

• 단점

  • 해시 충돌이라는 변수가 존재한다.
  • DB에서 자주 사용되는 >,<연산 같은 경우에는 해시테이블의 테이터가 정렬되어 있지 않아 시간이 오래 걸린다.

  B-Tree

  Binary Search Tree와 매우 유사하지만, 한 노드 당 자식 노드가 2개 이상이 가능한 tree 구조로 key 값을 이용해 찾고자 하는 데이터를 트리구조를 이용해 찾는다.

  

• 장점

  • 어떤 값에 대해서도 같은 시간에 결과를 얻을 수 있다.(균일성)
  • 균형트리 구조이기 때문에 성능이 안정화 되어있다.
  • 데이터양에 비례해 효과가 상승한다.

• 단점

  • 노드에 데이터가 같이 저장되어 있어, 용량에 이슈가 생길 수 있다.
  • 생성 당시에는 균형트리이지만 테이블 갱신의 반복을 통해서 균형이 깨지고 성능이 악화된다.

  B+Tree

  B+Tree는 B-Tree의 확장개념으로, 리프노드에만 key와 data를 저장하고, 리프 노드끼리 LinkedList로 연결되어 있는 구조이다.

  

• 장점

  • 리프 노드에만 데이터가 있어, 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다.
  • 하나의 노드에 더 많은 key를 담을 수 있어 트리의 높이는 더 낮아진다(cashe hit 높일 수 있다)

  B-Tree vs B+Tree