[DB] 데이터베이스가 사용하는 인덱스는 무엇일까?

개인 학습을 기록한 내용을 담고 있어 추후 수정될 수 있습니다.

인덱스의 개념

인덱스는 데이터베이스 테이블에서 검색 성능을 향상시키기 위한 자료구조의 이름입니다.

테이블에 있는 특정 칼럼에 대해 인덱스를 생성하면,
해당 칼럼의 데이터들은 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장됩니다.

인덱스가 생성된 이후 입력 받은 쿼리문에서 인덱스를 활용할 수 있다면
인덱스 정보를 저장하고 있는 인덱스 테이블을 활용하여 검색을 빠르게 수행합니다.

주위에서 인덱스처럼 동작하는 기능을 찾아보면 책에 있는 목차 혹은 단어 정리 페이지가 있습니다.

예를들어, 운영체제에 대해 1페이지부터 1’000페이지까지 작성된 책이 있다고 하겠습니다.
이 책의 독자는 운영체제 중 ‘프로세스’에 대한 설명을 찾아보고자 합니다.

여기서 인덱스가 없다면 독자는 1페이지부터 1’000페이지까지
한 장씩 넘겨가며 ‘프로세스’에 대한 내용이 있는지 확인해야 합니다.
알고리즘의 시간복잡도로 표현한다면 O(N)이 됩니다.

운영체제 책을 출간한 출판사는 이러한 독자의 불편을 덜어주고자
책의 첫 페이지에 책이 담고 있는 내용에 대한 목차를 정리하고
책의 마지막 페이지에는 등장하는 단어를 사전 순서로 정리하여 독자가 원하는 정보를
책에서 빠르게 찾을 수 있도록 개정판을 출간하였습니다.

여기서 추가된 목차와 단어 정리가 데이터베이스에서 사용하는 인덱스라고 할 수 있습니다.

따라서 ‘운영체제’ 책의 독자는 목차 혹은 단어 정리를 사용해서 원하는 페이지를 빠르게 찾을 수 있습니다.

인덱스 사용 목적 (인덱스의 장점)

인덱스의 가장 큰 특징은 생성된 인덱스들이 정렬되어 있다는 점입니다.
이 특징 덕분에 조건 검색을 실행할 때 빠르게 검색을 실행할 수 있습니다.

조건 검색 Where 절의 효율성

데이터베이스에서 테이블을 생성하고 여러 레코드를 삽입하면
삽입 레코드들은 정렬되지 않고 삽입된 순서대로 테이블에 존재하게 됩니다.

이렇게 정렬되지 않은 테이블에서 Where절을 실행할 경우,
테이블의 첫 번째 레코드부터 조건에 맞는 레코드가 등장할 때 까지 순차적으로 탐색을 수행합니다.
이러한 순차탐색을 풀 테이블 스캔(Full Table Scan)이라고 합니다.

그러나 인덱스를 사용하여 정렬되어 있는 인덱스 테이블을 사용한다면
풀 테이블 스캔 보다 더욱 빠르게 원하는 조건의 데이터를 찾을 수 있을 것 입니다.

정렬 Order by 절의 효율성

인덱스를 사용하면 Order by에 의한 정렬 과정을 회피할 수 있습니다.
쿼리문에 의해 생성된 뷰 라고 하더라도 레코드의 수가 많다면 많은 연산량이 필요할 수 있습니다.

그러나 인덱스를 사용한다면, 인덱스 테이블 자체가 정렬되어 있기 때문에
Order by절에서 소모되는 정렬 연산량을 줄일 수 있습니다.

MIN, MAX 연산의 효율적 처리 가능

MIN, MAX 연산은 최댓값과 최솟값만 가져오는 연산입니다.
인덱스 테이블은 정렬된 테이블이기 때문에
첫 번째 레코드 혹은 마지막 레코드를 출력하므로서 최댓값 혹은 최솟값을 가져올 수 있습니다.

인덱스의 단점

앞서 언급한 장점들은 모두 인덱스가 정렬되어 얻을 수 있는 특징들 이였습니다.
인덱스의 단점은 이러한 특징의 기본이 되는 정렬 때문에 생겨난 특징입니다.

모든 연산에 있어서 인덱스 테이블은 목적에 맞게 사용되기 위해서 항상 정렬되어 있는 상태여야 합니다.
그렇기 때문에 UPDATE, INSERT, DELETE 연산을 수행한다면
기존에 있는 인덱스 테이블을 새롭게 갱신된 데이터로 재정렬 해야 합니다.

또한 인덱스 테이블은 기존 테이블을 활용하기 위해 별도의 메모리 공간을 생성합니다.
테이블의 크기가 작고 메모리 공간에 여유가 많다면 상관없을 수 있지만
실제 데이터베이스는 많은 테이블을 사용하고 메모리 공간에 여유가 없을 수 있습니다.
때문에 검색 향상을 위한 추가 메모리 확보는 메모리 공간 활용 측면에서 손해일 수 있습니다.