인덱스란?
대량의 테이블에서 소량의 데이터를 검색할 때 속도를 향상시키는 자료구조입니다. 인덱스 기준으로 정렬하면 테이블 검색과 정렬 속도와 그에 따른 성능을 향상시킨다는 장점이 있습니다. 반면, 인덱스를 관리하는 데 추가적인 쓰기 작업과 데이터베이스의 약 10%에 해당되는 저장공간이 필요하다는 단점이 있습니다.
어떤 경우에 인덱스를 사용하면 좋을까요?
조금 극단적으로 1개의 데이터가 있는 테이블과 100만 개의 데이터가 있는 테이블이 있다고 했을 때, 100만 개의 데이터가 있는 테이블과 달리 1개의 데이터가 있는 테이블은 풀 스캔이 더욱 효율적입니다. 100만 개의 테이블일 때 인덱스를 통해 읽어 들이는 양이 많다면 디스크 I/O가 많이 발생하기 떄문에 처리 시간이 늦어질 수도 있습니다.
또한, DML 연산을 수행할 때 인덱스는 정렬되어 있는 상태를 유지한다는 특징을 가집니다. UPDATE와 DELETE 연산 시 기존 인덱스를 삭제하지 않고 '사용하지 않음' 처리를 해줍니다. INSERT와 UPDATE 연산 시 새로운 데이터에 대한 인덱스를 추가하며 정렬 연산이 이루어집니다.
결론적으로 규모가 작지 않은 테이블에서 DML 연산이 자주 발생하지 않는 칼럼, JOIN, WHERE이나 ORDER BY에 자주 사용되는 칼럼, 데이터의 중복도가 낮은 칼럼, 유니크한 값을 가지고 있는 칼럼 등의 경우에 인덱스를 사용하면 좋다는 것을 알 수 있습니다.
클러스터드 인덱스(Clustered Index)란?
데이터가 테이블에 물리적으로 저장되는 순서를 정한 인덱스입니다.
PK 설정 시 해당 칼럼으로 클러스터드 인덱스가 만들어집니다. PK의 특징과 같이, 테이블 당 1개씩만 허용되며 DML 연산 시 항상 정렬 상태를 유지하는 특징을 가지고 있습니다. 물리적으로 정렬되어 있어서 검색 속도는 빠르지만 DML 연산은 느립니다.
클러스터드 인덱스는 트리로 저장되어, Root 페이지와 Leaf 페이지(= 데이터 페이지)로 구성됩니다. 실제 행 데이터를 해당 열로 정한 후에 Root 페이지를 만들게 됩니다. Leaf 페이지에는 실제 데이터를, Root 페이지에는 Leaf 페이지의 주소로 구성되어 데이터를 검색할 때 Root 페이지를 통해 Leaf 페이지의 실제 데이터에 접근합니다.
DML 연산이 느려지는 이유는 리프 페이지가 모두 차있을 때 새로운 데이터가 들어오면 페이지 분할이 일어나며 데이터 페이지 전체를 다시 정렬해야 하기 때문입니다.
넌 클러스터드 인덱스(Non-Clustered Index)란?
클러스터드 인덱스와 달리 데이터의 행에 독립적이며 인덱스가 데이터에 함께 저장되는 것이 아니라 별도의 장소에 저장됩니다. 또한, 하나의 테이블에서 여러 개의 넌 클러스터드 인덱스를 설정할 수 있습니다.
인덱스 페이지의 Leaf 페이지가 Index로 구성한 칼럼과 위치 포인터(RID)로 구성됩니다(= Leaf 페이지가 정렬됨). 즉, 인덱스로 Leaf 페이지에 접근하면 Leaf 페이지의 RID 정보로 실제 데이터에 접근하게 됩니다(= 실제 데이터는 정렬되지 않음).
클러스터드 인덱스보다 거쳐야 하는 단계가 많아 검색 속도는 비교적 느리지만, DML 연산은 비교적 빠릅니다.
인덱스 알고리즘, B-Tree
데이터베이스의 인덱싱 알고리즘 가운데 가장 일반적으로 사용되는 자료구조로 Balanced-Tree를 의미합니다.
노드 안 데이터는 정렬된 상태로 구성되며 항상 양쪽 자식의 밸런스를 유지하므로, 리프 노드가 모두 같은 레벨에 있는 특징을 가집니다. 따라서 검색에 걸리는 시간이 일정하다는 장점을 지닙니다: O(logN).
노드 하나에 여러 데이터가 저장될 수 있으며 데이터와 데이터 사이의 범위에 따라 자식 노드를 가집니다. 이때 자식 노드는 부모 노드의 (key 개수 + 1) 만큼의 노드 개수를 가지게 됩니다.
왜 B-Tree를 사용할까?
- 항상 정렬된 상태를 유지해서 부등호 연산에도 빠르게 탐색할 수 있다
- 하나의 노드에 여러 데이터를 담을 수 있어 빠른 메모리 접근이 가능하고 참조 포인터가 적다
탐색 시간이 가장 빠른 해시 테이블과 또 다른 밸런스 트리 중 RedBlack-Tree와 비교해보겠습니다.
해시 테이블에서 단 하나의 데이터를 탐색하는데 걸리는 시간이 O(1)입니다. 하지만, 우리는 데이터베이스에서 등호뿐 아니라 부등호도 사용할 수 있습니다.
즉, 해시 테이블에서는 값이 정렬되어 있지 않아서 특정 기준보다 작거나 큰 값을 찾기에 매우 비효율적입니다.
RedBlack-Tree는 하나의 노드에 하나의 데이터 요소만을 저장하지만, B-Tree는 하나의 노드에 여러 개의 데이터 요소를 저장합니다. 자식 노드로 접근할 때 참조 포인터로 접근을 하게 되는데 하나의 노드가 가지는 데이터 개수가 많아질수록 포인터 개수가 줄어들어서 B-Tree가 더 효율적입니다.
