关于B树和B+树
小灰算法
B-树
为什么要使用B-树
二叉查找树速度和比较次数都是最小的，但是需要考虑磁盘IO问题。
数据库索引是存在磁盘上的，加载的时候不可能整个索引都加载到内存，只能逐一加载每一个磁盘页（每一个磁盘页对应一个索引树节点）。
首先假设一颗二叉查找树:
其查找次数最大为树的高度，也就是要进行4次磁盘IO。
将“瘦高”的树变得“矮胖”。
B树（就是B-树）主要目的是为了解决磁盘IO次数的。其中每个节点包括k个孩子，k取决于磁盘页大小。
k最大值就是k阶B树（下面这个应该是3阶B树）
其改善的地方，就是每个节点都是一个磁盘页，每次加载会将这一整个节点加载到内存中。在内存中比较的速度比磁盘IO快多了。
B-树插入
B-树一大优势：自平衡
插入过程比较麻烦，涉及到节点分裂。
节点3，5已经是两元素节点，无法再增加。父亲节点 2， 6 也是两元素节点，也无法再增加。根节点9是单元素节点，可以升级为两元素节点。于是拆分节点3，5与节点2，6，让根节点9升级为两元素节点4，9。节点6独立为根节点的第二个孩子。
B-树删除
删除11后，节点12只有一个孩子，不符合B树规范。因此找出12,13,15三个节点的中位数13，取代节点12，而节点12自身下移成为第一个孩子。（这个过程称为左旋）
B+树
性质1：父节点中的元素，出现在了子节点中，而且是其中最大的；
性质2：因为包括父节点元素，所以说叶子节点中，包括所有元素。而且连在一起成了个链表
卫星数据：卫星其实就是索引，一个指针，指向实际地址。下面图里的Data就是卫星数据。
在数据库的聚集索引（Clustered Index）中，叶子节点直接包含数据。MySQL中的InnoDB引擎。
在非聚集索引（NonClustered Index）中，叶子节点带有指向数据的指针。MySQL中MyISAM引擎。
与B-树对比
其查询：
B+树中间节点没有存储卫星数据（全在叶子节点上），所以说可以存储更多索引。IO次数更少
B+树必须查询到叶子节点，而B-树不一定。
B+树查询稳定，B-树则不是。
范围查询
查询分为单元素查询，和范围查询。
单元素查询比较容易理解；
而范围查询是指查询一个范围，比如“3到11”之间的所有数字。
B-树必须要去树的中序遍历；
而B+树在找到3之后，根据叶子节点的链表可以直接查询到。
总结
B树:
- 为了解决磁盘IO问题，使用B树。一个节点就是一个磁盘页。
- B树插入与删除比较麻烦，需要节点分裂与自旋，重要特性自平衡。
- MongoDB和文件系统使用B-树。
B+树：
- B+树只在叶子节点中存入数据，而非叶子节点中存的只是索引。
- 所以说B+树一定要查到叶子节点，稳定查询。而B树则不是。
- 所以说一个非叶子节点存的比B树的更多，更能解决磁盘IO问题。
- B+树子节点中包括父节点的数据，所以说叶子节点包括所有数据。
- 而且叶子节点之间用指针相连，形成了一个链表。做范围查询非常简单。
数据库索引
MySQL中B+树索引与哈希索引。
B+树索引：
- 非聚簇索引：MySQL的MyISAM引擎，B+树节点里面存储的是索引与数据地址。
- 聚簇索引：MySQL的InnoDB引擎
- 主索引：非叶子节点存储主键，叶子节点存储数据；
- 辅助索引：节点中存主键，然后再根据主索引去找。
哈希索引：
- MyISAM不支持
- InnoDB会自动在使用频繁的数据上添加，自动在B+树索引的基础上创建一个哈希索引。
