节点中的关键字与子树数目相同,比如节点中有 3 个关键字,那么就有 3 棵子树;<br>关键字对应的子树中的节点都大于或等于关键字,子树中包括关键字自身;<br>所有关键字都出现在叶子节点中;<br>所有叶子节点都有指向下一个叶子节点的指针。
与 B 树不同,B+ 树在搜索时不会在非叶子节点命中,一定会查询到叶子节点;另外一个,叶子节点相当于数据存储层,保存关键字对应的数据,而非叶子节点只保存关键字和指向叶节点的指针,不保存关键字对应的数据,所以同样数量关键字的非叶节点,B+ 树比 B 树要小很多。
B+ 树更适合索引系统,MySQL 数据库的索引就提供了 B+ 树实现。原因有三个:<br>(1)由于叶节点之间有指针相连,B+ 树更适合范围检索;<br>(2)由于非页节点只保存关键字和指针,同样大小非叶节点,B+ 树可以容纳更多的关键字,可以降低树高,查询时磁盘读写代价更低;<br>(3)B+ 树的查询效率比较稳定。任何关键字的查找必须走一条从根结点到叶子结点的路,所有关键字查询的路径长度相同,效率相当。<br><br>最后可以简单了解,还有一种 B* 树的变种,在 B+ 树的非叶节点上,也增加了指向同一层下一个非叶节点的指针。<br>