DBMS에서 사용하는 B+ Tree

B- tree vs B+ tree

<공통점>

1.모든 leaf의 depth 가 같다.

2.각 node에는 k/2 ~ k 개의 item이 들어있어야 한다.

3. search가 비슷하다.

4. add시 overflow가 발생하면 split 한다.

5. delete 시 underflow가 발생하면 redistribution 하거나 merge 한다.

<차이점>

1. B- tree의 각 node에는 key뿐 아니라 data 도 들어갈 수 있다.

    여기서 data 는 disk block으로의 포인터가 될 수도 있다.

    B+ tree의 각 node에는 key 만 들어가야 한다.

    그러므로 B+ tree에서 data는 오직 leaf 에만 존재한다.

2. B+ tree는 B- tree와는 달리 add,delete 가 leaf 에서만 이루어진다.(데이터가 거기만 있으니까)

    B- tree에서는 internal node 삭제시 successor와 교환한 뒤 leaf node에서의 삭제인 경우로 바꾼다.

3. B+ tree는 leaf node 끼리 linked list 로 연결되어 있다.

<상대적 장단점>

1. B+ tree는 internal node에 key만 저장한다. -> high fanout 으로 인해 tree의 depth가 줄어든다.

                                                           -> 그러나, internal node에서 데이터를 바로 찾을수가 없다.(불필요한 lookup이 더 필요할수 있다)

2.B+ tree는 leaf node 끼리 linked list 로 연결되어 있다. -> B- tree와는 달리, B+ tree에서는 range query가 가능하다.

장점이 단점을 충분히 커버하므로 B+ tree는 file system과 DBMS에 널리 사용된다.

 

 

 

원문

http://blog.naver.com/firia2000?Redirect=Log&logNo=10102240596