1. 인덱스란?

인덱스란 데이터베이스에서 조회 성능을 높히기 위해 추가적인 쓰기 작업과 저장공간을 활용하는 자료구조이다.

수천만에서 억에 달하는 데이터 중 내가 원하는 데이터를 처음 부터 끝까지 찾자면 답이 없다. 인덱싱은 다양한 방법을 통해 빠르게 데이터를 찾는 것을 돕는 것이 목적이다.

비유 하자면, 보통 책의 맨 뒤에 있는 "찾아보기"를 생각하면 된다. 책의 내용물은 데이터 파일에 해당하고, 찾아보기에 적혀 있는 페이지 번호는 데이터 파일에 저장된 "레코드 주소"로 비유할 수 있겠다. 찾아보기는 ㄱ, ㄴ, ㄷ 순으로 정렬 되어 있고, 단어들이 오름차순으로 기재되어 있다.

1.1 인덱스를 쓰면 왜 빠른가?
+ 구현체별 인덱스 종류

인덱싱을 걸면 왜 빠른건지? 그리고 "추가적인" 공간과 쓰기 작업이란 무엇인지 살펴보자.

밸런스드 트리의 형태

인덱스도 결국 자료구조인데, 어떻게 데이터를 저장하길래 빠른 것일까?
종류가 워낙 다양하지만 보통은 내부적으로 밸런스형 트리 구조 형태를 사용한다.
밸런스형 트리는 전체적인 Depth를 다양한 규칙을 통해 조절해 놓은 트리 구조로, 평균적인 탐색 속도가 빠르다. 왜냐하면, 정렬된 트리 구조에서의 탐색 횟수는 결국 원하는 데이터가 위치한 곳의 Depth와 직결되기 때문이다. 예를 들어 AVL이나 BTree류, 레드 블랙 트리 등이 여기에 속한다. (사실 밸런스형 트리라는 표현은 편의상 쓴 표현이니 주의)
또한 정렬된 트리 구조이기 때문에 범위 검색에 유리하다. MySQL은 기본적으로 B-Tree를 활용하고, PostgreSQL은 B+Tree를 사용하는 것으로 알려져 있다.
이들은 정렬된 형태의 밸런스드 트리이다. 높이가 균일하고, 데이터들이 정렬 되어 있다.
정렬된 트리의 탐색 시간복잡도는 노드의 데이터 갯수가 M일 때 O(lon_M(N))이다. 왜냐하면, 노드 안에서 데이터를 갯수만큼 비교하고, 이진탐색처럼 그 갯수만큼 연산을 스킵한다.
간단하게 증명을 요약하자면, 어떤 데이터가 위치한 depth가 h일 때, M개의 노드를 살펴보고 -> 자식 노드로 이동하는 과정을 h회 만큼 진행한다. 따라서, M^h = N 이고, O(h) = O(log_M(N))이다.

혹은 Fractal-Tree, Merge-Tree등 정말 생소한 트리를 사용하는 경우도 있다.

결론적으로 트리형을 사용하는 이유는 빠른 범위에 있다. 다른 형태로 Hash형태가 있는데, HashTable에 대한 이해가 있다면 알겠지만, 기본적으로 범위 탐색이 어렵다.
3월 부터 6월 자료 찾아주세요!!!!! 라는 질의를, 해쉬 테이블을 통해 처리한다고 상상해보면 끔찍하다.

추가적인 쓰기 작업은 예상되겠지만, 트리의 밸런스를 맞추고, 정렬하는 과정에서 발생한다. 그리고 트리의 노드들을 구성하면서 추가적인 공간을 쓰게 된다. 예를 들어 B+Tree의 경우 리프노드에 실제 데이터 전체가 있는데, (혹은 실제 데이터를 가리키는 포인터) 중간 노드들을 표현해야 하기 때문에 노드 갯수가 실제 데이터 갯수의 2배 가까이 된다.

해시의 형태

해시형 자료구조로도 구현할 수 있다.

