Index 개념 및 적용

[berryberrybin]

Index 란?

• 추가적인 쓰기작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료 구조
• Database 성능을 높이기 위한 방법 중 하나로 사용됨 (Index, 반정규화, 클러스터링 등등)
• 책의 모든 페이지를 찾아보는 것은 오랜 시간이 걸림. 이를 해결하기 위해 책의 맨뒤에 색인을 추가하는데 index가 색인과 동일한 역할을 함

Index 적용시 조회 속도가 빨라지는 이유

• 기존 탐색 방벅이 느린 이유
  • 데이터 베이스는 조건문으로 검색할때, 테이블 전체를 full scan으로 탐색함
  • row의 값을 순차적으로 scan하며 비교하므로, 데이터가 많아지면 비효율적인 방식
• Index가 빠른 이유
  • 인덱스는 데이터의 주소를 기억하고 관리하는 인덱스파일(IndexFile)과 실제 데이터를 기억하는 데이터 파일(Data File)로 구성되어 있음
  • 데이터 검색시 먼저 인덱스 파일에서 찾고자하는 데이터가 저장된 주소를 찾은 다음에, 찾은 주소값을 통해 데이터 파일에서 데이터를 찾음

예시

• 제품의 정보들을 저장하는 데이트 파일이 있으며, 각 값에 배정된 주소값에 대한 정보로 이루어진 인덱스 파일이 생성됨
• CA01라는 값의 데이터를 찾으려고 한다면 인덱스 파일을 통해 해당 값이 저장된 물리적 주소인 '500'을 먼저 찾음
• 그 후에 '500' 주소값을 가지는 항목을 찾기때문에 원하는 데이터에 바로 접근 가능
• 만일 순차접근 방식을 통해 검색한다면 AA01부터 CA01까지 모두 검색하여 많은 시간이 소요됨

[berryberrybin]

index의 장단점

• 장점
  • 테이블 조회 속도와 그에 따른 성능을 향상 시킬 수 있음
  • 전반적인 시스템 부하를 줄 일 수 있음
• 단점
  • 인덱스 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요함
  • 인덱스 관리하기 위해 추가 작업이 필요함
  • 인덱스를 잘못 사용할 경우 오히려 성능 저하 발생할 수 있음

index를 사용하면 좋은 경우

• 규모가 작지 않은 테이블
• INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
• JOIN이나 WHERE 또는 ODER BY에 자주 사용되는 컬럼
• 데이터의 중복도가 낮은 컬럼

Index 자료구조 : 해시테이블(Hash Table)

• 해시테이블은 Key-Value로 데이터를 저장하는 자료구조 중 하나로 빠른 검색이 필요할 때 유용
• Key값을 이용해 고유한 index를 생성하여 해당 index에 저장된 값을 꺼내오는 구조
• 해시 테이블 기반의 DB 인덱스는 특정 컬럼의 값과 데이터의 위치를 key-value로 사용함
• 해시테이블의 시간 복잡도는 O(1)
  • 해시테이블은 내부에 버켓이라는 배열이 존재함
  • 해시 함수를 통해 key를 고유한 해시값으로 변환시킴
  • 이를 버켓 배열의 인덱스로 사용하며, 해당 인덱스에 Value를 저장함
  • key 값으로 Value가 저장되어있는 주소를 바로 산출 할 수 있기 때문에 해시테이블의 평균적인 시간복잡도는 O(1)
• 해시 함수의 단점
  • 해시 함수를 제대로 정의하지 않으면 해시값이 중복되어 해시 충돌이 발생함
    • 검색 성능이 하락해 시간복잡도가 O(N)으로 수렴할 수 있음
  • 해시함수는 key가 조금이라도 다르면 완전 다른 해시 값을 생성함
    • Where 조건에서 등호(=)연산 이외에 부등호 연산(>,<)은 부적합
    • 내부 데이터들이 정렬되어 있지 않아 탐색이 효율적이지 않음

[berryberrybin]

Index 자료구조 : B+Tree

• B+Tree는 DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조

• BTree 와 B+Tree 차이점

  • B Tree : 모든 노드에 데이터(Value)를 저장함
  • B+Tree : leaf node에만 데이터를 저장하고, leaf node가 아닌 node에서는 자식 포인터만 저장

• 리프노드 끼리는 LinkedList로 연결되어 있음

• 리프노드에만 데이터가 저장되기 때문에 중간 node에서 key를 올바르게 찾아가기 위해 key가 중복될 수 있음

• 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 됨

• B+Tree 장단점

  • B+Tree는 leaf node를 제외하고, 데이터를 저장하지 않기 때문에 메모리를 더 확보할 수 있음
  • B+Tree는 하나의 node에 더 많은 포인터를 가질 수 있기 때문에 트리의 높이가 더 낮아지므로 검색 속도를 높일 수 있다.
  • Full scan을 하는 경우 B+Tree는 leaf node에만 데이터가 저장되어 있고, leaf node끼리 linked list로 연결되어 있기 때문에 선형 시간이 소모됨( 반면.,B-Tree는 모든 node를 확인해야 함)
  • B-Tree의 경우 최상의 경우 특정 key를 root node에서 찾을 수 있지만, B+Tree의 경우 반드시 특정 key에 접근하기 위해서 leaf node까지 가야 하는 단점이 있음
  • 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생할 수 있다. 즉, B+Tree의 Linked list를 이용하면 순차 검색을 효율적으로 할 수 있게 됨