Binary Search Tree(BST)와 B-Tree,B+Tree

    이번에는 저번 파일처리와 파일구조에 대하여 설명한 글에서 설명한 sequential access, simple index 방법에 이어서 BST와 B-Tree(B+Tree)에 대하여 알아보자.

    우선 잘 알려진 BST인 이진탐색 트리에 대하여 설명하자면 한 노드로부터 왼쪽에는 그 노드보다 작은 값, 오른쪽에는 큰 값이 있는 트리를 말한다. 아래의 그림과 같이 삽입 순서대로 노드를 탐색하며 해당 리프노드까지 비교한 다음 추가된다. BST는 평균적으로 O(logN)의 시간 복잡도를 가지며 레코드를 삽입, 삭제가 쉽다는 장점이 있다. 하지만 아래의 오른쪽 그림과 같이 한 쪽 방향으로 치우치며 트리가 형성되는 skew현상이 발생할 수 있다. 이 경우에는 시간 복잡도가 O(N)으로 순차처리와 같게 된다. 

이러한 문제점이 발생하기 때문에 이를 보완한 방법으로 AVL 트리가 나타났다. AVL 트리는 일정한 k값을 정하여 임의의 한 노드로부터 왼쪽 SubTree와 오른쪽 SubTree의 높이가 같게 유지하는 방법이다. 하지만 이 방법을 사용하더라도 파일처리에서 BST를 사용한다는 점은 이전 글에서 말했듯이 Secondary Storage로부터 적은 비용에 많은 정보를 얻어오기에 한계가 있다. 예를 들어 1000번째 있는 레코드를 탐색한다고 생각해보자 이 경우 BST를 사용했을 때 9번~10번의 디스크 접근이 필요하다(2^10이 1024이므로). 약 10번의 디스크 접근도 상당히 부담스러울 수 있다. 이를 보완한 방법으로 B-Tree가 나왔다.

    B-Tree 전에 B+Tree를 설명하겠다. B+Tree는 BST와 달리 한 노드에 하나의 키값이 아니라 여러개의 키값을 가진다. 또한 트리를 balance한 상태로 유지할 수 있기 때문에 skew가 발생하지 않는다. 따라서 모든 리프노드들이 같은 레벨을 가지고 있다. BST와의 또다른 차이점은 트리의 모양이다. BST의 경우 아래 그림의 왼쪽과 같이 좁은 너비에 큰 높이를 가지고 있지만 B+Tree의 경우 오른쪽 그림과 같이 형성되기 때문에 넓은 너비에 낮은 높이를 가지고 있다. 이러한 특징은 파일처리에서 상당히 중요하다. 그만큼 적은 디스크 접근이 발생하기 때문이다. 

아래 그림은 B+Tree 예시이다.

    이 B+Tree에서는 한 노드에 최대로 들어갈 수 있는 key의 개수가 3인 B+Tree이다. 여기서 리프노드가 아닌 non-leaf 노드의 키 왼쪽, 오른쪽에는 다음 노드를 가리키는 포인터가 존재한다. 실제 구현에서의 포인터는 주소이다. 그리고 leaf노드에서는 simple index 방식에서 주소를 가지는 것과 같이 각 key마다 실제 레코드파일의 포인터가 존재한다 위 그림에서는 빨간색 화살표 표시로 표현했다. 그리고 leaf노드는 다음 노드에 대한 포인터를 가진다(파란색 화살표). 이 포인터를 이용해 B+Tree에서는 순차탐색을 할 수 있는 장점이 있다. 또 하나의 특징은 임의의 노드에서 하나의 키값은 그 키 값의 오른쪽 SubTree의 가장 왼쪽 leaf node와 같다. 즉 루트노드인 60의 오른쪽 서브트리에서 가장 왼쪽에 있는 값이 60이라는 말이다. 다음 B-Tree에 대하여 설명하겠다. 아래 그림은 위 그림을 B-Tree로 나타낸 것이다.

    전체적인 구조는 B+Tree와 동일하다. 하지만 큰 차이점들이 있다. 우선 리프노드들이 서로 링크드리스트로 이어져있지 않다. 즉 순차탐색이 불가능하다는 단점이 있다. 하지만 B-Tree의 장점도 있다. 각 노드에서 레코드 파일에 대한 포인터가 존재한다(빨간 화살표). 즉 B+Tree와 달리 B-Tree는 리프노드까지 탐색하지 않고도 레코드파일의 주소를 알 수 있다. 또 하나의 차이점은 B+Tree와 달리 트리에 중복된 키가 존재하지 않는다. B+Tree에서는 임의의 노드에서 키값과 그 키값의 오른쪽 서브트리의 가장 왼쪽 키값이 같다는 특징이 있었다. 즉 중복된 키가 트리에 존재한다는 것이다. 하지만 B-Tree에서는 각 노드에서 곧바로 포인터를 가지기 때문에 중복된 키를 가지지 않게 된다.