一、索引的定义
索引是为了加速对表中的数据行进行检索而创建的数据结构。
二、为什么是B+tree？如果换成其他树结构呢？
innodb和MyISAM默认的索引是B+tree索引；而Memmory默认的索引是Hash索引。
2.1、Binary search tree（二叉查找树）
比根结点小的放左边，比它大的放右边。每一个结点都有两个孩子。
缺陷：会出现如果是一个递增的数列要构造二叉查找树。这棵树就会长畸形。如：一直往右边长孩子。（形成了畸形的链表结构）
2.2、Balanced binary search tree（平衡二叉查找树）
弥补了二叉查找树的缺陷，他可以自旋解决这种畸形的情况。
定义：对于每个节点来说，子节点的高度差不能超过1。超过1-->自旋
缺陷：1.搜索效率不足
一般来说，在树结构中待查找的数据所处的深度决定了它搜索时的IO次数。又因为索引太庞大，所以是放在磁盘上的，而磁盘IO耗时。
2.结点数据内容太少
每一个磁盘块保存的关键字的数据量太小了。操作系统和磁盘的交换是以页为单位，大小是4KB或者16KB的。所以这种树并没有利用好操作系统和数据交互的特征，也没有利用好IO的预读能力，因为OS的空间局部性原理，可能一次性读了8KB，24KB。
2.3、Balance tree（多路平衡查找树-----B树）
多路，几路？-----待查找的关键字数值数+1。假设如果有两个关键字的值待查找，就将子节点的引用区间划分成三个。
（假设一次IO是4KB=4096byte，又假如数据结构占用了4+4=8byte空间，那么现在可以分成4096/8=512个可查找的关键字值，也就是513路！！相对于二叉的时候，一层只能放几十个，现在可以放它的513倍个）
平衡定义：所有的子节点都在同一水平线上。--------绝对平衡
节点的分裂和合并。---------不平衡
2.4、加强版多路平衡查找树（B+树）
先说说B+树和B树的区别？
1 B+树节点关键字采用的是闭合区间，B树是开区间。
2 B+树非叶子节点不存储数据相关信息，只保存关键字（主键）和叶子节点的引用。相对于B树节省了节点的空间开销，所以能存储的关键字变多了。
3 B+树的叶子节点保存了数据部分
4 B+树叶子节点是顺序排列的，并且相邻节点具有顺序引用的关系。
那为什么要选用B+树？
但是，B+树也并不是完美的！！
