B-Tree란? (1)

elsa ❆·2021년 9월 12일

B-tree 자료구조

DB index에 대해 공부하다보면 B-Tree에 대해서도 자주 접하게 된다. 학교에서 자료 구조 시간에 배우긴 했지만 가물가물해서 이번 기회에 B-Tree에 대해서도 정리해보려한다.

B-Tree

B-Tree 구조란?

하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리구조를 말한다.
self-balancing search tree이다.
사실 앞의 B가 의미하는 게 무엇인지 명확하게 밝혀진 건 없지만 통상적으로 balancing으로 여겨지고 있다.

특징

B-Tree 구조는 하나의 노드에 2개 이상의 자식 노드를 갖는다.
모든 leaf node는 같은 level에 있다. 다르게 표현한다면, root node로부터 leaf node까지의 거리는 모두 같다고 할 수 있다.
b tree의 order가 m이라는 뜻은, non leaf node가 가질 수 있는 children의 수가 최대 m임을 의미한다. 때문에 값의 삽입과 삭제가 일어날 때, 노드들은 합쳐지거나 나눠진다.
실제 값은 트리의 맨 끝인 leaf node에 존재하며, 그 외의 non leaf node에는 key 값이 저장되어 있다.

규칙

각각의 노드에 있는 키들은 전부 정렬되어 있어야 한다.
부모 노드의 키 사이사이와 자식 노드들이 연결되어 있는데, 이 사이에 연결된 노드는 두 키 값 사이의 값들만 가져야 한다.
예를 들어 위의 그림을 보면 루트 노드 9번의 왼쪽에 연결된 노드의 키 값은 모두 9보다 작아야 한다.
9와 15번 사이에 연결된 2번 노드는 9보다 크고 15보다 작은 값을 가져야 한다.

왜 필요할까?

B-Tree가 왜 필요할까? 다른 트리와 차별점은 무엇인가? B-Tree의 필요성을 알아보기 위해 잠시 Binary Search Tree에 대해 알아보자.

Binary Search Tree (BST)

노드의 왼쪽 서브 트리는 노드의 키 값보다 작은 값들로 이루어져 있다.
노드의 오른쪽 서브 트리는 노드의 키 값보다 큰 값들로 이루어져 있다.
각각의 왼쪽, 오른쪽 서브 트리는 binary search tree이어야 한다.
위의 그림을 예로 들면, 맨 위의 루트 노드의 왼쪽에 있는 노드들은, 루트 노드의 키 값 8보다 작은 값이다. 루트 노드의 오른쪽에 있는 노드들은, 루트 노드의 키 값 8보다 큰 값들로 이루어져있다.

Balanced BST vs Unbalanced BST

균형잡힌 BST의 경우 삽입, 삭제, 검색에 대해 시간 복잡도가 O(log(n))이다.
위의 오른쪽 그림과 같이 좌우 균형이 맞지 않는 unbalanced BST의 경우에는 모든 노드를 조회해야 하기 때문에 O(n)의 시간 복잡도를 가진다.
위와 같이 좌우 노드 밸런스가 맞지 않을 때는 트리 구조를 사용함에도 불구하고 매우 비효율적인 성능을 보여준다. 이 점을 방지하고 트리의 좌우 균형을 유지하기 위해 나온 개념이 B-Tree이다.

검색

아래의 B-Tree에서 195를 검색해보자.
1. root node에서 시작한다.

2. 다음 레벨에 위치한 노드들의 키를 확인한다. 195는 왼쪽 노드에 위치한 35, 60보다 큰 값이고 오른쪽 노드에 위치한 키 값 180보다 큰 값이므로 B-Tree의 오른쪽 branch로 이동한다.

3. 180보다 큰 값이므로 맨 오른쪽 노드로 이동해 195 값을 찾는다.

다음 포스팅에서는 B-Tree를 코드로 구현해보자.