[SQLD] 인덱스

인덱스(Index)

인덱스는 관계형 데이터베이스에 검색 속도를 높이기 위해 컬럼을 색인화하는 것을 말한다.

테이블에 있는 모든 데이터를 돌아보며 원하는 데이터를 가져 오기엔(Full Table Scan) 시간이 오래 걸리기 때문에 컬럼의 값과 레코드에 있는 주소를 키와 값으로 묶어 인덱스를 만드는 것이다.

 

예를 들어, 저장된 데이터의 양이 정말 많은 경우 검색을 할 땐 시간과 자원이 많이 소모 될것이다. 그래서 자주 조회되는 컬럼에 대해 인덱스 테이블을 만들어 `SELECT`문을 사용해 Index 테이블에 있는 값들로 결과를 조회한다. 그러면 이전 보다 성능을 더 올릴 수 있을 것이다.

인덱스 테이블에 해당 값을 찾아 PK를 얻는다. PK 값으로 원본 테이블을 조회한다.

 

 

`EXPLAINS`를 통해 쿼리 접근한 행수(rows)를 비교해보면 인덱스를 사용했을 때 좀 더 빠르게 접근했다는 것을 확인할 수 있다. 단, 통계값이니 만큼 반드시 일치하지는 않다는 것을 알아두자.

B-Tree와 B+Tree

B트리와 B+트리, B*트리 등 알고리즘 관점에서의 내용은 해당 포스팅에서는 다루지 않습니다. 추후에 올릴 예정입니다.

 

데이터베이스에서 가장 일반적으로 사용하는 인덱스 타입으로 B Tree 인덱스가 있다. 

B Tree(Blanced Tree)는 기존 이진 트리와 다르게 하나의 노드에 많은 정보를 담을 수 있다. 그리고 한 노드에 있는 데이터는 항상 정렬된 상태이다. 그렇기 때문에 트리를 탐색할 때 시간을 줄일 수 있다는 장점을 가지고 있는 트리이다. 이 B트리는 이외에도 여러가지 규칙을 가지고 있다.

1. 하나의 노드에 데이터가 N개라면 자식의 노드는 N+1 개이어야 한다.(리프노드가 아닌 경우 2개 이상의 자식을 갖는다.)
2. M차 B Tree의 경우 최대 M개의 자식 노드를 갖는다. 
3. 하나의 노드의 데이터는 항상 정렬을 유지해야한다.
4. 모든 리프 노드의 높이는 같아야 한다. (아래 `8, 10, 12, 14` 노드가 없으면 모든 리프노드 높이가 다르기 때문)

B Tree와 다르게 B+Tree는 루트 - 브랜치 - 리프 노드로 이루어져 있다.

 

B 트리가 탐색을 하려면 루트노드부터 하향식으로 탐색하게 된다. 대소 비교를 통해 값을 찾아 나간다.

B+트리는 인덱스 부분과 리프노드가 나누어져 있다. 리프노드에만 데이터가 저장된다는 뜻이다. 인덱스의 Key 값을 통해 리프 노드에 있는 값을 찾을 수 있는데 이는 메모리를 여유롭게 사용할 수 있다는 장점을 가지고 있다. 그 뜻은 노드에 좀 더 많은 키를 담을 수 있다는 것이다.

또한 마지막에 B+트리의 리프노드는 서로 연결되어 있는데 이는 임의로 접근하나 순차적으로 접근하나 성능이 우수하다는 것을 알 수 있다. 

 

사실 B+트리는 한번의 경로를 통해 탐색만 하면 되므로 굉장히 효율적인 알고리즘이다.

 

트리기반 인덱스 말고도 해시기반 인덱스, 비트맵 기반 인덱스도 있는데 트리 기반 인덱스를 선호하는 이유?

인덱스 구조의 종류로는 해시기반 인덱스(해시함수), 비트맵 기반, 트리 기반 인덱스등이 있다.

이 중에서 비트맵 기반 인덱스는 주로 DW나 데이터 마트에서 검색용도로 주로 사용하는 인덱스다. 즉, 분포가 잘 나타나있는 컬럼에 적합하며 동일한 값이 반복하는 경우에 사용한다.

그리고 해시기반 인덱스는 해시 값을 계산해서 찾아내는 알고리즘으로  아예 일치하는 값을 찾아내는데는 빠르지만 부분의 값을 검색하거나 부등호(<>) 연산의 경우에는 불가능하다. SELECT 질의 조건에는 등호(`=`) 뿐만아니라 부등호(`<>`, 같지않다)도 포함되는데 Hash Table의 경우에는 동등 연산(=)에 특화 되있기 때문에 적합하지 않다.

