我要评论
b+树的特性
#有m个子树的节点包含有m个元素（b树中是k-1个元素），每个非叶子节点不保存数据，只用来索引；
#所有的叶子结点中包含了全部key，及指向含有这些关键字记录的指针，且叶子结点本身依关键字自小而大的顺序链接。 (而b 树的叶子节点并没有包括全部需要查找的信息)；
#所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而b 树的非终节点也包含需要查找的有效信息)；
b+树与b树的主要区别
#b树非叶子节点是保存数据的;而b+树是不保存数据的，只作索引作用，叶子节点才保存数据。
#b树中任何一个key只出现在一个结点中，而b+树可以出现多次。
#查找过程中，b树在找到具体的数值以后就结束，而b+树则需要通过索引找到叶子结点中的数据才结束
#b+树相邻的叶子节点之间是通过链表指针连起来的，b树却不是。
b+树性能优化
#页分裂，如果key进行随机插入，可能需要在已有的节点中插入，
导致元素超过m值，造成页分裂；而顺序插入就可以避免，
因此例如mysql的id推荐是递增的而不是uuid
#页合并，删除key后如果节点的元素数量小于阈值，就需要合并，
否则查找时可能需要两次io,合并后的页可能又需要分裂；由此可以
知晓mysql删除数据为什么只是标记删除而不是物理删除，是为了防止页分裂，
如果需要物理删除就需要执行mysql命令，
optimize table xxx 或 alter table xxx engine=innodb
为什么b+树比b树更适合数据库索引
1、b+树的磁盘io代价更低 - 非叶子节点不存储数据，体积小，单个节点能容纳的key多，一次性读入内存的效率高
b+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对b 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，
那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说io读写次数也就降低了；
2、b+树查询效率更加稳定 - 查找统一要到叶子节点，算法更快
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。
所有关键字查询的路径长度相同，导致每一个数据的查询效率相当；
3、b+树便于范围查询（最重要的原因，范围查找是数据库的常态） - 叶子与叶子之间是从小到大且链表关联的，很容易做范围查询
b树在提高了io性能的同时并没有解决元素遍历的我效率低下的问题，正是为了解决这个问题，b+树应用而生。
b+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而b树不支持这样的操作或者说效率太低；
其他资料
http://www.bjpowernode.com/hot/997.html
https://baijiahao.baidu.com/s?id=1692469218111984631&wfr=spider&for=pc
https://baijiahao.baidu.com/s?id=1663349019029796519&wfr=spider&for=pc
发表评论