1. 인덱스(Index)란?
인덱스는 데이터베이스에서 특정 컬럼의 값과 해당 값이 위치한 레코드의 주소를 매핑하여 빠르게 데이터를 찾을 수 있도록 해주는 "자료구조"이다. 즉, 컬럼의 실제 값이 키로 쓰이고 해당 값이 실제 테이블의 어느 위치에 있는지 나타내는 값을 가지고 있는 키-값 (key-value) 형식의 구조이다. 이 키-값 구조를 이용하여 특정 데이터가 원래 테이블의 어느 위치에 있는지 빠르게 찾을 수 있다. 인덱스는 디스크 안에 저장되며 이를 위해 추가적인 공간을 필요로 한다. 인덱스는 원본 테이블의 데이터와는 독립적이다.
2. 인덱스의 원리와 작동 과정
인덱스의 키들은 처음 저장될 때 특별한 순서로 정렬되어 저장된다. where문으로 특정 컬럼을 스캔할 시 해당 컬럼이 인덱싱 되어 있다면 인덱스 안에 정렬되어 저장되어 있는 키를 찾고 키에 매핑된 값으로 실제 테이블에서 인덱스 키에 해당하는 값의 위치를 빠르게 찾을 수 있다. 이를 통해 데이터 조회시 성능을 향상시킬 수 있는 것이다.
2-1. 인덱스의 생성 과정
인덱스 생성 과정의 일반적인 흐름은 다음과 같다.
- 데이터 스캔: 인덱스를 생성할 컬럼의 데이터를 스캔한다.
- 데이터 정렬: 스캔한 데이터를 특정한 순서로 정렬한다. 대부분의 인덱스에서는 데이터가 오름차순 또는 내림차순으로 정렬된다.
- 인덱스 구조 생성: 정렬된 데이터를 기반으로 인덱스 구조를 생성한다. 예를 들어, B-tree 인덱스의 경우, 정렬된 데이터를 사용하여 트리 구조를 만든다.
- 인덱스 저장: 생성된 인덱스 구조를 디스크에 저장한다.
2-2. 인덱스의 변경 과정
인덱싱한 컬럼에 데이터 변경이 일어나면 인덱스도 그에 따라 변경 된다. 인덱스의 업데이트 과정은 데이터베이스 관리 시스템(DBMS)에 의해 자동으로 처리된다.
데이터 삽입
새로운 레코드가 테이블에 추가될 때, 해당 레코드의 인덱싱된 컬럼 값에 대한 새로운 인덱스 항목이 생성되어 인덱스 구조에 추가된다.
데이터 수정
인덱싱된 컬럼의 값이 변경될 경우, 해당 값의 인덱스 항목도 업데이트되어야 한다. 예를 들어, B-tree 인덱스의 경우, 수정된 값의 위치가 트리 내에서 변경될 수 있다. 특정 데이터베이스는 기존의 데이터 항목을 변경하는 대신 새로운 데이터 항목을 인덱스에 추가한다. 이 때 기존의 데이터 항목은 쓰지 않는 상태로 나둔다. 이런 방식은 순차적인 데이터 쓰기 작업만 하기 때문에 성능이 향상된다.
데이터 삭제
레코드가 테이블에서 삭제될 때, 해당 레코드의 인덱싱된 컬럼 값에 대한 인덱스 항목도 인덱스 구조에서 제거된다. 특정 데이터베이스에서는 위 데이터 수정에서 말한 경우와 마찬가지로 해당 데이터를 실제로 삭제하지 않고 사용하지 않는 상태로 변경하는 soft-delete를 사용하기도 한다. 이 방식은 삭제를 위한 디스크 I/O 작업을 하지 않기 때문에 성능이 향상된다.
이러한 인덱스의 업데이트 작업은 추가적인 오버헤드를 발생시킨다. 따라서, 빈번한 데이터 변경이 발생하는 테이블에서는 인덱스의 수와 종류를 신중하게 결정해야 한다. 너무 많은 인덱스는 데이터의 삽입, 수정, 삭제 성능을 많이 저하시킬 수 있다.
3. 인덱스에 사용되는 자료구조
인덱스에 사용되는 자료구조는 DBMS의 종류에 따라 다양하다. B-Tree (Balanced Tree)와 B+Tree, Hash Index, Bitmap Index 등이 사용된다. Tree 자료구조를 사용할 때는 Tree의 각 노드들에 키와 데이터를 담아 이용한다. 이 글에서는 대표적으로 많이 사용되는 B-Tree와 B+Tree에 대해 알아본다.
3-1. B-Tree
기본적인 이진 탐색 트리에서는 균형을 유지하지 않는다. 따라서 최악의 경우에는 아래처럼 트리가 한 쪽으로 치우칠 수 있어서 검색, 삽입, 삭제 모두 O(n)의 시간 복잡도를 가질 수 있다.
B-Tree는 Balanced Tree라고도 불린다. 이진 탐색 트리와는 다르게 트리가 한쪽으로 치우치지 않는다. 왜냐하면 모든 리프노드(자식 노드가 없는 노드)들의 depth가 똑같이 유지되기 때문이다. 이 때문에 어떤 데이터를 찾든지 O(log n)의 시간복잡도가 유지된다.
B-Tree는 한 노드에 여러개의 키(실제 테이블의 데이터)를 가질 수 있다. 또 각 노드는 가지고 있는 키의 개수보다 한개 더 많은 자식 노드를 가질 수 있다. 노드의 키의 개수가 x개라면 x+1개의 자식 노드를 가질 수 있는 것이다.
3-1-1. B-Tree가 리프 노드들의 뎁스를 유지하는 방법
B-Tree는 아래와 같은 과정을 거치며 뎁스를 유지한다.
- 노드 분할: 데이터가 새로 들어왔는데 모든 노드들이 꽉 찼다면 꽉 찬 노드를 두 개의 노드로 분할하고, 중앙에 위치한 키를 상위 노드를 만들어 올린다.
- 상위 노드로 올리기: 중앙 키가 상위 노드로 올라갈 때, 상위 노드 역시 꽉 차 있을 수 있다. 이런 경우에는 상위 노드에서도 또 다시 노드 분할을 수행한다.
- 재귀 또는 반복: 상위 노드로 계속 올라가면서 필요한 경우 분할을 반복한다. 이 과정은 루트 노드에 이를 때까지 계속될 수 있으며, 루트 노드가 분할될 경우 트리의 높이가 하나 증가하게 된다.
이러한 노드 분할 과정을 통해 B-Tree는 항상 균형을 유지하게 된다.
3-2. B+Tree
B+Tree는 B-Tree와는 다르게 데이터를 리프 노드에서만 가지고 있다. 리프 노드가 아닌 노드들은 키만 가지고 있을 뿐이다. 리프 노드가 상위 노드에 있는 키도 모두 가지고 있고 키에 매핑되는 데이터도 모두 가지고 있다. 이 리프 노드들은 서로 더블 링크드리스트로 연결되어 있다.
상위 노드의 키는 리프 노드에도 반드시 존재하므로, 어떤 키를 찾을 때 리프 노드까지 내려가면 그 키와 연관된 데이터를 항상 찾을 수 있다.상위 노드(내부 노드)에 있는 키들은 리프 노드까지의 탐색 경로를 결정하는데 사용될 뿐이다.
3-2-1. B+Tree가 B-Tree에 비해 가지는 이점
특정 데이터를 찾는데 B+Tree나 B-Tree가 걸리는 시간복잡도는 같다. 둘 다 높이 h에 따라 노드를 탐색하는 데 O(h)의 시간이 걸리고, 각 노드 내에서 이진 탐색을 통해 키를 찾는 데 O(log d)의 시간이 걸린다. 여기서 높이 h는 키의 개수 N에 따라 달라진다. 결론적으로 둘 다 시간 복잡도는 O(log N)이다. 그렇다면 B+Tree는 어떤 경우에 B-Tree보다 효율적일까? 그것은 바로 데이터를 풀스캔할 때이다. 데이터를 풀스캔하는 경우 B+Tree는 리프 노드를 처음부터 선형탐색하면 된다. 바로 리프노드에 모든 데이터가 다 들어있고 링크드리스트로 다 이어져 있기 때문이다. 하지만 B-Tree는 각 노드들에 데이터가 다 분산되어 저장돼 있으므로 풀스캔시 모든 노드들을 순회해야 하므로 B+Tree보다 느리다.