대수 확장성
인덱스가 효율적인 이유는 단계적으로 데이터를 접근할 수 있는 균형 잡힌 트리와 트리 깊이의 대수 확장성 때문이다.
대수확장성은 트리의 깊이가 리프노드 수 보다 느리게 성장한다는 것을 의미하는데 깊이가 1배만큼 증가하면 리프노드는 최대 4배씩 증가하기 때문에 깊이를 추가해 검색하지 않아도 효율적으로 값을 검색할 수 있다.

 

인덱스 생성해보기

먼저, MySQL에서는 일부 인덱스가 자동으로 생성될 수 있다. 다음 그림을 보면 기본키(PK) 제약 조건을 가지거나 외래 키(FK) 관계를 정의한 열, `UNIQUE NOT NULL` 속성을 가진 열은 이미 인덱스가 생성되어있다. 이미 자동으로 생성된 인덱스를 이용하는 방법도 있지만 수동으로 인덱스를 만들어 데이터베이스 탐색을 최적화할 수 있다.

제약조건을 가지거나 외래 키 관계가 정의된 열은 인덱스가 생성된다.

인덱스 생성

CREATE INDEX idx_name ON TABLE(COLUMN);

 

예를들어, `STUDENT`라는 인덱스로 USER_ID 열의 인덱스를 생성했다고 가정하면 다음 결과를 볼 수 있다.

인덱스 변경

ALTER TABLE 테이블명 DROP 인덱스명;
ALTER TABLE 테이블명 ADD 인덱스명 (테이블_열);

 

인덱스 삭제

ALTER TABLE 테이블명 DROP INDEX 인덱스명;

인덱스 조회

SHOW INDEX FROM 테이블명;

// 혹은

SELECT *
FROM information_schema.STATISTICS
WHERE TABLE_NAME = '테이블명';

 

MongoDB는 도큐먼트 생성시 자동으로 ObjectID 가 생성된다. 부가적으로 세컨더리 키도 설정해서 복합 인덱스를 설정할 수 있다.

 

인덱스 생성시 고려사항

인덱스는 데이터베이스의 성능을 향상 시키는데 중요한 역할을 한다. 하지만 너무 많은 인덱스는 오히려 성능을 악화시킬 수 있다.

그렇다면, 언제 인덱스를 사용하면 좋을까?

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

인덱스는 탐색 성능에 효과를 볼 수 있게 하기 위해 사용한다. 그러므로 `WHERE`절을 자주 사용하거나 `JOIN`을 사용할 때 필요하다.

또는 자주 접근하고 검색하는 컬럼의 경우 인덱스를 생성하면 성능을 향상시킬 수 있다. 그리고 `ORDER BY`나 `ROWNUMBER` `RANK` `DENSE_RANK` 처럼 순위를 매기는데 사용하는 컬럼에 경우에도 사용하면 좋을 것 같다.

인덱스를 사용을 피해야 하는 경우

데이터 중복도가 높은 경우

컬럼내 데이터가 중복이 높으면 인덱스 사용을 피해야 한다. 그러면 같은 레코드의 인덱스를 읽는데 비용이 발생하기 때문이다. 이러한 경우엔 비트맵 기반 인덱스를 사용하는게 적절할 것 같아 보인다.

DML을 자주 사용하는 경우

• INSERT :  인덱스 테이블은 정렬하여 저장하기 때문에 성능 저하가 발생한다. 
• DELETE : 데이터가 삭제되면 인덱스 테이블은 삭제가 되지 않고 사용 안한다는 표시만 남겨둔다. 
• UPDATE  : 인덱스 테이블에서 DELETE 작업을 수행한 후 다시 INSERT 작업을 수행하므로 2배의 작업이 소요된다. 

다중 컬럼을 인덱싱하는 경우, 카디널리티가 높은 컬럼부터 낮은 컬럼 순으로 인덱싱을 해야 효율적이다.

 

 

---

☕️ 포스팅이 도움이 되었던 자료

• B-트리 시뮬레이션

오늘도 저의 포스트를 읽어주셔서 감사합니다.

설명이 부족하거나 이해하기 어렵거나 잘못된 부분이 있으면 부담없이 댓글로 남겨주시면 감사하겠습니다.