[DB] 데이터베이스 인덱스에 관하여

 

 

인덱스란?

인덱스는 데이터베이스의 검색 속도를 향상시키기 위한 자료구조이다. 인덱스는 데이터를 빠르게 찾을 수 있도록 도와준다.

특정 컬럼에 대해 생성되며, 이 인덱스는 해당 컬럼의 값과 해당 레코드가 저장된 물리적 위치 정보를 가진다. 쿼리를 실행하면, 테이블 전체를 스캔하는 대신 인덱스를 먼저 확인하여 필요한 데이터의 위치를 빠르게 찾아낼 수 있다. 

 

인덱스의 종류

인덱스는 2가지로 분류할 수 있다. Clustered Index와 Non-clustered Index이다. 

 

Clustered Index

클러스터드 인덱스는 물리적으로 데이터를 인덱스 키 값의 순서에 따라 연속된 위치에 저장한다.

특징:

1. 테이블당 하나만 존재 가능
   하나의 테이블에는 하나의 클러스터드 인덱스만 가질 수 있다. 물리적 데이터는 한 가지 기준으로만 정렬할 수 있기 때문이다. 
2. 실제 데이터 행이 인덱스 순서대로 물리적으로 재정렬됨
   클러스터드 인덱스가 생성되면 테이블의 모든 데이터 행은 인덱스 키 값에 따라 물리적으로 재정렬이 된다. 기존 데이터들 사이에 새로운 데이터를 삽입이 가능하다. 
3. 주로 기본 키(Primary Key)에 자동 생성됨
   대부분의 RDMBS에서는 기본 키를 정의하면 해당 키에 대해 자동으로 클러스터드 인덱스가 생성된다. 기본 키는 고유하고 null이 아니라는 특성을 가지기 때문에 데이터 정렬의 기준으로 적합하기 때문이다. 
4. 리프 노드가 실제 데이터 페이지를 저장
   클러스터드 인덱스는 B+Tree 구조로 구현되기 때문에, B+Tree의 특성을 따른다. B+Tree는 리프 노드에 실제 데이터를 저장한다. 

장점:

1. 인덱스 순서가 물리적으로 연속되어 정렬되어있기 때문에, 범위 검색에 매우 효율적이다. 
2. 연속된 데이터 접근 시 I/O 비용이 적다. 한 번의 디스크 읽기 작업으로 관련 레코드를 메모리로 가져올 수 있어 성능 이 향상된다.
3. 인덱스를 기준으로 정렬을 요청하는 쿼리에 대해 추가적인 정렬 없이 바로 결과를 반환할 수 있다. 

단점:

1. 데이터 삽입, 수정 시 물리적 재정렬이 필요하다. 이는 배열의 삽입, 삭제의 단점과 동일하다. 

 

Non-clustered Index

넌클러스터드 인덱스는 실제 데이터와 별도로 인덱스 값과 해당 데이터를 가리키는 포인터를 저장한다. 

실제 데이터 테이블은 있고, 인덱스에 따라 각각의 B+Tree가 구현된다. 구현된 B+Tree는 보조기억장치에 저장되고, 해당 인덱스를 메모리에 캐싱해 사용한다. 

넌클러스터드 인덱스는 클러스터드 인덱스 or 힙테이블과 함께 사용한다. 

특징:

1. 테이블당 여러 인덱스가 존재 가능
   각각 다른 열을 기준으로 인덱스를 만들 수 있기 때문이다.
2. 실제 데이터 행은 물리적으로 재정렬되지 않음
   넌클러스터드 인덱스가 생성되어도 테이블의 데이터 행은 원래 순서를 유지한다. 대신 별도의 인덱스 구조가 생성된다. 
3. 보조 인덱스로 사용
   일반적으로 검색 성능을 향상시키기 위해 자주 조회되는 열에 생성한다. 
4. 리프 노드가 데이터 포인터를 저장
   비클러스터드 인덱스의 리프 노드는 실제 데이터 페이지가 아닌, 데이터 행을 가리키는 포인터나 행 식별자(RID)를 저장한다. 

장점:

1. 데이터의 물리적 순서를 변경하지 않아 삽입, 수정이 비교적 빠르다.
2. 하나의 테이블에 여러 인덱스를 생성할 수 있어 다양한 검색 조건에 최적화할 수 있다. 

단점:

1. 클러스터드 인덱스에 비해 범위 검색 성능이 상대적으로 떨어진다. 
2. 데이터를 찾기 위해 인덱스를 검색한 후, 다시 실제 데이터에 접근하는 추가 작업이 필요하다. 
3. 인덱스 자체가 추가 저장 공간을 차지하므로 저장 공간 오버헤드가 발생한다. 

 

Clustered Index vs Non-Clustered Index

두 인덱스에 가장 큰 차이점은 리프노드에 저장된 데이터가 실제 데이터인지, 실제 데이터를 가리키는 포인터인지의 차이다. 

넌클러스터드 인덱스의 데이터 조회 과정

