[DataBase] Index

Index?

• Index는 말 그대로 책의 맨 처음 또는 맨 마지막에 있는 색인이라고 할 수 있다.
• 컬럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 Index를 만든다.
• DBMS의 Index는 항상 정렬된 상태를 유지하기 때문에 원하는 값을 탐색하는데에는 빠르다.
• 하지만, 새로운 값을 추가하거나 삭제, 수정하는 경우에는 쿼리문 실행 속도가 느려진다.
• 즉, 데이터의 저장 성능을 희생하고 대신 데이터의 읽기 속도를 높이는 기능이다.
• 장점
  • 테이블을 조회하는 속도와 그에 따른 성능 향상
  • 시스템 부하 감소
• 단점
  • 인덱스 관리를 위한 추가 작업
  • 자칫 잘못 사용하게 되면 역효과
    • SELECT 쿼리문장의 WHERE 조건절에 사용되는 컬럼이라고 전부 인덱스로 생성해버린다면, 데이터 저장 성능이 떨어지고 인덱스의 크기가 비대해져 오히려 역효과 발생
• 인덱스는 규모가 작지 않으며 수정,생성,삭제의 행위가 자주 발생하지 않는 컬럼, JOIN, WHERE, ORDER BY에 자주 사용되는 컬럼, 데이터의 중복이 낮은 컬럼에 사용하기 용이하다.

Index 자료구조

• Hash Index
  • 칼럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘으로 매우 빠른 검색을 지원한다. 하지만 값을 변형해서 인덱싱하므로, 특정 문자로 시작하는 값으로 검색을 하는 전방 일치와 같이 값의 일부만으로 검색하고자 할 때는 해시 인덱스를 사용할 수 없다. 주로 메모리 기반의 데이터베이스에서 많이 사용한다.
• B+-Tree
  • B-Tree
    • 리프노드, 브랜치노드 모두 데이터 저장이 가능하다.
    • 모든 노드가 여러 키를 포함하고 2개 이상의 하위를 갖는 자체 균형 탐색트리
    • 루트 노드에서 리프노드까지 거리가 동일하다. 즉, 모든 노드에서 탐색한다.
    • 트리 차수에 따라 노드 내 최대 key-value 수가 달라진다.
    • 처음 생성때에는 균형트리 이지만, 지속적으로 수정,삭제,생성을 하면 균형이 점점 깨진다. 그러면서 성능도 저조해진다.
    • 자주 access 되는 노드를 루트 노드 가까이 배치할 수 있고, 루트 노드에서 가까울 경우, 브랜치 노드에도 데이터가 존재하기 때문에 빠르다.

• B+Tree
  = Leaf Node만 인덱스와 함게 데이터를 가지고있고, 나머지 노드들은 데이터를 위한 인덱스 키만 가진다.
  • Leaf Node는 오직 Leaf Node끼리 LinkedList로 연결
  • B-Tree에 비해 노드 순회가 쉽다. Value가 없어 메모리가 절약되지만, Value를 찾기 위해서는 Leaf Node까지 올라갸아 한다.
  • 즉, Leaf Node까지 가야만 데이터가 존재한다.

• 왜 Index 생성때 B-Tree 사용할까?
  • 데이터에 접근하는 시간복잡도가 O(1)인 hash table 이 더 효율적일 것 같은데? SELECT 질의의 조건에는 부등호(<>) 연산도 포함이 된다. hash table 을 사용하게 된다면 등호(=) 연산이 아닌 부등호 연산의 경우에 문제가 발생한다. 동등 연산(=)에 특화된 hashtable은 데이터베이스의 자료구조로 적합하지 않다.

Index 성능과 고려 사항

• SELECT 쿼리의 성능을 향상시키는 Index는 좋은것일까?
  • 쿼리문의 성능을 향상시킨다는데, 모든 컬럼에 Index를 생성하면 빨라질까?
  • No!
    • Index를 생성하면 INSERT, DELETE, UPDATE 쿼리문을 실행할 때 별도 과정이 추가된다.
    • INSERT의 경우 INDEX에 대한 데이터도 추가해야해서 성능에 손실이 간다.
    • DELETE의 경우 INDEX에 존재하는 값은 삭제하지 않고 사용하지 않는 표시만 한다. 결국 row의 수는 그대로이다.
    • 위 작업이 지속적으로 반복된다면 실제 데이터는 10개인데 데이터가 100만건이 될 수도 있는 참사가 나올수도 있다. 이러면 인덱스는 역할에 충실하지 못하게 된다.
    • UPDATE의 경우 INSERT,DELETE 의 문제점들을 동시에 가지고 있다.
    • 이전 데이터가 삭제되고 그 자리에 새 데이터가 들어오는 개념이기 때문이다. 즉, 변경 전 데이터는 삭제되지 않고 INSERT로 인해 Split도 발생한다.
• Example
  • 이름,나이,성별 의 필드를 가지고 있는 테이블이 있다.
  • 이름은 여러 경우의 수가 존재하며 나이는 int 타입이고, 성별은 남,녀 두가지 뿐인 데이터가 존재한다고 예측할 수 있다.
  • 이 경우 이름에 대해서만 인덱스를 생성하면 효율적이다.
    • 왜냐하면 10000레코드에 해당하는 테이블에 대해 2000단위로 성별에 대한 인덱스를 생성했다고 가정했을때, 값의 range가 적은 성별은 인덱스를 읽고 다시 한 번 디스크 I/O가 발생하기 때문에 그만큼 효율적이지 못한것이다.
    • Disk I/O?
      • 말 그대로 디스크에 들어가고 나오고 하는 데이터이다.즉, 데이터를 작성,변경할 때 디스크에 저장되는것