B-tree Algorithm

http://www.semaphorecorp.com/btp/algo.html
http://www.nist.gov/dads/HTML/btree.html
http://mathworld.wolfram.com/B-Tree.html

B-tree
ordered set의 data을 다루는 효율적인 방법
node : key들과 다른 node를 가리키는 pointer들로 구성
       k개의 key를 가지는 node는 항상 k+1개의 pointer를 가진다
order n : b-tree의 node가 n~2n개의 key를 가졌다는 뜻
(b-tree의 모든 node는 적어도 n개의 key를 가져야한다. 단 root node만은 n개보다 적은 key를 가질 수도 있다.)
이것을 쓰는 이유 : data secondary storage(HDD 등..)에 저장되어 있을 때
Block(Page) size에 맞추어 child node 갯수를 정하는 것이 cache, buffer 등에 의해 efficient하다.

B+tree
http://babbage.clarku.edu/~achou/cs160/B+Trees/B+Trees.htm

B+ tree는 leaf node에만 data page를 두고 intermediate node에는 index page를 둔다.
따라서 increasing order의 data가 들어오면 data page가 split되는 일이 없기 때문에
매우 빠른 성능을 보여준다.
또한 data의 내용에 상관없이 height만큼의 시간에 data를 찾아온다.
(반대로 B tree는 운 좋으면 1, 운이 나쁘면 height만큼의 시간이 걸린다.)
height = maximum depth

B*tree
http://www.nist.gov/dads/HTML/bstartree.html
B tree의 child가 항상 2/3 정도 차도록 하는 variation.