1. SQL Server는 넌클러스터드 인덱스의 루트 노드에서 시작
2. 찾고자 하는 키 값인 1052이 키 값 1024보다 크거나 같은지 확인 ➡️ true
3. 루트 노드의 다음 키 값 1052와 비교 ➡️ true
4. 루트 노드의 다음 키 값 1074와 비교 ➡️ false
5. 이전 키 값인 1052를 통해 중간 노드로 이동
6. 위 2~5 과정을 반복해 리프노드로 이동
7. 리프 노드에서 1052를 찾을 때까지 탐색
8. 1052를 찾으면 이와 연결된 포인터 값을 통해 실제 테이블을 조회
   1. 클러스터드 인덱스 테이블이라면, 넌클러스터드 인덱스 ➡️ 클러스터드 인덱스 ➡️ 실제 데이터
   2. 힙 테이블이라면, 넌클러스터드 인덱스 ➡️ 힙 테이블(RID 사용)  ➡️ 실제 데이터

클러스터드 인덱스의 데이터 조회 과정

1. SQL Server는 클러스터드 인덱스의 루트 노드에서 시작
2. 클러스터드 인덱스의 루트 노드부터 시작하여 B+-트리 구조로 탐색
3. 중간 노드들을 거쳐 내려가며 키 값 1052가 어느 범위에 속하는지 판단
4. 데이터 페이지(리프 노드)에 도달하면, 페이지 내에서 키 값이 1052와 일치하는 행을 탐색
5. 데이터 페이지 내의 행들은 클러스터링 키 값으로 정렬되어 있기 때문에 이분 탐색을 사용하여 찾음
6. 일치하는 행을 찾으면 해당 데이터를 직접 반환
7. 범위 탐색의 경우, 데이터가 키 값 순서로 정렬되어 있어 연속된 페이지를 순차적으로 읽음

💡 인덱스의 자료구조에는 대표적으로 해시 테이블과 B+Tree가 있다.
해시 테이블은 DB 인덱스를 사용해 O(1)의 시간복잡도로 빠른 검색을 할 수 있지만, 부등호 연산이 자주 사용되는 데이터베이스 검색에는 적합하지 않다. 
B+Tree는 범위 검색에 효율적이고,  B+Tree의 키 값 순서대로 트리를 순회하면 자동으로 정렬된 결과를 얻을 수 있다. 

💡 언제 클러스터드 인덱스를 사용하고 언제 힙 테이블을 사용할까?
클러스터드 인덱스는 인덱스 키 값에 따라 정렬되어 있고 힙 테이블은 특별한 순서가 없이 저장되어 있다. 
넌클러스터드 인덱스를 통해 클러스터드 인덱스에 접근할 경우 클러스터드 인덱스의 정렬 순서로 접근하지 않고 무작위로 접근한다. 그럼 클러스터드 인덱스의 정렬이 필요 없다고 생각할 수도 있다. 
하지만 데이터베이스 엔진이 "키 조회 순서 정렬" 최적화를 통해 클러스터드 인덱스 값을 정렬 후 접근하여 성능 이점을 얻거나 테이블 재구성이 힙 테이블보다 효율적이고 단편화에 더 강하다. 
힙 테이블은 대량 데이터 삽입이 주요 작업인 경우 유리하다. 이는 한 번 삽입된 후 거의 수정되지 않고 테이블 재구성이 필요 없을 때 클러스터드 인덱스보다 효율적이다. 

 

왜 넌클러스터드 인덱스를 사용할까? 

넌클러스터드 인덱스는 여러 인덱스를 사용할 수 있다. 각 연산에 따라 적합한 인덱스가 있을 것이다. 

넌클러스터드 인덱스는 데이터를 매번 물리적으로 재배열하지 않고도 여러 연산을 최적화할 수 있는 유연성을 제공한다. 

여러 인덱스는 모두 실제 하나의 테이블과 연결되어 있다. 각 인덱스를 따라 하나의 실제 테이블을 정렬된 것처럼 사용할 수 있다. 

 

 

 

인덱스의 단점

1. 인덱스는 추가적인 디스크 공간이 필요하다. 테이블이 커질 수록 인덱스도 커진다.
2. INSERT, UPDATE, DELETE 작업마다 관련 인덱스를 모두 업데이트해줘야 한다. 인덱스가 많을 수록 DML 작업의 성능이 떨어진다. 
3. 인덱스 단편화를 방지하기 위해 테이블의 재구성이 추가로 필요하다. 
4. 잘못된 인덱스가 있다면 조회가 더 오래 걸린다.  

 

References

https://www.sql-datatools.com/2017/02/nonclustered-index-on-clustered-index-sql-server-2016.html?m=0

Nonclustered Index on Clustered Index in SQL Server

https://www.linkedin.com/pulse/heap-vs-index-organized-table-pranav-pandey

Heap vs Index organized table

https://josipmisko.com/posts/clustered-vs-non-clustered-index

Clustered vs Nonclustered Index: What are the main differences? – Josip Miskovic