[Algorithm Part 1] 7. B-tree

이번 글에서는, 2-3 트리를 일반화한 B-트리에 대해 살펴볼 것이다.

 

빅 데이터는 메모리 용량으로 부족하기 때문에, 외부 저장소(e.g., 하드 디스크)에 저장한다.

때문에, 빅 데이터의 특정 데이터(=instance)를 사용(read/write)하기 위해서는, 그 데이터가 속해 있는 page를 외부 저장소에서 메모리로 가져와야 한다.

 

여기서 발생하는 대부분의 비용은 해당 page를 메모리로 가져올 때까지 발생하는 page I/O 횟수이다.

B-트리는 page I/O 횟수 획기적으로 줄여준다.

---

Definition of B-Tree

B-tree는 2가지 종류의 노드(=page)를 가지고 있는 트리다.

1. external node(=leaf node): (정렬 순서를 유지한) M-1개의 실제 데이터 key(client key)를 저장할 수 있는 노드
2. internal node(=non-leaf node): 탐색을 위해, M-1개의 key(복사본)-link 쌍을 저장할 수 있는 노드
   • root 노드는 적어도 2 key-link 쌍을 가지고 있어야 한다.
   • 그 외 노드는 M/2 key-link 쌍 이상을 가지고 있어야 한다.

3 쌍까지 가질 수 있는 2-3 트리를 일반화 했다고 보면 쉽다.

Data Structure

각 노드를 크기가 M인 배열로 표현한다.

• internal node: 각 배열 요소마다 key-link 쌍을 저장할 수 있게 만든다.
• external node: 각 배열 요소마다 key만 저장할 수 있게 만든다.

Operations

2-3 트리를 일반화 했기에, 2-3 트리 연산 진행 과정과 매우 흡사하다.

 

1. search

1. root 노드부터 탐색 key를 포함하는 범위 즉, 서브 트리를 찾는다.
2. 탐색 key가 속해 있을 만한 externel node를 찾으면, node에서 탐색 key를 찾는다.
   이때, externel node에서 탐색 key를 찾는 시간은 무시해도 될 정도다.page를 하드 디스크에서 메모리로 가져 오는 시간(page I/O 시간)이 매우 크기 때문이다.

2. insert

1. root 노드부터 삽입 key를 포함하는 범위 즉, 서브 트리를 찾는다.
2. 삽입 key가 속해 있을 만한 externel node를 찾으면, node에 key를 삽입한다.
   만약 node가 full이 될 경우, 2-3 트리에서 처럼 노드를 쪼갠다.

---

Performance

	insert		search
	worst	best	worst	best
b-tree	$\log_{M/2} N$ (I/O)	$\log_{M-1} N$ (I/O)	$\log_{M/2} N$ (I/O)	$\log_{M-1} N$ (I/O)

대부분 4 이하의 I/O 횟수로 탐색 / 삽입 연산이 가능하다.

(if $M=1024, N=62B$, then $\log_{M/2} N \le 4$)