자료구조 해시형 Map을 생각해보면 간단하다. key값에 해당하는 Value를 해시 테이블 통해 아주 빠르게 찾아낼 수 있다. 대신 해시 테이블을 사용함으로써 버켓들을 표현하는 과정에서 추가적인 저장 공간이 추가적으로 쓰이고, 버켓을 찾고, 그 안에서 동등성을 비교해야 하므로, 추가적인 쓰기 작업이 필요하다.

보통 Hash형이 쓰이지 않는 경우는 앞서 언급한 것 처럼 범위 검색이 어렵기 때문이다. 또한 어떤 칼럼의 Prefix만 일치하는 상황 또한 검색하기 어렵다. 유연성이 떨어지는 느낌..

1.2 클러스터 여부

바로 앞에서 인덱스가 빠른 이유를 설명하며 내부 자료구조 구현체를 설명했다. 꼭 분류하려던건 아닌데, 분류된 김에 클러스터링 여부로 분류해보겠다.

클러스터드?가 뭔데?

Clustered Index는 실제 데이터 레코드를 인덱스 값을 기준으로 정렬 시켜 놓은 인덱스이다. 앞서 언급한 대로 인덱스는 보통 정렬되어 있지만, 그렇다고 실제 데이터가 정렬되어 있지는 않다.

Clustered Index는 데이터 또한 물리적으로 정렬 되어 있다.

MySQL InnoDB 엔진은 테이블을 만들 때, Primary Key에 대한 인덱스를 만들어 준다. 이는 PostgreSQL 또한 똑같은데, 테이블 설계시 Primary Key는 Null이 허용 되지 않고, 유니크 하기 때문에 사실 인덱스로 만들기 딱 좋다.

이때, InnoDB 테이블은 Primary Key를 기준으로 정렬 되어 있는 인덱스 테이블을 만든다. 실제 데이터 또한 Primary Key를 기준으로 정렬 되어 있다. 위 그림에서 아래 테이블이 Clustered 형태이다.
반대로 PostgreSQL이 만드는 기본 인덱스는 Non-Clustered인데, 위 그림에서 위의 테이블이 Non-Clustered형태의 Secondary Index이다.

Secondary Index

MySQL에서 Primary Key로 자동으로 만들어지는 인덱스 외의 인덱스 테이블은 모두 Secondary Index이다. 이들은 앞서 소개한 인덱스의 정의대로, 실제 데이터가 아닌 실제 레코드를 가리키는 "물리적" 주소 값을 가진다.
따라서 위 그림의 1번째 그림처럼 리프 노드에 다다르면 레코드의 주소를 알 수 있게 되는 것이다.
그리고 2번째 테이블 그림처럼 InnoDB에서는 세컨더리 인덱스로 레코드의 "논리적' 주소값을 알게 되는데 (Key값) 그 값으로 Primary Key index를 한번 더 조사해서 데이터를 얻는다.

2. B-Tree 인덱스

B-Tree는 DB 인덱싱 알고리즘 가운데 가장 일반적으로 사용되는 인덱스이다. MySQL, Postgresql이 기본적으로 사용하고 있다.
B는 Balanced의 약자로, 트리의 Depth를 낮추기 위해 밸런스를 맞추는 형태의 트리 중 하나이다. 트리의 Depth를 낮추면 평균 탐색 속도가 줄어들기 때문이다.
혹시 헷갈리면 트리를 잘못 만들어 편향 되면 매우 느려진다는 사실을 기억해보면 Depth와 평균 탐색 속도의 관계가 이해 갈 것이다.

B-Tree는 칼럼의 원래 값을 변형시키지 않고, 트리 내에서 항상 정렬된 상태로 유지한다.

2.1 구조와 특성

1. Branch Node : B-Tree는 위의 그림과 같이 생겼다. 루트와 리프 노드 외의 중간 노드들을 Branch Node라고 부른다.
2. Leaf Node : 인덱스 트리의 리프 노드는 아래 그림과 같이 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있다. 실제 데이터들은 인덱스와 별개로 따로 관리되는 것이다.

