B+树

B+树

flyfish 2015-7-21

引用自严蔚敏《数据结构》（C语言版）

一棵阶的B+树和m阶的B树的差异在于：

1.有n棵子树的结点中含有n个关键字。
(B树是n棵子树有n-1个关键字)

2.所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。
(B树的叶子结点没有包含全部关键字的信息)

3.所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。
（B树的非终端结点不仅包含其子树根结点中最大（或最小）关键字的信息，还可以包含其他关键字的信息）

通常在B+树上有两个头指针,一个指向根结点,一个指向关键字最小的叶子结点
B+树可进行两种查找运算：一种是从最小关键字起进行顺序查找；另一种是从根结点开始进行随机查找。

Degree为3的B+树示意图