从最初的问题出发，mysql是用来存储&&查询数据的，索引是用来加速数据查询过程的。如果让我们设计一个数据存储系统，我们如何去实现？
1--数组 or 链表
最简单的想法是直接用数组存储所需的数据，但是会存在插入新元素会导致大量元素后移的操作，费时费力；并且查找元素，数组和链表都需要粗暴的遍历，不可取；由此可想到二叉搜索树
2--二叉搜索树 BST
二叉搜索树，又叫二叉排序树、二叉查找树，极端情况下会退化为链表、树高度不可控，pass
3--平衡二叉树AVL
AVL是最早发明的自平衡二叉搜索树：
1.本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。通过左旋和右旋实现左右子树深度差不超过1，避免了二叉树的极端情况的出现。
为什么不使用AVL作为索引：浪费空间，具体原因如下：
Innodb存储引擎的存储单位是 页（page），1页的大小是16kb，1页就是树的1个结点，而每查询一次结点就要进行一次IO操作；如果使用平衡二叉树，一个结点存储的信息大小远达不到16kb，太浪费空间；AVL树存在的最大问题就是空间利用不足，浪费了大量空间，数据量大的时候就会成为一颗瘦高的树，树越高，IO次数越多。
4--B树（B-树、多路平衡查找树）
由AVL树的缺点可想到改进方向：树越矮胖越好，这样IO次数就少，但是为什么用B+树而不是用B树？是因为B+树对B树进行了改进：
1）根节点、枝结点不存储数据，只有叶子结点存储数据，这样每个结点可以保存更多的关键字，一次磁盘IO可以加载更多的关键字；
2）扫表能力更强：叶子结点存储了相邻叶子结点的指针形成了链表，叶子结点数据天然有序，直接遍历结点即可获取所有数据，无需像B树一样遍历整棵树；
3）效率稳定，B树每次获取数据的深度不一定，而B+树每次都需要到叶子结点，效率和时间消耗稳定可预估；
