인덱스란?

흔히들 언급하는 책의 "찾아보기" 페이지로 이해하면 된다.
DB가 저장해놓은 테이블의 레코드를 더 빠르게 찾을 수 있도록 도와주는 친구다.

인덱스 구조

페이지

먼저, 인덱스 구조를 보기 전에 페이지(Page)를 이해하고 가야 한다.

페이지 또는 블록이라고 부르며, 디스크에 데이터를 저장하는 가장 기본 단위인데, 인덱스도 결국은 페이지 단위로 관리되며 아래에서 살펴볼 인덱스 구조인 B-Tree에서 사용되는 노드를 구분하는 기준 또한 페이지다.

⇒ 페이지 1개 = 노드 1개

B-Tree

B-Tree는 데이터베이스의 가장 오래된, 가장 일반적으로 사용하는 인덱싱 알고리즘이다.

🤔 B-Tree = Binary Tree?

B-Tree를 자칫 Binary Tree의 줄임말로 오해하는 경우도 있지만, Balanced Tree를 의미한다.
좌우 자식 간의 균형을 맞추는 트리를 Balanced Tree라고 부른다.

우리가 알고 있는 알고리즘을 풀 때 사용하는 트리들과는 다르게 여러 개의 하나의 노드에 여러 값이 들어가 있는 걸 볼 수 있는데, 이걸 key 라고 부른다.

또, 최대 M개의 자식을 가질 수 있는 B-Tree를 M차 B-Tree라고 부른다.

아래는 차수가 3인 B-Tree의 모습이다.

B-Tree 특징

• node의 key는 반드시 정렬된 상태
• 모든 leaf node들은 같은 level에 있어야 한다.
• 자식 node들의 key는 현재 node의 key를 기준으로 크기 순으로 분류 → 이진검색 트리처럼 각 key들의 왼쪽 자식 key는 해당 key보다 작은 값을, 오른쪽 자식 key는 해당 key보다 큰 값을 가진다.
  
• 노드에는 최대 M - 1개 부터 [M/2] - 1개의 키가 포함될 수 있다.
• node의 key 수가 k개라면, 자식 node의 수는 k+1개
• root node는 항상 2개 이상의 자식 node를 가진다.
• M차 트리일 때, root node를 제외한 모든 node는 최소 $\lceil M/2 \rceil$ , 최대 M개의 서브 트리를 갖는다.

*차수 또는 계수: 노드가 가질 수 있는 자식의 최대 개수

B-Tree 구조에 대해 이해가 안 가거나, 더 탐구해보고 싶다면 아래 visualization을 해주는 사이트를 이용해보면 좋을 것 같다.

https://www.cs.usfca.edu/~galles/visualization/BTree.html

B+ Tree

B-Tree의 단점을 개선한 알고리즘이다.

B+ Tree VS. B-Tree

• key와 data: B-Tree는 리프노드가 아니어도 key마다 data를 가진다면, B+Tree는 리프 노드에서만key가 data를 가진다. 위의 B-Tree 모습에서는 생략되었던 data를 명시하면 아래와 같은 모습이다.
  

• 리프노드의 연결리스트: B-Tree는 바로 이웃한 리프노드를 검사할 때, 다시 루트노드부터 검사해야 한다면, B+Tree는 모든 리프노드가 연결리스트 형태를 띄고 있어, 선형검사를 수행할 수 있다. (=범위 검색 작업이 더 빠르다) 아래는 리프노드가 연결리스트의 형태를 띄고 있는 B+tree모습이다.
  

• 중복 key: B-Tree는 중복키가 없지만, B+Tree는 중복키가 존재한다.

B-Tree에서 개선한 점

B+Tree의 인덱스 구조 살펴보기

앞서 설명했던 것처럼 페이지 하나가 노드 하나로 표현되고 있고, 각 인덱스 키 값과 다음 값을 가리키는 포인터인 자식 노드가 트리 노드 안의 key를 표현하고 있다.

인덱스의 변경 작업

테이블의 레코드를 저장하거나 변경할 때, 인덱스에도 똑같이 저장 및 변경 작업이 발생한다. 인덱스는 그 작업이 어떻게 진행될까?

인덱스 키 추가

인덱스 키가 추가된다면 어떤 과정을 통해 이뤄지는지 살펴보자.

