데이터베이스 인덱스

cdwde·2022년 10월 12일

삐룸 스터디(얕게 이것저것🙃)

목록 보기

8/10

페이지네이션에 대해 알아보다가 인덱스를 타는지 확인하고 효율적인지(?) 판단하는 글을 봤는데 정확하게 인덱스를 탄다는게 무슨 소리 이해를 못해서.. 인덱스에 대해 먼저 알아보려고 한다.

✅ 인덱스(index)란?

추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다.
테이블의 특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터를 정렬한 후 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다.

✅ 인덱스의 장점과 단점

장점

조건 검색 WHERE 절의 효율성

테이블을 만들고 안에 데이터가 쌓이게 되면 테이블의 레코드는 내부적으로 순서가 없이 뒤죽박죽으로 저장이 된다. 이렇게 되면 WHERE 절에 특정 조건에 맞는 데이터들을 찾아낼 때도 레코드의 처음부터 끝까지 다 읽어서 검색 조건과 맞는지 비교해야 한다. 이를 풀 테이블 스캔(Full Table Scan) 줄여서 풀 스캔(Full Scan)이라고 한다. 하지만 인덱스 테이블 스캔(Index Table Scan) 시 인덱스 테이블은 데이터들이 정렬되어 저장되어 있기 때문에 해당 조건에 맞는 데이터들을 바르게 찾아낼 수 있다.

정렬 ORDER BY 절의 효율성

인덱스를 사용하면 ORDER BY에 의한 정렬 과정을 피할 수 있다. ORDER BY는 굉장히 부하가 많이 걸리는 작업이다. 정렬과 동시에 1차적으로 메모리에서 정렬이 이루어지고 메모리보다 큰 작업이 필요하다면 디스크 I/O도 추가적으로 발생하기 때문이다. 하지만 인덱스를 사용하면 이미 정렬되어 있기 때문에 가져오기만 하면 된다.

디스크 I/O
간단하게 데이터를 작성하고 변경할 적에 디스크, 즉 HDD에 저장되는 것을 말한다.

MIN, MAX의 효율적인 처리

데이터가 정렬되어 있기에 얻을 수 있는 장점이다. MIN, MAX 값을 레코드의 시작 값과 끝 값 한 건 씩만 가져오면 되기 때문에 Full Scan보다 효과적이다.

인덱스를 사용하면 무조건 효율이 좋을까? ❌

인덱스는 DML에 취약

INSERT, UPDATE, DELETE를 통해 데이터가 추가되거나 값이 바뀐다면, 인덱스 테이블 내에 있는 값들을 다시 정렬해야 한다. 그리고 인덱스 테이블, 원본 테이블 이렇게 두 군데의 데이터 수정 작업을 해줘야한다는 단점이 발생한다. 그렇기 때문에 DML이 빈번한 테이블보다 검색을 위주로 하는 테이블에 인덱스를 생성하는 것이 좋다.

속도 향상을 위해 인덱스를 많이 만드는 것은 좋지 않다

인덱스를 관리하기 위해서는 데이터베이스의 약 10%에 해당하는 저장공간이 필요하다. 따라서 속도 향상에 비해 단점들의 COST를 비교해서 인덱스를 만들지 말지 정해야 한다.

✅ 인덱스의 관리

DBMS는 인덱스를 항상 최신의 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다. 그렇기 때문에 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE가 수행된다면 계속 정렬을 해주어야 하고, 그에 따른 부하가 발생한다. 이런 부하를 최소화하기 위해 인덱스는 데이터 삭제라는 개념에서 인덱스를 사용하지 않는다라는 작업으로 이를 대신한다.

INSERT: 새로운 데이터에 대한 인덱스를 추가함
DELETE: 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행함
UPDATE: 기존의 인덱스를 사용하지 않음으로 처리하고, 갱신된 데이터에 대해 인덱스를 추가함 (?)

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

INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
JOIN, WHERE, ORDER BY에 자주 사용되는 컬럼
데이터 중복도가 낮은 컬럼 = Cardinality가 높은 컬럼

일반적으로 Cardinality가 높은 컬럼을 우선적으로 인덱싱하는 것이 검색 성능에 유리하다. Cardinality란 특정 데이터 집합의 유니크한 값의 개수를 의미한다.
예를 들어

남,여 등 2가지 값만 존재하는 성별 컬럼은 중복도가 높으며 Cardinality가 낮다
개인마다 고유 값이 존재하는 컬럼은 중복도가 낮으며 Cardinality가 높다

Cardinality가 높은 컬럼의 경우 index를 통해 데이터를 더 많이 필터링할 수 있기 때문이다.

✅ 인덱스의 자료구조

인덱스를 구현하기 위해서는 다양한 자료구조를 사용할 수 있는데 가장 대표적으로 해시 테이블과 B+Tree가 있다.

해시 테이블(Hash Table)

해시 테이블은 Key, Value로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용하다.

해시 테이블
해시 테이블은 각각의 key값에 해시 함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷이라고 한다.

시간복잡도는 O(1)로 매우 빠른 검색을 지원한다.
하지만 DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적인데, 이유는 해시가 등호 연산에만 특화되었기 때문이다. 이러한 특성에 의해 부등호 연산이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.
예를 들어 "안녕"으로 시작하는 모든 데이터를 검색하기 위한 쿼리문은 인덱스의 혜택을 전혀 받지 못하기에, 데이터베이스의 인덱스에서는 B+Tree가 일반적으로 사용된다.

B+Tree

B+Tree는 DB 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조이다. B+Tree는 모든 노드에 데이터를 저장했던 B-Tree와 다른 특성을 가지고 있다.

leaf node만 인덱스와 함께 데이터를 가지고 있고, 나머지 노드들은 자식 포인터만 저장한다.
leaf node끼리는 LinkedList로 연결되어 있다.
반드시 leaf node에만 데이터가 저장되기 때문에 중간 node에서 key를 올바르게 찾아가기 위해 key가 중복될 수 있다.

이로 인한 장점은?
leaf node를 제외하고 데이터를 저장하지 않기 때문에 메모리를 더 확보할 수 있다. 따라서 하나의 node에 더 많은 포인터를 가질 수 있기 때문에 트리의 높이가 더 낮아지므로 검색 속도를 높일 수 있다.(?)
Full Scan을 하는 경우 B+Tree는 leaf node에만 데이터가 저장되어있고, leaf node끼리 linked list로 연결되어 있기 때문에 선형 시간이 소모된다. 반면 B-Tree는 모든 node를 확인해야 한다.