[데이터베이스] 19. 트리 기반 인덱스 (B+트리)

인덱스는 결국 레코드를 빠르게 식별하기 위해 레코드 정보인 rid 를 갖고 있는 추가적인 데이터이다.

이 데이터 하나하나를 가리켜 '데이터 엔트리' 라고 부르며 이 정보드는 인덱스 파일에 저장되어 있다.

인덱스 파일도 레코드를 저장하는 파일처럼 여러 인덱스 엔트리의 집합으로 구성되어 있고, '페이지' 로 구분된다.

 

이번에는 정렬되어 있는 데이터 엔트리 중에서 내가 찾으려는 데이터 엔트리를 빠르게 찾기 위한 방법을 정리해본다.

데이터 엔트리를 빠르게 찾기 위해 데이터 엔트리를 특별한 방법으로 젖아할 수 있는데, 크게 트리 기반 인덱스와 해시 기반 인덱스로 나뉜다.

이번 글에서는 먼저 트리 기반 인덱스에 대해 정리해본다.

 

트리 기반 인덱스

트리 기반 인덱스는 특정 탐색 키 값을 트리의 노드로 갖고 있다. (이를 가리켜 인덱스 엔트리라고 부른다.)

이 탐색 키보다 작은 값은 왼쪽 자식 노드, 크거나 같은 값은 오른쪽 자식 노드를 루트로 하는 서브트리에 저장한다.

각각의 탐색키로 구성된 노드를 지나, leaf node 에 다다르면, 단말 노드에는 실제로 rid를 가리키는 데이터 엔트리가 존재한다.

 

이때 데이터 엔트리 뿐만 아니라 트리를 구성하는 모든 노드 역시 물리적인 페이지로 저장되며, 각 노드 데이터를 읽을 때는 디스크 입출력이 수반된다.

 

정적 인덱스 (ISAM)

 

인덱스 순차 접근 방식은 인덱스를 통해 인덱스가 가리키는 값을 빠르게 찾는 방법을 제공한다

ISAM 은 비교적 정적이다. 따라서 데이터의 삽입과 삭제가 여러번 일어나도 변화가 크지 않다.

 

먼저 ISAM 은 인덱스가 위와 같이 이진 트리 구조로 되어있다.

이때 인덱스 트리 부분은 노드에 기준 인덱스 값이 들어가고, 좌우에는 포인터가 들어간다.

그 포인터는 각각 좌 우 자식 노드와 연결되어 있으며, 왼쪽 자식 노드는 부모노드 미만의 인덱스 값을 기준으로 갖고, 오른쪽 자식 노드는 부모노드 이상의 인덱스 값을 갖는다. BST를 생각하면 편하다.

 

맨 마지막 리프노드에는 실제 데이터 값이 들어있다.

예를 들어 10 이라는 실제 최종 값을 찾는다면, 40 -> 20 -> 10 순으로 타고 들어가서 찾게 된다.

 

이제 이 상황에서 새로운 데이터 엔트리를 추가한다고 해보자.

그리고 그 엔트리의 pk 값이 12라면 ISAM 에서는 똑같이 40 -> 20 순으로 타고 내려가는데, 12는 20보다 작으므로 왼쪽 포인터를 타고 내려간다.

이때 이미 왼쪽에는 2개의 칸이 모두 채워져 있는 상황이다. 이런 상황이면 ISAM은 단말 노드 밑에 추가하려는 엔트리를 포인터로 연결해서 붙이게 된다.

 

이 방법으로 동작하다보니, 특정 종류의 데이터가 많이 들어오는 경우, 트리의 균형이 깨질 수 있고, 조회 성능에 문제가 발생할 수 있는 것이 ISAM의 단점이다.

 

 

 

B+ Tree

B+ Tree 는 ISAM 에서 동적으로 동작하는 개념이 추가되었다.

B+ Tree 는 인덱스 엔트리와 Data 엔트리로 구분된다.

 

먼저 B+ 트리에는 '차수' 라는 개념이 존재하며, 트리의 각 노드가 가질 수 있는 엔트리의 개수를 차수 d 에 대해 d <= k <= 2d 로 제한을 둔다.

 

만약 차수가 2라면 모든 트리의 엔트리는 2 ~ 4 사이의 개수를 가지는 것이다.

