B树与B+树
目录
前言
关于索引的基本概念可参考这篇博客https://blog.csdn.net/Delicious_Life/article/details/105466368
我们知道MySQL的索引结构使用了B+树，想必读者很想知道为什么百度B+树会搜出来个B树，B树和B+树到底有什么异同？要清楚这些内容，首先我们要了解平衡二叉树
平衡二叉树
程序运行时需要从本地磁盘加载到内存中。每次从磁盘加载到内存都可以看做是一次I/O操作，而这种I/O操作是很耗费时间和性能的。因此MySQL在设计索引时考量的重点是哪种数据结构查找快并且I/O读写次数尽可能少。
答案是树，一个典型的查找树就是平衡二叉树！
平衡二叉树有两个特点：首先必须是“二叉的排序树”；其次每个节点的左子树和右子树高度差最多为1
这种数据结构相比扫描所有数据，平均效率提高了1/2。
B树
上面使用的二叉平衡树的确大大减少了查找次数，但生活中“秒”级别的查找是不够的，让用户等20-30s很可能用户会“裂开”。要想提高检索的速度不光要“缩小查找的范围”，还要“减少I/O读写”。
B树这个多叉查找树出现了！多叉也叫多“阶”，指的是一个树能拥有的最大节点树。
B树有如下特性
1.根节点至少有2个叶子节点
2.每个节点可以包含多个元素，根节点最多可以有“阶数-1”个元素
3..其他节点最少有“阶数/2(向上取整)再减去1”个元素，最多有“阶树/2(向上取整)”个元素
B+树
先来说说B树怎么解决了二叉平衡树的问题。二叉就表示最多只能把I/O读写次数减半，既然二叉解决不了问题，多叉、每个叶子节点可以存多个数据不就好了？这样是不是让I/O读写次数在减半的基础上又减少了呢？
但当数据量非常大的时候，B树的性能还可以提的更高，因此B+树出现了，B+树也正是MySQL所使用的索引结构
B+树有如下特性
1.B+树的所有非叶子节点只存索引
2.B+树的叶子节点包含所有的索引值，并且指向数据
3.B+树的所有叶子节点相连
总结：可以看到，在数据量小的时候，B+树的I/O次数并不一定比B树少。但是由于B+树把所有数据都放到了一排并增加了指针，实现了顺序查找，因此效率比B树更高。
MySQL中B+树的应用