이진 트리(Binary Tree)
이진 트리는 평균적인 시간복잡도로 O(logN)을 갖지만, 한쪽 방향으로만 노드들이 쏠려 균형이 맞지 않은 경우 최악의 시간복잡도로 O(N) 을 갖게 된다.
또한 이진 트리는 노드 하나의 자식 노드로 최대 두 개의 노드만 가질 수 있으므로 데이터가 증가할 수록 깊이가 커지는 속도가 빠르다.
B-Tree
B-Tree의 B는 Binary가 아닌 Balanced로, 균형이 잡힌 트리라는 의미의 자료구조이다. 트리의 노드가 한쪽으로만 쏠리지 않도록 노드 삽입 및 삭제 시 특정 규칙에 맞게 재정렬하여 전체적으로 balance를 유지한다.
최상단에 있는 node를 Root node, 최하위에 있는 node를 Leaf node라고 한다. Root와 Leaf 중간에 있는 node들을 Branch node라고 칭하기도 한다.
특징
B-Tree는 다음과 같은 특징을 갖는다.
- 한 node의 key가 k개라면, 자식 노드의 개수는 k+1이다.
- node의 key는 항상 정렬된 상태이다.
- leaf node가 아닌 node는 항상 2개 이상의 자식 node를 가진다.
- 모든 leaf node들은 항상 같은 level에 위치한다.
- 각 node는 여러 개의 key와 각 key에 대응하는 data를 가지며, node들의 key는 중복되지 않는다.
- 각 node는 자식 node를 참조하는 포인터를 갖고 있다.
B+Tree
B-Tree는 어떤 한 데이터의 검색에서는 빠를 수 있으나, 모든 데이터를 순회하기 위해서는 leaf node까지 갔다가 다시 부모 node로 BackTracking하여 트리의 모든 node를 방문해야 하므로 비효율적이다. 이러한 단점을 보완한 것이 B+Tree이다.
다른 점
- 데이터는 leaf node에만 저장한다. leaf가 아닌 root node와 중간 node들은 자식 node로 향하는 포인터만 갖는다.
- 모든 leaf node들은 linked list를 통해 서로 연결되어 있다.
- 중간 node들의 key를 통해 leaf node를 찾아가므로, node들이 갖는 key는 중복될 수 있다.
장점
- leaf가 아닌 node들에 실제 데이터를 저장하지 않고, key에 따라 자식 node로 향하는 포인터만 가질 수 있으므로, 저장 공간을 절약해 더 많은 포인터를 저장할 수 있다. → 한 node가 가질 수 있는 자식 node의 최대 개수를 늘릴 수 있으므로, 트리의 depth를 낮출 수 있다.
- Full scan시, linked list로 연결된 leaf node들에 대해서만 읽기를 진행하면 되므로 시간이 단축된다.
단점
- 실제 Data까지 접근하기 위해서는 무조건 트리의 맨 아래에 있는 leaf node까지 접근해야 한다.
MySQL InnoDB의 B+Tree Index 구조
MySQL InnoDB에서는 테이블의 인덱스로 B+Tree를 이용한다. 트리의 node로 Page를 이용하며, key의 범위에 따라 자식 node(page)로 향하는 포인터를 가진다(leaf node가 아닌 경우). Leaf node(page)의 경우, 페이지의 앞뒤로 접근할 수 있도록 Doubly Linked List로 연결되어 있는 모습을 볼 수 있다.
B-Tree와 B+Tree의 비교
| B-Tree | B+Tree | |
|---|---|---|
| 데이터 저장 | 모든 node에 저장 | leaf node에만 저장 |
| key의 중복 | 중복 없음 | 중복 존재 가능 |
| Full Scan | 모든 node를 순회하며 탐색 | linked list를 통해 leaf node만 선형 탐색 |
| key를 통한 탐색 | leaf node까지 가지 않아도 되는 경우가 있음 | 무조건 leaf node까지 가야 함 |
| 높이 | 비교적 높음 | 비교적 낮음 |
참고 자료
