[DB] Index

calm0_0·2023년 5월 2일

목록 보기

1/6

인덱스(Index)란?

인덱스(Index)는 우리가 흔히 접하는 책에서의 목차나 찾아보기에 비유할 수 있습니다. 책에서 찾고하 하는 내용이 있을 때 목차나 찾아보기가 없다면 앞에서부터 차례대로 확인해야 합니다. 책이 두껍고 찾으려는 내용이 책 후반부에 있다면 해당 내용을 찾기 위해 많은 시간이 소요될 것입니다. 하지만 목차나 찾아보기를 이용한다면, 해당 내용이 어느 페이지에 있는지 찾은 후, 해당 페이지를 확인한다면 더 빠르게 찾을 수 있습니다.

데이터베이스에서 인덱스란 데이터베이스에서 테이블에 대한 검색 속도를 향상하기 위해 사용되는 자료 구조를 의미합니다.

SELECT * FROM USER WHERE COMPANY_ID = ?

테이블에서 원하는 데이터들을 조회할 때, WHERE 조건절에서 찾고자 하는 컬럼의 인덱스가 없다면, DB에서는 테이블 전체를 탐색(Full Table Scan)하여 원하는 데이터를 찾게 됩니다. 테이블에 데이터의 양이 많아질수록 검색에 소요되는 시간이 길어집니다.
(적용 가능한 인덱스가 없는 경우, 인덱스 처리 범위가 넓은 경우, 크기가 작은 테이블에서 엑세스 하는 경우 등 데이터베이스가 인덱스를 적용하여도 성능 상 이점이 없다고 판단했을 때 Full Table Scan이 적용될 수 있습니다.)

CRERATE INDEX USER_COMPANY_INDEX ON USER(COMPANY_ID);

하지만 찾으려는 칼럼에 인덱스가 존재한다면, 데이터베이스는 테이블 전체를 탐색하지 않고 인덱스를 바탕으로 찾고자 하는 데이터의 위치를 빠르게 검색합니다. 인덱스를 잘 활용한다면 테이블을 검색하는 속도와 성능을 향상할 수 있고, 그에 따라 시스템의 전반적인 부하를 줄일 수 있습니다.

인덱스의 특징

인덱스의 특징은 다음과 같습니다.
1. 인덱스는 항상 최신의 정렬 상태를 유지합니다.
2. 인덱스도 하나의 데이터베이스 객체입니다.
3. 그렇기 때문에, 원본 데이터베이스 크기의 약 10% 정도의 저장 공간이 필요합니다.

인덱스의 자료구조

데이터베이스에서 인덱스를 구현하기 위해 사용되는 자료 구조에는 Hash Table, B-Tree, B+Tree 등이 있습니다.

Hash Table

해시 테이블 기반의 데이터베이스 인덱스는 (칼럼의 값, 데이터의 위치)를 (key, value)로 사용하여 칼럼의 값으로 생성된 해시를 통해 인덱스를 구현합니다. key값으로 value가 저장되어 있는 위치를 바로 접근할 수 있어 시간복잡도가 O(1)로 매우 빠릅니다. 해시 테이블은 등호(=) 연산에는 최적화되어 있지만, 해시 테이블 내의 데이터들은 정렬되어 있지 않아 부등호 연산(>,<)에는 부적합하다는 단점이 있습니다.

B-Tree (Balanced-Tree)

B-Tree는 균형이 깨졌을 때 발생하는 이진 탐색 트리의 단점을 보완한 자료 구조입니다. 트리의 높이가 같으며, 자식 노드의 개수가 2개 이상인 균형 트리입니다. 각 key의 왼쪽 자식은 항상 해당 key보다 작은 값을, 오른쪽 자식은 큰 값을 가집니다. B-Tree 기반의 인덱스는 특정 칼럼의 값(key)에 해당하는 노드에 데이터의 위치(value)를 저장합니다. 찾고자 하는 값을 루트 노드부터 시작해 하향식으로 탐색해갑니다.
B-Tree는 항상 key를 기준으로 오름차순 정렬되어 있습니다. 때문에 부등호 연산(>,<)에 대한 데이터 탐색이 해시 테이블보다 효율적입니다. 또한 B-Tree는 균형 트리이므로 루트 노드에서 리프 노드까지의 거리가 모두 동일하기 때문에, 평균 시간 복잡도는 O(logN)이 됩니다.

