B-tree

만약에 data가 외부 disk에 저장되면 어떡하지.. 한번 접근하는 데 엄청 느릴 텐데..
최대한 wide 하면서도 (depth가 적을수록 좋다는 뜻) 한 disk block에 fit 할 수 있어야 함
 
B tree의 조건 : 임의의 k (keys)에 대하여 - floor 한 node 수

• k'개의 key를 갖고 있는 non-leaf node는 k' + 1개의 children이 있다. 
• $T_{0} < key_{0} < T_{1} < key_{1} <  \cdots < key_{k'-1} < T_{k'}$
• node 안에는 적 어 도 $\left \lfloor k/2\right \rfloor \leq k' \leq k$
• 모든 leaf node들이 같은 층에 있어야 함

B tree의 조건 : 임의의 m ( children)에 대하여 - ceiling 한 node 수

• m개의 children을 갖고 있는 non-leaf node는 m-1
• $T_{0} < key_{0} < T_{1} < key_{1} <  \cdots < key_{k'-1} < T_{k'}$
• node 안에는 적 어 도 $ \left \lceil m/2\right \rceil\leq m'\leq m(=k+1)$
• 모든 leaf node들이 같은 층에 있어야 함

그니까 조건 주어진 거에 따라 조금은 적용하는 게 다른데 모양은 똑같다~ 복잡하게 생각하지 마라~
 
Search - BST랑 똑같음, 최악의 경우 $d  = O(log_{m} n)$ 근데 disk access 하는 것보단 빨라서 괜찮다!!
 
https://www.cs.usfca.edu/~galles/visualization/BTree.html

B-Tree Visualization

여기 가면 시뮬레이션 돌릴 수 있다.

직접 해보기~

연습할겸 여러 개 직접 해봤는데

자식 노드가 모두 같은 층이여야 한다는 점과

기본적인 BST 구조를 따른 다는 점,

노드 갯수에 제한이 있다는 점을 잘 생각하면 된다!