3. 실제 데이터의 정렬 : 위 그림과 같이 인덱스의 키 값은 모두 정렬되어 있는 반면, 실제 데이터 파일 레코드는 정렬되어 있지 않다. (Custered Index 제외)
   많은 사람들이 파일 레코드들이 삽입된 순서대로 저장된다고 생각하지만, 그건 아니다.
   물론 삽입될 때는 그렇게 삽입되지만. 레코드가 삭제되는 경우 그 빈공간에 다른 데이터가 삽입된다. DB는 공간을 최대한 활용한다.

2.2 인덱스 검색, 추가, 삭제, 변경

책에서는 추가와 삭제 먼저 알려주지만, 내 생각엔 검색을 먼저 이해하는 것이 좋다. 결국 추가 삭제 과정에서 노드가 삽입될 적절한 위치를 찾기 위해 검색이 선행되기 때문이고, 가장 이해하기 쉽기 때문이다.

검색

인덱스의 존재 이유는 빠른 검색이다. B-Tree는 정렬되어 있으므로, 루트 부터 시작해서 값의 대소 비교를 하며 내려가면 된다.
예를 들어 위 그림에서 35를 찾는다고 생각해보자. 루트 노드에서 20과 40 사이임을 확인하고, 그 사이에 위치한 포인터가 가리키는 [30, 33]이 있는 노드로 향한다.
이후, 값이 33보다 큰 것을 확인하고, 세 번째 포인터로 이동한다. 그러면 35를 찾게 된다.

추가

추가시엔 일단 B-Tree를 탐색해 적절한 삽입 위치를 찾는다. 저장 위치가 결정되면, 레코드의 키 값과 대상 레코드의 주소 정보가 리프 노드에 저장된다.
추가 과정에서 리프 노드가 꽉 차게 되서 더는 저장할 수 없을 때, 리프 노드가 분리된다. 이때, 상위 노드에서 분리된 노드들을 잘 찾을 수 있어야 하기 떄문에, 상위 노드에도 무언가 처리를 해 줘야한다. 이러한 처리 때문에 추가 작업은 시간이 오래 걸린다.

의외로 이 책에선 어떤 처리를 하는지 자세히 적어 놓지 않았는데, 이 사이트 (opens in a new tab)에서 코드를 확인해보자. B+Tree 동작을 이 사이트에서 확인한 적이 있는데, 도움이 많이 되었었다.
따로 글이나 써 봐야겠다..

한가지 특이한 점은 InnoDB 스토리지 엔진은 INSERT시 새로운 Key 값을 B-Tree에 바로 추가하지 않는다. 지연시켜 나중에 처리한다. 단, Primary Key인덱스의 경우 중복 확인을 해야하므로 즉시 수행된다. (이는 InnoDB 체인지 버퍼를 공부해보라고 한다.)
그리고 MyISAM의 경우 이러한 지연 처리 없이 바로 저장된다.

삭제

삭제의 경우 간단하다. 단순히 B-Tree의 리프 노드를 찾아 값을 삭제한다.
삭제 마킹된 인덱스 키 공간은 그대로 방치되거나 재활용된다. 이 작업은 디스크 I/O가 발생한다. InnoDB에선 추가와 같이 지연 처리될 수 있다.

변경

인덱스 키 값이 변경되는 경우, 당연히 B-Tree에서의 위치도 변경되어야 한다. 그래야 대소비교를 통해 빠르게 탐색할 수 있기 때문이다.
BTree류에서의 값 변경은, 키를 삭제하고 추가하는 방식으로 처리된다. 역시 InnoDB에서는 지연 처리될 수 있다.

다음 글에서

-> B-Tree 인덱스 사용에 영향을 미치는 요소, 인덱스를 통해 읽기, 스캔 방향, 가용성과 효율성 등..