(Algorithm) B tree 설명 및 pseudo-code

B-Tree는 self-balancing 탐색 트리로. 거의 모든 데이터가 메모리상에 존재한다고 보면된다.
그러나 데이터량이 커지면 이 모든 것을 메인 메모리에 보관할 수 없다.
만약 key의 숫자가 커질 수록, 데이터들은 디스크에서 정보를 가져올 수 밖에 없다.
디스크 액세스 타임의 비용은 메인메모리 액세스 타임보다 훨씬 비용이 크다.

B-Tree의 핵심은 디스크 액세스타임을 감소 시키는 것이 목적이다.
B-Tree의 높이 h는 디스크 접근의 횟수와 비례한다 즉, 이것에 따라 성능이 결정된다.

B-Tree의 PseudoCode는 다음과 같다.

1. B트리의 검색 (B-Tree-Search)
2. 빈 트리 생성 (B-Tree-Create)
3. B트리에 삽입 (B-Tree-Insert)
4. B트리 분할 (B-Tree-Split)

1. B트리의 검색 (B-Tree-Search)

B-Tree-Search (x, k)  // x is node, k is value what we find.

i = 1

while i<= x.n && k > x.key(i)

 i= i + 1

if i <= x.n && k == x.key(i)

 return (x, i) // x is node , i is index number

else if x. leaf

 return nil

else DISK-READ(x)

 return B-Tree-Search(x, k)

2. 빈 트리 생성 (B-Tree-Create)

B-Tree-Create (T)

x = new Node()

x.leaf = true

x.n = 0 (X노드에 있는 값의 갯수 0)

Disk-Write(x)

T.Root = x

3. B트리에 삽입 (B-Tree-Insert)

O(h)번의 디스크 접근과 , O(tlogN)의 CPU시간이 걸린다.

B-Tree-Insert (T, k)

r = T.root

if r.n == 2t -1 

   s = new Node()

   T.root = s

   s.leaf = false

   s.n = 0

   s.c1 = r // 새로 생긴것을 루트로 만듬

   B-Tree-Split (s, 1)

   B-Tree-Insert-NonFull (s, k)

else B-Tree-Insert-NonFull(r, k)

4. B트리 분할 (B-Tree-Split)

B-Tree-Split-Child(x, i)