前言
B+树，是数据库索引的一个数据类型。B+树，是从最早的平衡二叉树演化而来。先了解一下二叉查找树、平衡二叉树、和B树。
二叉查找树
左子树的键值小于根的键值，右子树的键值大于根的键值。
二叉查找树可以任意地构造,以下这种也是二叉查找树，但是其查询效率太低
平衡二叉树
平衡二叉树（AVL树）在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为1。
当失去平衡时，有四种姿态：
- “左左”。插入或删除一个节点后，根节点的左孩子（Left Child）的左孩子（Left Child）还有非空节点，导致根节点的左子树高度比右子树高度高2，AVL树失去平衡。
- 将根节点的左孩子作为新根节点。
- 将新根节点的右孩子作为原根节点的左孩子。
- 将原根节点作为新根节点的右孩子。
- “右右”。插入或删除一个节点后，根节点的右孩子（Right Child）的右孩子（Right Child）还有非空节点，导致根节点的右子树高度比左子树高度高2，AVL树失去平衡。
- 将根节点的右孩子作为新根节点。
- 将新根节点的左孩子作为原根节点的右孩子。
- 将原根节点作为新根节点的左孩子。
- “左右”。插入或删除一个节点后，根节点的左孩子（Left Child）的右孩子（Right Child）还有非空节点，导致根节点的左子树高度比右子树高度高2，AVL树失去平衡。
- 围绕根节点的左孩子进行RR旋转。
- 围绕根节点进行LL旋转。
- “右左”。插入或删除一个节点后，根节点的右孩子（Right Child）的左孩子（Left Child）还有非空节点，导致根节点的右子树高度比左子树高度高2，AVL树失去平衡。
- 围绕根节点的右孩子进行LL旋转。
- 围绕根节点进行RR旋转。
B Tree
满足的条件
- 树中每个结点至多有m个孩子；
- 除根结点和叶子结点外，其它每个结点至少有m/2个孩子；
- 若根结点不是叶子结点，则至少有2个孩子；
- 所有叶子结点(失败节点)都出现在同一层，叶子结点不包含任何关键字信息；
- 所有非终端结点中包含下列信息数据 ( n, A0 , K1 , A1 , K2 , A2 , … , Kn , An )，其中： Ki (i=1,…,n)为关键字，且Ki < Ki+1 , Ai (i=0,…,n)为指向子树根结点的指针, n为关键字的个数
- 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
特征
- 关键字集合分布在整颗树中；
- 任何一个关键字出现且只出现在一个结点中；
- 搜索有可能在非叶子结点结束；
- 其搜索性能等价于在关键字全集内做一次二分查找；
- 自动层次控制；
B+Tree
满足条件
- 树中每个非叶结点最多有 m 棵子树；
- 根结点 (非叶结点) 至少有 2 棵子树。除根结点外, 其它的非叶结点至少有 ém/2ù 棵子树；有 n 棵子树的非叶结点有 n-1 个关键码。
- 所有叶结点都处于同一层次上，包含了全部关键码及指向相应数据对象存放地址的指针，且叶结点本身按关键码从小到大顺序链接；
- 每个叶结点中的子树棵数 n 可以多于 m，可以少于 m，视关键码字节数及对象地址指针字节数而定。
- 若设结点可容纳最大关键码数为 m1，则指向对象的地址指针也有 m1 个。
- 结点中的子树棵数 n 应满足 n 属于[m1/2, m1]
- 若根结点同时又是叶结点，则结点格式同叶结点。
- 所有的非叶结点可以看成是索引部分，结点中关键码 Ki 与指向子树的指针 Pi 构成对子树 (即下一层索引块) 的索引项 ( Ki, Pi )，Ki 是子树中最小的关键码。
- 特别地，子树指针 P0 所指子树上所有关键码均小于 K1。结点格式同B树。
- 叶结点中存放的是对实际数据对象的索引。
- 在B+树中有两个头指针：一个指向B+树的根结点，一个指向关键码最小的叶结点。
特性
- 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
- 不可能在非叶子结点命中；
- 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
- 更适合文件索引系统
保持树平衡主要是为了提高查询性能，但为了维护树的平衡，成本也是巨大的，当有数据插入或删除时，需采用拆分节点、左旋、右旋等方法。B+树因为其高扇出性，所以具有高平衡性，通常其高度都在2~3层，查询时可以有效减少IO次数。B+树索引可以分为聚集索引(clustered index)和非聚集索引（即辅助索引，secondary index）。
- 聚集索引：InnoDB表时索引组织表，即表中数据按主键B+树存放，叶子节点直接存放数据，每张表只能有一个聚集索引。
-
辅助索引：辅助索引（也称非聚集索引）是指叶节点不包含行的全部数据，叶节点除了包含键值之外，还包含一个书签连接，通过该书签再去找相应的行数据。
B-Tree、B+-Tree、Skip-List, 都在用了二分查找的思想
参考：
http://www.cburch.com/cs/340/reading/btree/index.html
https://www.cnblogs.com/wade-luffy/p/6292784.html
http://blog.codinglabs.org/articles/theory-of-mysql-index.html
https://www.cnblogs.com/vianzhang/p/7922426.html
https://www.cnblogs.com/gym333/p/6877023.html
https://www.cs.helsinki.fi/u/mluukkai/tirak2010/B-tree.pdf
http://itindex.net/detail/44489-mysql-%E7%B4%A2%E5%BC%95
