[데이터베이스] 19. 복합 키, B+트리

인덱스의 탐색 키는 여러 필드를 포함할 수 있다.

이렇게 여러 필드로 구성된 탐색 키를 '복합 키' 라고 한다.

 

 

위 그림과 같은 테이블을 생각해보자.

만약 age 라는 하나의 search key 를 둔 경우에는 11, 12, 12, 13 순으로 인덱스가 정렬되어 가리킬 것이고,

<sal, age> 라는 복합키를 둔 경우에는 (10, 12) (20, 12) (75, 13) (80, 11) 순으로 가리킨다.

<age, sal> 라는 복합키를 둔 경우에는 (11, 80) (12, 10) (12, 20) (13, 75) 순으로 가리킨다.

 

 

이제 이렇게 인덱스가 주어진 상태에서 다음의 쿼리를 실행해보자.

 

 

 

만약 위와 같은 쿼리를 실행한다면 <sal, dno> 라는 복합키와 <dno, sal> 라는 복합키가 주어졌을 때, 어떤 것이 더 효율적일까?

정답은 <dno, sal> 이라는 복합키이다.

왜냐하면 일단 sal = 10000 으로 조건을 걸고 나서, 그 안에서 dno 으로 묶고 있기 때문에 sal 가 먼저 활용되며, dno 은 그 안에서 정렬될 필요가 없으므로 인덱스가 꼭 필요하지 않다.

 

 

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은 오버플로우 페이지에 계속 붙이기만 하면 되므로 락을 걸지 않아도 된다.)