트리와 이진트리, B-Tree와 B+Tree

개요

데이터베이스 인덱스(Index)를 구현할 때 대표적으로 해시 테이블과 B+Tree 자료구조를 많이 사용한다. 그 중에서도 B+Tree를 주로 사용한다. 이번 포스트는 B+Tree 자료구조에 대해 정리하려고 한다.

B-Tree, B+Tree를 이해하기 위해 필요한 기본적인 트리, 이진 탐색 트리(BST)의 개념을 알아본 후 B-Tree, B+Tree 개념을 정리하려고 한다.

트리 (Tree)

트리는 자료 구조 중 비선형 자료 구조에 속한다. 비선형 자료 구조는 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말한다.

트리의 구성

트리는 노드와 간선으로 이루어져 있다.

• 루트 노드: 가장 위에 있는 노드
• 내부 노드(internal 노드): 루트 노드와 내부 노드 사이에 있는 노드
• 리프 노드(leaf 노드): 자식 노드가 없는 노드

트리 특징

• 부모, 자식 계층 구조를 가진다.
  • 예를 들어 위 그림에서 5 노드는 6 노드, 7 노드의 부모 노드이다.
• 간선 수 = 노드 수 - 1
• 임의의 두 노드 사이의 경로는 유일무이하게 존재한다. (반드시 존재한다는 뜻)

이진 탐색 트리(BST)

모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고 모든 노드의 오른쪽 서브트리는 해당 노드의 값보다 큰 값들만 가진다.

이진 탐색 트리 예시

• 20 노드를 기준으로 왼쪽은 20보다 작은 노드들이 있고 오른쪽은 20보다 큰 노드들이 있다.
• 5 노드를 기준으로 보았을 때 왼쪽은 5보다 작은 노드가 있고 오른쪽은 5보다 큰 노드들이 있다.

이진 탐색 트리 특징

이진 탐색 트리는 자녀 노드를 최대 두개까지 가질 수 있다는 특징이 있다.

그렇다면 자녀 노드를 두개 보다 더 많이 가지고 싶을 땐 어떻게 해야할까? 이때 사용할 수 있는게 B tree이다.

B tree가 등장한 이유

• 위 그림에서 왼쪽이 이진 탐색 트리를 나타낸다.
• 이진 탐색 트리는 부모 노드를 기준으로 왼쪽은 부모 노드보다 작은 값을 가지고 있고 오른쪽은 부모 노드보다 큰 값을 가지고 있다.
• 이렇게 이진 탐색 트리의 원리를 가지고 자녀 노드가 3개일 때를 구현해보자.
• 자녀 노드가 3개일 때 각각의 자녀 노드가 가질 수 있는 값의 범위를 정해주는 것이다.
  • 왼쪽 노드는 k1보다 작고, 가운데 노드는 k1과 k2 중간 값을 가지고 오른쪽 노드는 k2보다 큰 값을 가진다.
• 이렇게 하려면 k1 값과 k2 값이 필요하다.

• 결국 부모 노드에 1개의 값만 저장하는 것이 아닌 k1 값과 k2 값을 모두 저장해야 한다.
• 이렇게 하면 이진 탐색 트리와 동일한 형태로 동작을 하면서도 하나의 노드가 2개 이상의 노드도 가질 수 있게 된다.

즉, B tree는 이진 탐색 트리가 자식 노드를 2개 이상 둘 수 없는 한계를 극복하고자 등장했다.

B-tree

B-Tree는 이진 탐색 트리를 일반화한 트리이다. 일반적인 이진 탐색 트리에서는 각 노드가 최대 두개의 자식 노드를 가지지만 B-Tree에서는 제약이 없어 여러 개의 자식 노드를 가질 수 있다. 또한 노드 내의 key가 1개 이상일 수 있다. Balanced Tree의 일종이다.

B tree 특징

• 부모 노드의 key 수가 k개 라면, 자식 노드의 수는 k+1개 이다.
• 자녀 노드의 최대 개수를 늘리기 위해서 부모 노드에 key를 하나 이상 저장한다.
• 부모 노드의 key들을 오름차순으로 정렬한다.
• 정렬된 순서에 따라 자녀 노드들의 key 값의 범위가 결정된다.
• 이런 방식을 사용하면 자녀 노드의 최대 개수를 입맛에 맞게 결정해서 쓸 수 있다.
• 때문에 B tree는 BST를 일반화한 tree라고도 한다.
• 최대 몇 개의 자녀 노드를 가질 것인지가 B tree를 사용할 때 중요한 파라미터이다.

B-tree 예시

