[데이터베이스] 트리 구조 인덱스

1. ISAM 트리구조

정적 트리구조

삽입 / 삭제를 하여도 트리의 구조가 변화하지 않는 것이 특징이다. 만일 페이지에 더 이상 데이터를 추가할 수 없다면 오버플로우 페이지를 생성하여 마지막 리프노드에 체인으로 연결하여 추가한다.

오버플로우 페이지

위의 그림 왼쪽 트리 구조에서 7을 삽입하는 연산이 수행한다고 가정하자. 루트에서 시작해서 리프 노드에 도달하면 7이 들어갈 노드가 (6*, 9*)로 채워져 들어갈 공간이 없다. 이때 ISAM 트리 구조는 트리의 구조를 변형시키지 않고 아래에 7이 들어갈 수 있는 공간을 만든 후 다음 7을 삽입한다. 이 때 새로 만들어진 이 공간을 오버플로 페이지라고 한다. 

오버플로 페이지를 생성함에 따라서 얻을 수 있는 이득은 오버플로가 발생하는 경우 삽입 / 삭제 연산이 B+ 트리보다는 빠르다는 점이다. 아래에 설명할 B+트리는 동적 트리구조로 만약 위의 그림과 같은 상황이 발생하면 트리 구조를 변형을 하여 삽입을 시도하기 때문이다. 또한 Lock을 거는 경우 트리의 내용물에는 변화가 없기 때문에 리프 노드에만 Lock을 걸면 된다. 하지만 오버플로 페이지가 많이 발생할수록 위 그림에서 눈치챘을지도 모르지만 데이터를 물리적으로 정렬하지 않기 때문에 데이터를 탐색하는 속도는 늦어어진다는 단점이 있다.

2. B+ 트리구조

동적 트리구조

ISAM 트리와 달리 삽입 / 삭제시에 트리구조가 변화가 발생하는  특징이 있다. 또한 Root 노드를 제외한 나머지 노드들은 데이터를 반드시 절반 이상 점유해야 하는 필수 조건이 있다. 

삽입 연산

위의 트리에서 8을 삽입한다고 가정하자. 8은 L2에 삽입되어야 하지만 현재 노드가 꽉 차있어서 삽입을 할 수 없다. B+ 트리는 오버플로 페이지를 생성하지 않고 L2를 쪼개서 새로운 노드를 만드는 방법을 사용한다. 8을 포함한 L2의 구성 요소 (5,6,7,8,9) 중 중간 값인 7은 상위 단계 노드로 Copy up 되고 트리구조의 특징상 기존의 L2(5,6,7,8,9)는 L2(5,6), L3(7,8,9)로 갈라지게 되어 아래 그림과 같이 된다.

따라서 삽입 연산 중 리프 노드에서 오버플로가 발생하면 B+트리는 해당 노드의 중간 값이 상위 노드로 Copy up 하는 과정이 발생한다. 만일 Copy-up 과정에서 상위 레벨 노드마다 오버플로가 발생한다면 어떻게 트리구조가 변화할까?

위의 그림과 같은 트리에서 15가 삽입된다고 가정하자. 15가 삽입될 노드는 L4인데 L4가 가득 차있으니까 아까 위에서 Copy up을 시도한다. L4(13,14,15,16,18) 중에서 중간 값인 15가 상위 단계 노드로 Copy up이 되려는 순간 상위 노드가 꽉 차있다. 따라서 상위 노드도 분열이 되어야 하는데 이 과정에서 분열된 상위 노드들을 연결할 새로운 루트 노드가 필요하다.  상위 노드의 값 (5, 7, 13, 15, 20) 중 중간 값인 13이 한 단계 상승한 Push up 과정이 발생하고 나머지 (5,7) (15,20)이 다음 노드로 연결되는 아래 그림과 같은 트리구조로 변화한다.

기존 트리의 높이는 1이였지만 삽입의 결과로 높이가 2로 변화하였다. B+트리는 이처럼 트리의 구조를 유지하기 위해서 Copy up / Push up 알고리즘을 사용하고 경우에 따라서 트리의 높이가 변화할 수도 있다.

삭제 연산

삭제 연산에서 가장 중요한 키워드는 루트를 제외한 각 노드는 점유율을 항상 50%이상 유지한다는 점이다. 만약 50프로가 안된다면 인접한 노드에서 빌려온다. 그런데 빌려 오니까 인접 노드도 점유율 50%를 만족하지 못한다면 인접 노드와 병합하는 방법으로 점유율 50%를 유지한다.

 

위 그림(아까 삽입한 결과)에서 24*를 삭제하는 연산을 수행한다고 하자. L6은 이제 데이터가 (21*)만 존재하게 되어 데이터의 점유율이 50프로 미만이 되어버렸다. 따라서 인접 노드인 L5에서 데이터를 (18*)를 빌려온다. L5도 (15*, 16*)을 가지고 있고 L6도 (18*, 21*)로 50프로를 유지할 수 있으므로 L6의 최솟값 18*을 상위 노드에 20*으로 Copy up 하는 것으로 마무리한다. 결과는 아래의 그림과 같다.

이번에는 L1의 1을 삭제한다고 가정하자. 1이 삭제된 L1은 (2*)만 남아 50프로를 유지할 수 없고 인접 노드 L2의 5*를 빌려서 채울려고 하지만 그렇게 진행하면 L2도 (6*)만 남아 점유율 50프로를 만족하지 못한다. 따라서 L1과 L2는 합병이 된다.

합병을 하고 상위 노드 I1의 5*를 삭제하니 I1도 50프로를 만족하지 못한다. 인접 노드 L2에서 데이터를 하나 빌릴려고 하니 연산 결과 L2도 50%를 만족하지 못한다. 따라서 합병을 해야하는 상황이 발생한다. 

합병을 할 때 상위 노드의 값은 한 단계 내려와 Pull down되어 I1, I2와 함께 합쳐진다.  그 외 여기서 다루진 못했지만 만약 I1이 데이터가 4개 있고 삭제당한 I2의 데이터가 1개 있다면 합병하게 되면 5개가 돼버려서 오버플로가 발생하는 경우가 있다. 이 경우에는 재분산(Re-distribution)을 사용하여 2개 / 3개로 다시 나누어 주는 과정이 있다. 기존의 트리의 높이는 2였지만 모든 삭제 연산을 수행한 후에 보면 높이 1의 트리로 변화하였다. 

트리 구조를 유지하면서 이득 / 손해

우선 이득은 데이터 탐색 속도가 ISAM보다 빠르다. 오버플로 페이지가 발생하지 않고 데이터가 삽입되면 그 데이터를 물리적으로 정렬하기 때문이다. 대신 삭제나 삽입의 경우 트리 구조를 유지해야 하는 면에서 ISAM에 비하면 복잡한 과정이 있기 때문에 비용이 좀 더 드는 손해는 있다. 하지만 인덱스를 사용하는 이유는 탐색 속도의 향상이므로 대부분 상용 DBMS에서는 B+ 트리를 사용하여 인덱스를 만든다.