Database Index (인덱스)

Tags:

• Database
• RDBMS
• Transaction

인덱스(index)란?

• 데이블에 대한 동작 속도를 높여주는 자료 구조를 말한다.
• 인텍스는 테이블 내에 1개의 컬럼, 혹은 여러 컬럼을 이용하여 생성될 수 있다.
• 빠른 검색 동작뿐 아니라 레코드 접근과 관련 효율적인 순서 매김 동작에 대한 기초를 제공한다.
• 인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료 구조이다.
• 만약 우리가 책에서 원하는 내용을 찾는다고 하면, 책의 모든 페이지를 찾아 보는 것은 오랜 시간이 걸린다. 그렇게 때문에 책의 저자들은 책의 맨 앞 또는 맨 뒤에 색인을 추가하는데, 데이터베이스의 index는 책의 색인과 같다.
• 데이터베이스에서도 테이블의 모든 데이터를 검색하면 시간이 오래 걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조를 생성하여 빠르게 조회할 수 있도록 돕고 있다.
• 만약 index를 적용하지 않은 컬럼을 조회하면, 전체를 탐색하는 Full Scan이 수행된다. Full Scan은 전체를 비교하여 탐색하기 때문에 속도가 떨어진다.

데이터베이스에서 자료를 갬색하는 2가지 방법

• FTS(Full Table Scan)
  • 테이블을 처음부터 끝까지 검색하는 방법이다.
• Index Scan
  • 인데그를 검색하여 해당 자료의 테이블을 액세스하는 방법이다.

인덱스의 자료구조

• 해시 테이블

  • 컬럼의 값으로 생성된 해시를 기반으로 인덱스를 구현한다.
  • 시간복잡도 O(1)이라 검색이 매우 빠르다.
  • 부등호(<, >)와 같은 연속적인 데이터를 위한 순차 검색이 불가능하다.

• B+Tree

  • 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조이다.
  • BTree의 리프노드들을 LinekdList로 연결하여 순차 검색을 용이하게 하였다.
  • 해시 테이블보다 나쁜 O(𝑙𝑜𝑔2𝑛)의 시간 복잡도를 갖지만 해시테이블보다 흔하게 사용된다.