引用
https://www.jianshu.com/p/8b653423c586
https://mp.weixin.qq.com/s/jRZMMONW3QP43dsDKIV9VQ
小灰真可爱（QWQ）
https://zhuanlan.zhihu.com/p/27700617
https://www.cnblogs.com/nullzx/p/8729425.html
http://data.biancheng.net/view/61.html
https://www.cnblogs.com/jing99/p/11760993.html
https://draveness.me/mysql-innodb/
B(B-)树
在较少比较的前提下，以达到减少磁盘IO的目的。与搜索树相比，B树更矮更胖。
规则
m阶B树表示该树每个节点最多有m个子节点（m>=2）,非叶子节点最少有1个子节点- 所有节点关键字是按递增次序排列，并遵循左小右大原则
- 每个节点最少有
ceil(m/2)-1个关键字(根节点最少1个)，最多有m-1个关键字 - 所有叶子节点均在同一层,叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子
实现
查找
- 找到待查值是否在当前节点中，在则返回，不在则向待查值排序方向继续查找。
插入
- 根据要插入的key的值，找到叶子结点并插入。
- 判断当前结点key的个数是否小于等于
m-1，若满足则结束，否则进行第3步。 - 以结点中间的key为中心分裂成左右两部分，然后将这个中间的key插入到父结点中，这个key的左子树指向分裂后的左半部分，这个key的右子支指向分裂后的右半部分，然后将当前结点指向父结点，继续进行第3步。
删除
- 如果当前需要删除的key位于叶子结点上则直接删除，否则用后继key（右下方子树的第一个）覆盖要删除的key，然后在后继key所在的子支中删除该后继key
- 当被删除关键字所在结点的key个数大于等于
Math.ceil(m/2)-1时，结束删除操作，否则执行第3步。 - 如果兄弟结点key个数大于
Math.ceil(m/2)-1，则父结点中的key下移到该结点，兄弟结点中的一个key上移，删除操作结束。否则，将父结点中的key下移与当前结点及它的兄弟结点中的key合并，形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复上第2步。
- 兄弟节点大于
Math.ceil(m/2)-1情况下（左右任意一个均可）
- 兄弟节点均小于
Math.ceil(m/2)-1情况下
- 父节点在下移后不足
Math.ceil(m/2)-1情况下的情况下
B+树
相比B树更加胖矮，可以存储更多数据。同时更加稳定（B可能在中间查到，B+只在子查到），范围查找更快！
PS:B+树有两种解释，一种为子节点数==关键字数，另一种为子节点数==关键字数+1，其原理均一致，这里采用相等的解释。
规则
- 关键字数和子树相同
- 非叶子节点仅用作索引，它的关键字和子节点有重复元素
- 叶子节点用指针连在一起，从小到大,且关键字数目范围是[ceil(m/2),m]
- 除根以外的非叶子结点，每个结点包含分支数范围[ceil(m/2),m]
实现
查找
- 找到小于某一个作为方向，进行查找
插入
- 根据要插入的key的值，找到叶子结点并插入。
- 判断当前结点key的个数是否小于等于
m，若满足则结束，否则进行第3步。 - 若超过
m,则将其分裂成两个包含floor(m/2)向下取整，另一个ceil(m/2)，将左边移至父节点，再进行判断
- 插入95
删除
- 当删除最大时需要跟新索引，非最大时直接进入下一步
- 删除后当前节点关键字少于
ceil(m/2)时，若其兄弟结点中含有多余的关键字（大于ceil(m/2)），可以从兄弟结点中借关键字完成删除操作。若兄弟没有则于兄弟合并，继续判断父亲节点。
- 删除51 兄弟有 则相借
- 接上图 删除59 兄弟无 则合并
树与索引
为什么InnoDB 选择B+树而Mongodb 选择B树?
- B树的单点搜索效率是O(1)-O(log(n))，B+树为恒定O(log(n))，单搜索B树更有优势
- B+树数据仅存储于叶子节点，由指针依次相连，范围查询效率更高
MySQL中一个表往往有多个索引，且存在不唯一的索引，如何通关树实现？
数据库中的 B+ 树索引可以分为聚集索引（clustered index）和辅助索引（secondary index）
- 聚集索引就是按照表中主键的顺序构建一颗 B+ 树，并在叶节点中存放表中的行记录数据。
- 辅助索引也是通过 B+ 树实现的，但是它的叶节点并不包含行记录的全部数据，仅包含索引中的所有键和一个用于查找对应行记录的『书签』，在 InnoDB 中这个书签就是当前记录的主键。