아래는 3차 B-Tree(=페이지 1개당 들어갈 수 있는 인덱스의 개수는 3개)이다. 이 트리에 우리는 18이라는 값을 가진 key를 삽입하려고 한다고 가정한다.

1) 먼저 root부터 탐색해 내려오다, leaf node중 18을 추가할 수 있는 위치를 찾는다.

2) 최대 key 개수를 넘겼기 때문에, 해당 노드를 분할 후, 분할된 오른쪽 노드의 가장 작은 값을 부모 key로 설정한다.

3) [12, 16, 17] → 또 노드가 최대 key 개수를 초과했기 때문에 분할을 수행, 중간 노드를 부모 key로 설정후, 분할된 노드를 자식노드로 설정한다.

앞서 봤던 과정은 테이블의 레코드를 저장하거나, 변경하는 경우에 발생하는 인덱스 키 추가 작업 과정 중 페이지가 꽉 찼을 때를 살펴본 것이다. 인덱스 키 추가 작업에 대해 더 자세히 살펴보자.

성능이 오히려 떨어지는 Index?

항상 언급되는 인덱스의 단점으로는 SELECT 작업이 아닌 데이터 변경 작업(INSERT, UPDATE, DELETE)에 관해서는 오히려 성능이 떨어질 수 있다는 점이다. 왜 그런지 위의 인덱스 추가 과정을 봤다면 대충 짐작할 수 있다.

인덱스가 추가될 위치의 리프 노드가 꽉 찬 경우가 아니라면 바로 인덱스 추가 작업이 끝난다. 하지만 앞서 봤던 것처럼 추가될 위치의 리프 노드가 꽉 찬 경우에는 노드의 분할 작업이 필요하고, 이 경우에 상위 브랜치 노드까지 처리할 범위가 넓어진다. 그래서 변경 작업에는 성능이 오히려 떨어질 수 있다고 이야기하는 것이다.

인덱스 키 삭제

테이블의 레코드가 삭제되면, 저장되어 있던 해당 레코드의 인덱스 키도 삭제되어야 한다. 인덱스의 삭제는 굉장히 간단하다. 해당 키 값이 저장된 리프 노드를 찾아, 삭제 마크만 하면 작업이 완료된다.

이 마킹된 인덱스 키 공간은 계속 그대로 방치하거나 재활용할 수 있다.

아래 그림은 이해를 돕기 위한 예시 모습(실제X)이다.

인덱스 키 변경

키 값에 따라 인덱스 구조 내에서의 위치가 결정되기 때문에 인덱스 키 값만 변경하는 것은 불가능하다.

따라서 해당 인덱스 키를 삭제하고, 새롭게 변경한 인덱스 키를 추가하는 방식으로 인덱스 키의 변경 작업이 진행된다.

Clustered Index & Non-Clustered Index

클러스터링 인덱스이냐 아니냐를 구분하는 기준은 “인덱스가 실제 데이터와 함께 저장되어 있는지”다.

Non-Clustered Index

특정 컬럼을 인덱스로 설정해도, 인덱스로 설정된 컬럼 값에 따라 테이블이 물리적으로 정렬되지 않는다. 따라서 앞서 봤던 것처럼 별도의 인덱스 페이지를 생성하고 관리한다.

Clustered Index

아래처럼 실제 데이터와 무리를 지어 인덱싱이 된다. 클러스터형 인덱스는 테이블 당 하나만 생산할 수 있으며, PK로 지정하며 자동으로 클러스터형 인덱스를 생성한다.

따라서 클러스터형 인덱스의 리프 노드는 아래와 같은 모습이다.

혼합형

보통 인덱스는 혼합형으로 주로 쓰인다. 혼합형은 아래처럼, Non-Clustered Index에서 탐색 후, 해당 노드가 가리키는 PK를 이용해 또 다시 Clustered-Index를 탐색하도록 하는 구조다.

만약, Non-Clustered Index 구조에서, 리프노드 값에 PK가 아닌 데이터 주소를 기록한다면 굳이 Clustered-Index를 탐색하지 않고 바로 데이터에 접근할 수 있다. 하지만 데이터가 추가, 수정, 삭제가 된다면 해당 테이블 레코드의 저장 위치나 순서가 변경될 경우 해당 테이블 설정되어 있는 모든 인덱스에 저장되어 있는 데이터를 변경해야 하는 문제점이 발생한다.

따라서, 데이터 주소 대신 PK를 저장해 아래와 같이 혼합형으로 사용하는 경우가 대부분이다.