什么是索引？

索引是对数据库表中一列或者多列的数据进行排序的一种数据结构。 它可以加速数据的检索。索引的作用相当于图书的目录。

InnoDB和MyISAN默认索引为B+树。 Memony就是是哈希表

B树什么？

B的意思是平衡。
B树是一种自平衡树数据结构，它维护有序数据并允许以对数时间进行搜索、顺序访问、插入和删除。
B树是二叉搜索树的一般化，可以有两个以上的子节点。B树非常适合读取和写入相对较大的数据块的存储系统

B树的阶
B树中，一个节点的子节点数目的最大值，即为B树的阶， 如上图为4阶B树。

B树的根节点
如果根节点不是唯一节点，那它至少有两个子节点

B树的内部节点
内部节点是除叶子节点和根节点之外的所有节点

B树的叶子节点
叶子节点没有子节点，也没有指向子节点的指针， 在m阶B树中叶子节点的元素符合（m/2）-1 <= K <=m-1

每个中间节点包含K-1个元素和K个孩子

插入

插入一个元素，先看它是否存在。如果不存在，即在叶子节点处结束，然后在叶子节点中插入该新元素。

1. 若该节点中关键码个数小于 m - 1 , 直接插入
2. 若关键码个数等于 m - 1, 引起节点分裂，以中间关键码为界将节点一分为2，产生一个新节点，并把中间关键码插入到父节点
   重复上述工作，最坏的情况是分裂到根节点，整个B树增加一层
   

查询

比如查找13 ，
第一次磁盘IO， 定位到17 35 ，比17小查询左子树
第二次磁盘IO，定位到8 12， 比12到查询右子树
第三次磁盘IO， 定位到13，15， 找到13

比较的时候是在内存中进行比较的，所有不怕比较的多， 怕树深度大。

删除

较为复杂

B+ 树

B+树是B树的变种，有着更好的查询效率， B+树和B树区别：

每个中间节点包含K个元素和K个孩子， 每个元素不保存数据，只用来索引，所有数据存在叶子节点
所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

B+树查找

B+树的优势在于查找效率，由于B+树中间节点没有卫星数据，所有同样一块区域可以存更多的元素，是的B+树更加矮胖，IO操作更少。
在数据库的聚集索引（Clustered Index）中，叶子节点直接包含卫星数据。在非聚集索中，叶子节点带有指向卫星数据的指针

由于卫星数据的不同，所以B树查询性能不稳定，有时候根节点就拿到了数据，有时候叶子节点才能拿到数据。
而B+树每次必须查询到叶子节点，性能稳定

范围查找B树效率更低， 需要不断的中序遍历，找到上下限， 而B+树（因为叶子节点是顺序链表连起来的）只需要找到范围下限即可。

插入、删除差不多

总结

B+树相比B树的优势：
　　1.单一节点存储更多的元素，使得查询的IO次数更少；
　　2.所有查询都要查找到叶子节点，查询性能稳定；
　　3.所有叶子节点形成有序链表，便于范围查询。