BTree B+Tree

参考博文

http://blog.csdn.net/v_JULY_v/article/details/6530142

http://blog.csdn.net/hguisu/article/details/7786014

 

 

B-Tree

T度的B树,满足以下条件:

每个节点至多有2T个节点

除根节点外,其他每个分支节点至少有T子树

根节点至少有两颗子树

所有的叶子节点在同一层上

每个节点有j-1个关键字,j个子节点,关键字按顺序排列

 

 

B+Tree

T度的B+树,对比B树满足以下条件:

每个节点有T个关键字,T个子结点

所有的叶子节点中包含全部关键码的信息,叶子节点按关键码顺序连接

每个非终端节点,可以看成索引部分,节点中仅仅包含子树的最大或最小关键码

 

 

B*Tree

T度的B*树,对比B+树满足以下条件:

在每个非叶子节点上,添加指向兄弟节点的指针

每个非叶子节点上,关键字至少为2/3(2T)个(提高了每个节点的使用率)

 

 

 

以下是BTree在插入新数据时的分裂操作:

 

 BTree B+Tree