[DATABASE] 인덱스(Index)

김수혁·2024년 1월 16일

B+TREE B+트리 Database Index db hash 인덱스 해쉬

OS

목록 보기

5/6

1. 인덱스(Index)란?

추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조

데이터베이스를 책과 비교하였을 때, 우리가 책의 내용을 찾기 위해 첫 장부터 한장한장 찾기 시작한다면 시간이 상당히 걸릴 것이다.
하지만, 책 앞에 목차 혹은 색인(Index)를 활용한다면 원하는 내용을 찾는데 상당한 시간을 절약할 수 있다.
이처럼 테이블에서도 원하는 데이터를 찾기 위해 모든 row를 조회한다면 시간이 오래 걸릴 것이다. 이러한 검색 시간을 절약하기 위해 우리는 책의 색인과 같이 데이터와 데이터의 위치를 포함한 자료구조인 인덱스를 사용한다.

그렇다면 CRUD에서 활용하는 SQL문 중 어떤 기능에서 인덱스가 성능을 향샹시킬까?
정답은 데이터를 조회하는 SELECT 외에도 연산을 수행하기 위해 조회를 요구하는 작업인 UPDATE와 DELETE의 성능 또한 향상된다.

인덱스의 장단점

인덱스의 장점

데이터 검색 및 정렬 속도 향상
데이터가 정렬되어 있기 때문에 테이블에서 정렬과 검색 속도를 향상시킨다.

조건 검색 Where절의 효율성
Where절 사용 시 조건에 맞는 데이터를 찾기 위해 데이터를 탐색해야 하는데, 인덱스를 통해 데이터가 정렬되어 있으면 빠르게 찾아낼 수 있다.

정렬 Order by 정의 효율성
Order by는 본래 부하가 많이 걸리는 작업이기 때문에 인덱스를 통해 이미 정렬되어 있으면 Order by를 피할 수 있다.

MIN, MAX의 효율적인 처리 가능
인덱스를 통해 정렬된 데이터에서 MIN, MAX를 효율적으로 추출할 수 있다.

쿼리 성능 향상
위에서 언급한 것 처럼 SELECT, UPDATE, DELETE의 쿼리문들의 성능이 향상된다. 이를 통해 쿼리 실행 속도를 높일 수 있다.

조인 성능 향상
두 개 이상의 테이블 조인 시, 인덱스를 통해 DB에서 관련 행을 빠르게 찾아 병합할 수 있기 때문에 조인 성능이 향상된다.

인덱스의 단점

추가적인 공간 소모
데이터베이스 내에서 인덱스 테이블을 생성하므로 추가적인 공간을 필요로 한다. (보통 DB의 10%정도의 추가 공간 필요)

정렬된 상태를 계속 유지해야 함
INSERT, UPDATE, DELETE 명령어가 수행된다면 정렬을 수행해야한다. 이러한 정렬을 DB에 부하를 발생시키기 때문에 인덱스는 데이터를 실제로 삭제하지 않고 다음과 같은 작업을 대신 수행한다.

UPDATE: 기존의 데이터를 사용하지 않음 처리하고, 갱신된 데이터를 인덱스에 추가

DELETE: 삭제하는 데이터의 인덱스를 사용하지 않음 처리

인덱스가 모든 쿼리에 도움을 주지 않음
인덱스가 모든 쿼리에 도움을 주는 것은 아니다. 테이블의 개수가 적거나 조회하려는 데이터가 테이블의 대부분일때는 인덱스를 사용하지 않는 것이 더 속도가 빠르다.

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

규모가 큰 테이블 (데이터가 많은 경우)
INSERT, UPDATE, DELETE가 자주 발생하지 않는 경우
JOIN, ORDER BY, WHERE이 자주 사용되는 경우
데이터의 중복도가 낮은 경우

클러스터 인덱스(Clustered Index)

기본적으로 테이블 당 1개만 생성이 가능하며 보통 PK가 클러스터링 인덱스로 구성되어있다.
Root Node와 Leaf Node로 구성된 인덱스 페이지이며, Root 페이지에서 하위 노드로 이동하면서 Leaf Node까지 이동 후 Leaf Node에서 데이터 위치를 참조하는 포인터를 획득하여 이 포인터를 이용하여 실제 데이터가 위치한 곳을 찾아 데이터를 가져온다.
데이터 삽입, 수정, 삭제 시 항상 정렬된 상태를 유지해야 한다.

Root Node란?
인덱스 맨 위쪽에 존재하는 노드이다.
인덱스의 전체 구조를 유지하고, 인덱스를 탐색하는데 필요한 정보를 가지고 있다.
일반적으로 인덱스 중 가장 적은 공간을 차지하며 DBMS는 인덱스를 사용하여 데이터를 검색 시 루트노드에서 시작하여 하위 노드로 이동하며 검색을 시도한다.

논클러스터 인덱스(Non-Clustered Index)

index page와 data page가 분리되어 있다.
논-클러스터 인덱스의 index page에는 data page의 주소가 들어있고 이 주소를 이용하여 data page에 존재하는 실제 데이터를 가져올 수 있다.
테이블이 정렬되어있지 않기 때문에 행이 추가, 삭제, 변경되어도 영향을 덜 받는다.
하지만, 데이터 검색 시 인덱스 페이지에서 먼저 Leaf Node를 찾고 Leaf Node에 저장된 데이터 주소를 이용하여 데이터 페이지에서 검색 대상을 찾아오기 때문에 클러스터 인덱스보다 많은 I/O 작업이 필요하다.

인덱스의 자료구조 (Hash Table, B-Tree)

해시 테이블(Hash Table)

데이터 요소의 주소/인덱스 값이 해시 함수에서 생성되는 데이터 구조 유형이다.
인덱스 값이 데이터 값에 대한 키로 동작하기 때문에 매운 빠른 데이터 엑세스가 가능하다.
해시 테이블 기반 DB의 인덱스의 경우 (Key, Value)쌍을 저장하며 조회하는 동안 Key가 해시되고 결과 해시는 해당 값이 저장된 위치를 나타내게 된다.
해시테이블의 특징

성능 O(1)의 시작복잡도
메모리 기반 데이터베이스에서 많이 사용
정렬 X
데이터의 크기가 늘어나면 테이블의 크기도 증가
범위에 대한 비교 X, 오직 equality 비교 O
multicolumn index(2개 이상의 속성으로 이루어진 인덱스)의 경우 전체 속성에 대한 조회만 가능
- B-Tree의 경우, (a,b) 인덱스 테이블에서 a만 검색 가능, Hash Table의 경우 불가능