• 3차 B tree의 예시이다.
• 노드 안에서 key들은 항상 정렬된 상태를 유지한다.
• 이진 탐색 트리처럼 각 key의 왼쪽 자식은 자신보다 작고, 오른쪽 자식은 자신보다 크다.

B tree의 4가지 파라미터

최대 M개의 자녀를 가질 수 있는 B tree를 M차 B tree라 부른다.

• 각 노드의 최대 자녀 노드 수: M
• 각 노드의 최대 key 수: M-1
• 각 노드의 최소 자녀 노드 수: [M/2] (소숫점은 올림) (root노드, leaf 노드 제외)
• 각 노드의 최소 key 수: [M/2]-1 (root 노드 제외)

일반적인 B tree는 internal 노드의 key 수가 x개라면 자녀 노드의 수는 언제나 x+1개라는 특징이 있다.

만약 아래 그림과 같은 트리가 있다면 이는 B tree가 아니다.

• 부모 노드의 키가 2개이므로 자녀 노드의 수는 3개이어야 한다. 하지만 여기선 2개이므로 B tree가 아니다.

• 위 구조도 key는 1개 인데 자녀 노드가 3개이므로 B tree가 아니다.

일반적인 B tree가 아닌 M 차 B tree는 아래와 같이 계산 방법이 달라진다.

• M이 정해지면 root 노드를 제외하고 internal 노드는 최소 [M/2]개의 자녀 노드를 가질 수 있게 된다.
• 예) 5차 B tree 노드는 root 노드를 제외하고 internal 노드는 최소 3개의 자녀 노드를 가질 수 있게 된다.

결론적으로 B-tree를 사용하는 이유는 다음과 같다.

일반적인 트리인 경우 탐색하는데 평균적인 시간 복잡도로 O(logN)을 갖지만, 최악의 시간복잡도는 O(N)을 갖게 된다. 이러한 단점을 보완하기 위해 트리가 편향되지 않도록 항상 밸런스를 유지하는 트리가 필요하다. 자식들의 밸런스를 잘 유지하면 최악의 경우에도 O(logN)의 시간을 보장한다.

B Tree의 key 검색

원하는 값을 검색하는 방법은 이진 탐색 트리와 비슷하다. 원하는 값을 K라 가정한다.

1. 루트 노드부터 탐색을 시작한다.
2. 노드의 key를 순회하여 K가 존재하면 탐색을 종료한다.
3. K가 존재하지 않으면, 루트 노드 중 어떠한 두 key 사이에 K가 들어갈지를 생각하여 해당 포인터를 통해 자식 노드로 내려간다.
4. leaf 노드까지 2~3을 반복한다.

예를 들어 B Tree 예시에서 14를 검색한다고 가정하자.

• 루트 노드의 key를 순서대로 확인

• 7보다 크므로 다음 key 확인. 15보다 작으므로 사이에 있는 포인터가 가리키는 자식으로 이동

• 자식으로 이동한 후 key 순서대로 확인
• 11보다 크므로 11의 오른쪽에 있는 포인터를 통해 자식으로 이동

• 마찬가지로 순서대로 탐색 후 14 확인

B+Tree

B-Tree는 어느 한 데이터의 검색은 효율적이지만, 모든 데이터를 한 번 순회하는데에는 트리의 모든 노드를 방문해야 하므로 비효율적이다. 이러한 B-Tree의 단점을 개선시킨 자료구조가 B+Tree이다.

B+Tree는 오직 leaf node에만 데이터를 저장하고 leaf node가 아닌 node에서는 자식 포인터만 저장한다. 그리고 leaf node끼리는 Linked list로 연결되어있다.

또, B+Tree에서는 반드시 leaf node에만 데이터가 저장되기 때문에 중간 node에서 key를 올바르게 찾아가기 위해서 key가 중복될 수 있다.

B+Tree 예시

B+Tree 장점

• leaf node를 제외하고 데이터를 저장하지 않기 때문에 메모리를 더 확보할 수 있다. 따라서 하나의 node에 더 많은 포인터를 가질 수 있기 때문에 트리의 높이가 더 낮아지므로 검색 속도를 높일 수 있다.
• Full scan을 하는 경우 B+Tree는 leaf node에만 데이터가 저장되어 있고, leaf node끼리 linked list로 연결되어 있기 때문에 선형 시간이 소모된다. 반면 B-Tree는 모든 node를 확인해야 한다.

하지만, B+Tree는 특정 key에 접근하기 위해선 반드시 leaf node까지 가야한다는 단점이 있다.

인덱스에서 B-Tree보다 B+Tree를 사용하는 이유

인덱스 컬럼은 부동호를 이용한 순차 검색 연산이 자주 발생한다. 따라서 B+Tree의 Linked list를 이용하면 순차 검색을 효율적으로 할 수 있다.