[Database] Index

Index란 우리가 실생활에서 자주 접해볼 수 있는 단어이다. 우리는 책에서 원하는 내용을 찾기 위해서 책의 처음부터 끝까지 원하는 내용을 찾아보는 것이 아니라 목차나 인덱스에서 원하는 내용을 먼저 찾은 뒤 해당 내용이 있는 페이지를 찾아간다. 이와 같은 방식으로 데이터베이스에서도 인덱스를 사용한다.

Database에서 Index 란 ❔❔

출처: https://mangkyu.tistory.com/96

데이터베이스에서 인덱스란 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다.

데이터베이스에서 데이터 조회 요청을 하면, DB 서버 프로세스는 메모리(DB 버퍼 캐시)를 먼저 확인한다. 메모리에는 자주 사용되는 테이블이 캐싱되어 있는데, 메모리에 원하는 데이터가 없는 경우 디스크에서 데이터 파일을 복사해온 후 조회한 데이터를 찾아 반환한다.

이때 인덱스를 사용하지 않은 컬럼을 조회할 경우 전체 테이블 블록을 가져와 탐색하는 Table Full Scan을 해야 한다. Table Full Scan은 테이블 전체를 비교하여 탐색하기 때문에 비교적 속도가 느리다.

(항상 풀 스캔이 느린 것만은 아니다. Database Scan 포스트에서 설명)

따라서 인덱스를 사용하여 Table Full Scan을 최소화해 조회 속도를 향상시키는 것이 중요하다.

인덱스 관리

DBMS는 인덱스를 항상 최신의 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다. 그렇기 때문에 인덱스가 적용된 컬럼에 Insert(삽입), Update(수정), Delete(삭제)가 수행된다면 추가적인 연산이 발생하고 그에 따른 오버헤드가 발생한다.

• Insert: 새로운 데이터에 대한 인덱스 추가
• Update: 기존의 인덱스를 사용하지 않음 처리하고, 수정된 데이터에 대한 인덱스 추가
• Delete: 삭제하는 데이터의 인덱스를 사용하지 않음 처리

인덱스의 장점과 단점

장점

조건 검색 Where 절의 효율성

특정 컬럼 입장에서 테이블의 레코드는 순서가 없이 저장된다. 이때 Where 절의 특정 조건에 맞는 데이터를 찾기 위해서 테이블의 처음부터 끝까지 풀 스캔을 하면서 조건에 부합하는지 비교해야 한다. 하지만 인덱스는 데이터가 정렬되어 있기 때문에 Where 절의 조건에 맞는 데이터를 빠르게 찾아낼 수 있다.

 

정렬 Order by 절의 효율성

인덱스를 사용하지 않을 경우 전체 테이블을 대상으로 Order by에 의한 정렬을 해야 한다. 하지만 인덱스를 사용할 경우 이미 정렬되어 있기 때문에 정렬에 필요한 자원을 소모할 필요가 없다.

 

Min, Max의 효율성

Min, Max 또한 인덱스를 사용하지 않을 경우 Table Full Scan을 해야 한다. 하지만 인덱스는 정렬되어 있기 때문에 레코드의 시작값(Min) 또는 끝값(Max)를 가져오면 된다.

단점

• 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 추가 저장 공간이 필요하다.
• 인덱스를 관리하기 위해 추가 작업이 필요하다
• 인덱스를 잘못 사용할 경우 오히려 성능이 저하될 수 있다.
  (이유는 Database Scan 포스트에서 설명)

인덱스를 사용하면 좋은 경우

인덱스를 효율적으로 사용하기 위해서는 데이터가 거의 중복되지 않는 컬럼(Cardinality가 낮음 컬럼)이나 조건절 또는 Order by 절에 자주 사용되는 컬럼을 인덱스로 생성하는 것이 좋다. 또한 규모가 작은 테이블에 인덱스를 사용할 경우 Table Full Scan과 차이가 크지 않기 때문에 규모가 큰 테이블에 인덱스를 사용하는 것이 좋다.

1. 규모가 큰 테이블
2. Insert, Update, Delete가 자주 발생하지 않는 컬럼
3. Join이나 Where, Order by에 자주 사용되는 컬럼
4. 데이터의 중복도가 낮은 컬럼(Cardinality가 낮은 컬럼)

인덱스의 자료구조

인덱스를 구현하는 대표적인 자료구조인 해시 테이블과 B+트리에 대해 간단하게 알아보자.

Hash Table

해시 테이블은 (Key, Value) 형태로 데이터를 저장해 Key를 이용하여 데이터를 빠르게 가져올 수 있다는 장점이 있다.

출처: https://mangkyu.tistory.com/96

해시 테이블 기반의 인덱스는 (컬럼의 값, 데이터 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현한다. 해시 테이블의 시간복잡도는 O(1)로 굉장히 빠른 검색을 지원한다.

하지만 해시 테이블의 경우 등호(=) 연산에만 특화되어 있기 때문에 인덱스에서 사용이 제한적이다. Key 값을 생성하는 해시 함수는 값이 조금이라도 달라지면 완전히 다른 해시 값을 생성하기 때문에 부등호 연산(<, >)이 자주 사용되는 데이터베이스 검색에는 적합하지 않다.

이러한 이유로 데이터베이스의 인덱스에서는 B+트리가 일반적으로 사용된다.

B+Tree

• 리프노드는 인덱스와 데이터(ROWID)를 가지고 있고, 내부노드는 인덱스만 갖는다.
• 리프노드들은 연결되어 있다.

B+트리는 리프노드들이 모두 연결되어 있기 때문에 데이터베이스에서 자주 사용되는 부등호 연산에 적합한 자료구조이다. B+트리의 시간복잡도는 O(logN)으로 해시 테이블보다 탐색 시간이 오래 걸리지만, 부등호 연산에 적합하기 때문에 데이터베이스의 인덱스에서는 B+트리를 주로 사용한다.

---

Reference

https://mangkyu.tistory.com/96

https://lovefor-you.tistory.com/183

https://hoon93.tistory.com/53

https://wedul.site/403

https://coding-factory.tistory.com/746

https://www.youtube.com/watch?v=9ZXIoh9PtwY&t=313s 

https://www.youtube.com/watch?v=NkZ6r6z2pBg&t=646s