인덱스 (1) - 인덱스의 자료구조, 전략

들어가며

기술 서적의 경우 모르는 개념을 다시 공부할 때 활용할 수 있도록 목차, 즉 인덱스를 사용하곤 한다.

데이터베이스에서도 테이블의 데이터를 빠르게 찾아낼 수 있도록 인덱스라는 개념이 존재한다.

 

관계형 DB는 일반적으로 인덱스를 B+ Tree를 사용해 구현한다. 흔히 사용하는 MySQL의 스토리지 엔진 InnoDB에서는 B+ Tree를 사용하고 있다.

(뒤에서 설명하겠지만 B- Tree를 좀 더 개선한 자료구조가 B+ Tree라고 할 수 있다.)

 

인덱스의 자료구조

B-Tree

B-Tree는 BST(이진탐색트리)를 발전시킨 형태로 트리의 균형이 항상 잡혀있으며 자식 노드를 2개 이상 가질 수 있다. 즉, 3개나 그 이상의 자식을 가지는 것도 가능하다.

 

또한 모든 노드에 키(데이터)와 포인터가 존재하며, 각 노드는 항상 내부적으로 오름차순 정렬된 상태로 저장된다.

 

B+Tree

B+Tree는 B-Tree를 범위 검색, 순차 탐색이 더 용이하도록 개선한 자료구조로서, 모든 실제 데이터는 리프 노드에만 저장되어 있고 각 레벨의 노드끼리는 양방향 연결리스트를 통해 연결되어 있다.

 

또한 리프 노드 인덱스가 Clustered Index, Non-Clustered Index 전략 둘 중 어느 쪽을 따르는지에 따라 형태가 조금 다르다. 이는 이어서 설명하도록 한다.

 

B+Tree는 범위 검색, 순차 탐색은 B-Tree보다 효율적이지만 항상 데이터가 저장된 리프 노드까지 내려가는 오버헤드가 발생하므로 단일 데이터 검색은 내부 노드에 데이터가 있는 B-Tree가 더 효율적일 수 있다.

 

이어서 인덱스 전략에 대해서 알아보도록 하겠다.

 

인덱스 전략

전략들은 MySQL InnoDB에서의 Default인 B+Tree를 기준으로 설명한다.

 

Full Table Scan

일반적으로 MySQL에서는 1페이지(16kb)의 단위로 데이터를 묶어서 저장한다.

Full Table Scan은 인덱스 전략(해당 전략에서 인덱스를 사용하진 않는다.)의 일종으로 위 그림과 같이 각 페이지 내부 데이터들을 순차적으로 탐색하는 방법이다.

 

이는 다음과 같은 상황에서 적용된다.

 

1. 적용 가능한 인덱스가 없는 경우

2. 인덱스 처리 범위가 넓은 경우

3. 크기가 작은 테이블에 액세스하는 경우(이 경우 인덱스를 사용하게 되면 오히려 접근 비용이 늘어날 수 있다.)

 

Clustered Index

Clustered Index는 인덱스 순서에 맞춰 디스크의 데이터의 순서를 일치시키는 전략이다. 따라서 해당 인덱스는 한 테이블에 하나만 존재할 수 있다. 또한 리프 노드들이 실제 데이터를 갖고 있다.

Clustered Index는 PK가 적용된 컬럼을 기준으로 적용되고 다음 우선순위로는 unique와 not null 조건을 만족하는 컬럼을 기준으로 적용된다.

 

Non-Clustered Index

Non-Clustered Index는 인덱스의 순서와 디스크 순서가 일치하지 않는 전략으로, 리프 노드들은 실제 데이터를 가지고 있는 것이 아니라 실제 데이터가 위치한 데이터 페이지의 위치를 가리키기만 한다. 또한 별도의 인덱스 페이지가 생성되므로 추가 공간이 필요하고 한 테이블에 여러 개가 존재할 수도 있다.

Non-Clustered Index는 unique 제약조건 적용 시 자동으로 생성되며, 직접 인덱스를 생성하는 경우에도 Non-Clustered Index로서 생성된다.

 

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

1. 카디널리티가 높은(중복도가 낮은) 컬럼

 

2. WHERE, JOIN, ORDER BY절에 자주 사용되는 컬럼

인덱스는 조건 절이 없는 쿼리에는 사용되지 않는다.

 

3. 삽입, 삭제, 갱신이 자주 발생하지 않는 컬럼

이러한 컬럼에 인덱스를 적용하게 되면 인덱스를 수시로 갱신하게 되면서 오히려 많은 오버헤드를 얻게 될 수 있다.

 

4. 규모가 작지 않은 테이블

규모가 일정 수준 이하인 테이블에서는 오히려 Full Table Scan이 더 빠를 수 있다.

 

 

DB에서 Red-Black Tree가 아닌 B-Tree/B+Tree를 사용하는 이유?

 

1. 두 자료구조 모두 일반적으로  O(lgN)의 시간복잡도로 탐색이 가능하지만, RBT는 자식을 두 개밖에 가질 수 없다.

 

2. DB의 데이터들은 일반적으로 보조 메모리(디스크)에 저장되고, 사용할 데이터만 메인 메모리에 올려서 사용하게 된다. 따라서 접근 속도가 훨씬 느린 보조 메모리에 접근하는 횟수가 적을수록 좋을 것이라는 결론에 도달할 수 있다.

 

위 2가지 정보를 바탕으로 저장공간을 효율적으로 사용할 수 있고, 가장 깊은 depth에 있는 데이터에도 단 3번의 이동만으로 접근이 가능한 B-Tree가 RBT보다 훨씬 DB의 자료구조로서 실용적이다.

 

이에 대한 예시로 101차 B-Tree의 경우 최소 depth가 3일 때 최소 26만 ~ 최대 1억 개의 데이터를 한 트리에 담을 수 있다고 한다.

 

참조

https://youtu.be/edpYzFgHbqs?si=4P3ABGHNgg_zcl1w

https://youtu.be/liPSnc6Wzfk?si=GO6ocY7ivysxAN2m

https://dba.stackexchange.com/questions/204561/does-mysql-use-b-tree-btree-or-both https://bugoverdose.github.io/computer-science/btree-index-and-hash-index/

https://www.sqlservercentral.com/articles/nonclustered-index-structure