[데이터베이스] 인덱스

인덱스는 말 그대로 책의 맨 처음 또는 맨 마지막에 있는 색인이라고 할 수 있다. 이 비유를 그대로 가져와서 인덱스를 살펴본다면, 데이터는 책의 내용이고 데이터가 저장된 레코드의 주소는 인덱스 목록에 있는 페이지 번호가 될 것이다. DBMS도 데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과를 가져 오려면 시간이 오래 걸린다. 그래서 칼럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 인덱스를 만들어 두는 것이다.

DBMS의 인덱스는 항상 정렬된 상태를 유지해야 하기 때문에 원하는 값을 탐색하는데는 빠르지만 새로운 값을 추가하거나 삭제, 수정하는 경우에는 쿼리문 실행 속도가 느려진다. 결론적으로 DBMS에서 인덱스는 데이터의 저장 성능을 희생하고, 그 대신 데이터의 읽기 속도를 높이는 기능이다. SELECT 쿼리 문장의 WHERE 조건 절에 사용되는 칼럼이라고 전부 인덱스로 생성하면 데이터 저장 성능이 떨어지고 인덱스의 크기가 커져서 오히려 역효과를 불러올 수 있다.

 

[Index 자료 구조]

그렇다면 DBMS에서 인덱스는 어떻게 관리되고 있을까?

 

B+ Tree 인덱스 알고리즘

일반적으로 사용되는 인덱스 알고리즘은 B+ Tree 알고리즘이다. B+ Tree 인덱스는 칼럼의 값을 변형하지 않고, 원래의 값을 이용해 인덱싱하는 알고리즘이다.

 

Hash 인덱스 알고리즘

칼럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘으로, 매우 빠른 검색을 지원한다. 하지만 값을 변형해서 인덱싱하므로, 특정 문자로 시작하는 검색하는 등 전방 일치와 같이 값의 일부만으로 검색하고자 할 때는 해시 인덱스를 사용할 수 없다. 주로 메모리 기반의 데이터베이스에서 많이 사용된다.

*- 왜 인덱스를 생성하는데 B+ Tree를 사용할까? *

SELECT 질의의 조건에는 부등호 연산도 포함된다. 앞서 말했듯이 해시 테이블을 사용하면 부등호 연산의 경우 문제가 발생한다. 해시 테이블은 데이터에 접근하는 시간 복잡도가 O(1)이지만 이는 데이터베이스의 자료 구조로 적합하지 않다.

 

[Clustered Index vs. Non-clustered Index]

클러스터란 여러 개를 하나로 묶는다는 의미로 주로 사용되는데, 클러스터드 인덱스도 크게 다르지 않다. 인덱스에서 클러스터는 비슷한 것들을 묶어서 저장하는 형태로 구현되는데, 이는 주로 비슷한 값들을 동시에 조회하는 경우가 많다는 점에서 착안된 것이다. 여기서 비슷한 값들은 물리적으로 인접한 장소에 저장되어 있는 데이터를 말한다.

클러스터드 인덱스는 테이블의 기본 키에 대해서만 적용되는 내용이다. 즉, 기본 키의 값이 비슷한 레코드끼리 묶어서 저장하는 것을 클러스터드 인덱스라고 표현한다. 클러스터드 인덱스에서는 기본 키의 값에 의해 레코드의 저장 위치가 결정되며, 기본 키의 값이 변경되면 그 레코드의 물리적인 저장 위치 또한 변경되어야 한다. 그렇기 때문에 기본 키를 신중하게 결정하고 클러스터드 인덱스를 사용해야 한다.

클러스터드 인덱스는 테이블 당 한 개만 생성할 수 있다. 기본 키에 대해서만 적용되기 때문이다. 이에 반해, 논클러스터드 인덱스는 테이블 당 여러 개를 생성할 수 있다.

 

[Index를 사용하면 좋은 경우 / 사용을 피해야 하는 경우]

• 사용하면 좋은 경우

  1. WHERE 절에서 자주 사용되는 칼럼
  2. 외래 키가 사용되는 칼럼
  3. 조인에 자주 사용되는 칼럼

• 사용을 피해야 하는 경우

  1. 데이터 중복도가 높은(카디널리티가 낮은) 칼럼 (e.g) 성별

  2. DML이 자주 일어나는 칼럼

     e.g) INSERT - 기존 블록에 여유가 없을 때, 새로운 데이터가 입력된다. 새로운 블록을 할당받은 후, 키를 옮기는 작업을 수행하므로 많은 REDO가 유발된다.

 

 

 

 

 

 

 

Reference

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Database#index

https://gyoogle.dev/blog/computer-science/data-base/Index-.html