하지만 순차 탐색의 경우 중위 순회를 하기 때문에 효율이 좋지 않습니다. 예시의 경우 7->3->8->1->9->4->10->0->11->5->2->6 순으로 조회하는 등 상당히 많은 노드를 확인해야 합니다.

B+Tree

B+Tree는 B-Tree를 확장 및 개선한 자료구조이며 다음과 같은 특징을 가지고 있습니다.

최하단 리프 노드에만 데이터의 위치(value)를 관리합니다.
리프 노드가 아닌 노드에서는 자식 포인터만 저장합니다.
리프 노드끼리는 Linked List로 연결되어 있고 오름차순으로 정렬되어 있습니다.

B+Tree는 리프 노드를 제외하고 데이터를 저장하지 않기 때문에 (검색을 위해 무조건 리프 노드까지 가야 한다는 단점이 있지만) 메모리를 더 확보할 수 있으며, 하나의 노드에 더 많은 포인터를 가질 수 있어 트리의 높이가 더 낮아지므로 검색 속도를 높일 수 있습니다. 또한 부등호를 이용한 순차 검색 연산을 하는 경우, B-Tree는 많은 노드들을 방문해야 하지만, B+Tree는 리프 노드들을 저장한 Linked List를 한 번만 탐색하게 되어 B-Tree보다 효율적으로 탐색할 수 있습니다.

데이터 갱신 작업의 경우

지금까지 인덱스의 자료 구조를 살펴보며 어떻게 검색 속도를 향상하는지 알아보았습니다. 그렇다면 검색(SELECT)이 아닌 INSERT, UPDATE, DELETE와 같이 데이터 갱신 작업이 이루어지는 경우에 인덱스는 데이터베이스에 어떤 영향을 끼치게 되는지 알아보겠습니다.

인덱스는 항상 정렬된 상태로 유지해야 하기 때문에 인덱스가 적용된 컬럼에 데이터 갱신 작업을 수행하면 원본 테이블 뿐만 아니라 인덱스에도 추가 작업이 필요합니다.

INSERT : 새로운 데이터에 대한 인덱스를 추가
DELETE : 삭제하는 데이터의 인덱스를 사용안함 표시
UPDATE : 기존의 인덱스를 사용안함 표시, 갱신된 데이터에 대한 인덱스 추가

인덱스의 트리 자료 구조는 값이 추가 혹은 삭제될 때마다 트리의 균형을 위해 트리 구조의 재분배 및 합병 등 복잡한 연산이 수반됩니다. 또한 테이블에 UPDATE, DELETE 연산이 자주 발생한다면, 이들은 기존의 인덱스를 삭제하지 않고 '사용하지 않음'으로 처리하기 때문에, 실제 데이터 건수보다 인덱스는 더 많이 존재하게 되어, SQL문 처리 시 비대해진 인덱스에 의해 오히려 성능이 저하될 수 있습니다.

인덱스의 종류

클러스터링 인덱스

실제 데이터 자체가 정렬됩니다. 정렬된 사전에 비유할 수 있습니다.
테이블 당 1개만 존재합니다.

생성 방법

ALTER TABLE member
ADD CONSTRAINT pk_id PRIMARY KEY (id);  -- 우선 순위

ALTER TABLE member MODIFY COLUMN id int NOT NULL;
ALTER TABLE member ADD CONSTRAINT nuq_id UNIQUE (id);

클러스터링 인덱스를 적용한 id 칼럼을 기준으로 데이터를 정렬합니다.
정렬된 데이터를 기준으로 루트 페이지가 생성됩니다.
리프 페이지는 실제 데이터 페이지로 구성됩니다.

논-클러스터링 인덱스

실제 데이터 페이지는 그대로 두고, 별도의 인덱스 페이지를 생성합니다. - 그렇기 때문에 추가 공간이 필요합니다.
실제 데이터 탐색에 도움을 주는 별도의 찾아보기 페이지입니다.
테이블 당 여러 개가 존재합니다.

생성 방법 (unique 제약 조건, 직접 index 생성)

ALTER TABLE member
ADD CONSTRAINT unq_name UNIQUE (name);

CREATE UNIQUE INDEX unq_idx_name
ON member (name);

CREATE INDEX idx_name
ON member (name);