[데이터베이스] 인덱스(Index)

인덱스는 데이터를 빠르게 찾을 수 있는 하나의 장치이다.

B-트리

인덱스는 보통 B-트리라는 자료 구조로 이루어져 있다. 이는 루트 노드, 리프 노드, 브랜치 노드로 나뉜다.

예를 들어 설명하자면 다음 그림과 같다.

키가 "57"인 데이터를 검색하는 과정이라고 가정하자.

트리 탐색은 맨 위 루트 노드부터 탐색이 일어나며, 브랜치 노드를 거쳐 리프 노드까지 내려온다.

각 노드의 시작부터 57보다 크거나 같은 수를 만날 때까지 정렬된 값을 기반으로 탐색한다.

즉, 루트 노드의 경우 39,83을 거치고, 그 밑의 브랜치 노드로 내려와서 46,53,57을 거치고, 그 밑의 리프 노드로 내려와서 55,57을 거쳐 원하는 데이터를 찾는다.

루트 노드에서 시작해서 리프 노드까지 도달해서 찾은 57을 가리키는 데이터 포인터를 반환한다.

 

인덱스가 효율적인 이유와 대수 확장성

인덱스가 효율적인 이유는 효율적인 단계를 거쳐 모든 요소에 접근할 수 있는 균형 잡힌 트리 구조와 트리 깊이의 대수확장성 때문이다.

대수확장성이란, 트리 깊이가 리프 노드 수에 비해 매우 느리게 성장하는 것을 의미한다. 기본적으로 인덱스가 한 깊이씩 증가할 때마다 최대 인덱스 항목의 수는 4배씩 증가한다.

트리의 대수확장성

 위 표처럼 트리 깊이가 10일 때, 약 100만개의 레코드를 검색할 수 있다.

 

인덱스를 만드는 방법

인덱스를 만드는 방법은 DBMS마다 다르다. 대표적으로 MySQL을 기준으로 설명하겠다!

MySQL

MySQL의 경우 클러스터형 인덱스와 세컨더리 인덱스가 있다. 

클러스터형 인덱스는 테이블당 하나를 설정할 수 있다. Primary key 옵션으로 기본키로 만들어서 클러스터형 인덱스를 생성하거나, 기본키로 만들지 않고 unique not null 옵션을 붙여서 클러스터형 인덱스를 생성할 수도 있다. 

위 두가지 옵션이 동시에 존재하는 경우엔 primary key 옵션이 붙은 필드가 우선적으로 클러스터형 인덱스가 된다.

테이블의 데이터는 클러스터형 인덱스를 기준으로 자동 정렬된다. (MySQL 의 경우 오름차순 정렬)

출처 : https://hudi.blog/db-clustered-and-non-clustered-index/

세컨더리 인덱스는 create index ... 명령어를 이용해서 생성할 수 있다. 클러스터형 인덱스와 달리, 물리적으로 실제 테이블을 정렬하진 않는다. 다만, 정렬된 별도의 인덱스 페이지를 생성하고 관리한다. 또, 한 테이블에 여러 개의 세컨더리 인덱스가 존재할 수 있다. 

세컨더리 인덱스는 보조 인덱스로, 여러 개의 필드 값을 기반으로 쿼리를 많이 보낼 때 생성해야 하는 인덱스이다.

예를 들어, age라는 하나의 필드만으로 쿼리를 보낸다면 클러스터형 인덱스만으로 충분하다. 하지만, age, name, email 등 다양한 필드를 기반으로 쿼리를 보낼 때는 세컨더리 인덱스를 사용해야 한다. 

출처 : https://hudi.blog/db-clustered-and-non-clustered-index/