(따라서 각 노드는 최대 4개의 칸으로 구성되어 있고, 루트를 제외한 모든 노드는 반 이상이 채워져 있어야 한다.)

 

 

그림이 조금 난잡하지만, 차수가 2인 B+ 트리의 예시는 위와 같다.

 

먼저 어떤 부모 노드에 <30, 34, 38, 50> 이라는 값이 있다고 해보자.

이때 각 엔트리 사이사이에는 포인터가 있다.

30의 왼쪽 포인터는 30 이하의 값을 가지고 (미만이지 않나?)

그림에서 13을 기준으로는 왼쪽에는 13 미만의 값, 오른쪽에 13이상의 값이 들어간다.

 

그리고 13 왼쪽에는 <2, 3, 5, 7> 오른쪽에는 <12, 13> 이 있다고 해보자.

(여기서도 그림이 조금 잘못된 것 같다. 13 오른쪽에 12가 존재할 수 없다.)

 

이 상황에서 만약 8을 새로 삽입한다면 8은 현재 4개 엔트리가 모두 가득 찼으니 들어갈 수 없다.

이런 상황에서는 2가지 방법이 있다.

 

1. 8을 왼쪽에 삽입한다고 치고 정렬한 뒤, (2, 3, 5, 7, 8) 이중에 중간값을 위로 올리고 분할한다.

그러면 5라는 값이 위로 올라가고 5의 왼쪽에는 (2, 3) 5의 오른쪽에는 (5, 7, 8) 이 들어있게 된다.

 

다음으로 복사되어 올라간 5는 데이터 엔트리에서 인덱스 엔트리로 넘어간 셈이 된다.

이때 5가 올라간 인덱스 엔트리에도 역시 <13, 17, 24, 30> 으로 4개의 값이 모두 차있다.

반복적으로 나열하고, 중간값을 취하고 위로 올리는 과정을 거친다.

 

<5, 13, 17, 24, 30> 에서 중간값 17을 위로 올리고 (이때는 복사하지 않는다. 엔트리 영역에서는 복사할 이유가 없다.

17의 왼쪽은 <5, 13> 오른쪾은 <24, 30> 으로 정확히 4개 엔트리중 절반이 채워진 형태를 갖게 된다.

그리고 17은 루트 노드로서 혼자 올라가게 된다. (루트 노드는 절반 이상을 채울 필요가 없다.)

 

2. 두번째 방법은 모든 데이터 노드는 그 좌우의 형제 노드와 연결될 수 있다.

따라서 8이 삽입 되었을 때 7에 공간이 없다면 그 옆 <12, 13> 라인에 붙여서 <8, 12, 13> 으로 만든다.

그리고 <8, 12, 13> 의 부모노드를 기존의 13 에서 8로 '교체' 해버린다.

그러면 여전히 8의 왼쪽 4개 엔트리 값에 대해서도 성립하고, 오른쪽 <8, 12, 13> 에 대해서도 성립한다.

 

B+트리는 동적으로 인덱스가 계속 변하는 구조이므로, 데이터가 변하고 있는 과정에서는 락을 걸어두고 수정해야 한다.

(ISAM은 오버플로우 페이지에 계속 붙이기만 하면 되므로 락을 걸지 않아도 된다.)

 

- 데이터 엔트리 삭제

해당 데이터 엔트리가 들어있는 인덱스 페이지가 절반 이상 차있다면 그대로 삭제가 끝난다.

만약 절반보다 작아졌다면 형제 노드에서 데이터 엔트리를 가져오고, 형제 노드의 부모 노드 (인덱스 엔트리) 의 키 값을 교체한다.

만약 형제 노드에서 데이터 엔트리를 가져왔을 때, 형제 노드의 인덱스 페이지가 절반보다 작게 찬다면, 형제 노드의 데이터 엔트리 전체를 자신쪽으로 가져오고, 부모 노드의 인덱스 페이지에서 해당 형제 노드의 기준이 되었던 인덱스 엔트리를 제거한다.

 

만약 이로 인해 부모 노드의 인덱스 페이지가 절반보다 작게 차게 된다면 형제 인덱스 페이지와 비교하여 병합하고, 분배하는 과정을 거칠 수 있다.

 

(구체적인 예시 추가)