B+树的性质

一棵m阶的B+树满足如下性质:

在B+树中,所有的关键字都存放在叶子节点。而在B树中,所有的节点都存放关键字。在B+树中,非叶子节点的关键字,只充当索引的作用,所以在搜索的时候,一定要搜索到叶子节点,而在B树中,可能无需搜索至叶子节点就找到关键字了。
在B+树中,所有的叶子节点,都通过指针连接起来。
在B+树中,有两个指针:一个指向根节点,一个指向最左面的叶子节点。
下面是一棵3阶B+树的例子:
b_plus_tree.jpg


B+树的深度

对于关键字总数为n的m阶B+树而言:


B+树的插入、搜索、删除

与B树的区别点主要在于:


代码实现

tim-chow的github