B-tree, B+tree

 B-tree와 각 노드에 데이터가 저장이 되지만 B+tree의 경우엔 인덱스노드와 리프노드가 분리되어서 존재한다. 그리고, 리프노드는 서로 연결되어 있어서 임의접근과 순차접근모드 성능이 우수하다.

공통점

• 모든 leaf의 depth가 같다
• 각 node에는 k/2 ~ k 개의 item이 들어있어야 한다.
• search가 비슷하다.
• add시 overflow가 발생하면 split 한다
• delete 시 underflow가 발생하면 redistribution하거나 merge 한다.

차이점

• B-tree의 각 노드에서는 key 뿐만 아니라 data도 들어갈 수 있다. 여기서 data는 disk block으로의 포인터가 될 수 있다.
• B+tree는 각 node에서는 key만 들어가야 한다. 그러므로 B+tree에서는 data는 오직 leaf에만 존재한다.
• B+tree는 B-tree와는 달리 add, delete가 leaf에서만 이루어진다.
• B+ tree는 leaf node 끼리 linked list로 연결되어 있다.

B+tree의 장점

• 블럭사이즈(노드사이즈) 를 더 많이 이용할수잇다 ( 키값에 대한 harddisk 엑세스 주소가 없기 때문에 )
• leaf node 끼리 linked list로 연결되어있어서 시퀀셜한 레인지 탐색에 매우 유리하다 

B + Tree 의 단점

• B Tree의 경우 best case에는 루트에서 끝날수 있지만, B+ Tree의 경우 무조껀 leaf노드까지 가야한다.

출처: https://wangin9.tistory.com/entry/B-tree-B-tree [잉구블로그]