公众号merlinsea
索引的目的
提⾼查询效率，可以类⽐字典，如果要查“mysql”这个单词，我们肯定需要定位到m字⺟，然后从下往下找到y字⺟，再找到剩下的sql 索引设计的核心目的是将原本随机乱序的数据按照一定顺序组织起来，这样在检索到一个值的时候可以快速判断是否需要继续检索。
常见的索引设计方案
1、数组索引：数组索引可以知道查询的时间复杂度是O(n),如果数据量特别大的情况下是不适合的。
2、二叉查找树索引：1、二叉查找树索引的时间复杂度是O(log2n) 2、二叉查找树每个节点只能存一个数据，因此如果数据量足都大的话二叉查找树的层数也会比较高 3、如果需要检索一个范围的话，比如查找[5,12]范围的数据需要递归回溯，查询比较麻烦。
3、hash索引：hash索引本质上是不连续的，即如果是模糊查询或者范围查询的话效率会比较低，但等值查询效率接近常数级别。
4、B树索引：B树本质上就是一个多叉查找树，所有的节点都存放数据 优点：相比于二叉查找树，B树的高度比二叉树要低 缺点：如果是范围查询，B树也需要回溯查询。
5、B+树索引：
B+树在B树上做的改进：1、所有的非叶子节点不再存数据data，非叶子节点只存key值，只有叶子节点才存data 2、所有的叶子节点都增加了指向下一个叶子节点的指针
优点：1、对于范围查询不需要递归回溯进行查找，直接找到第一个节点之后顺序遍历即可。2、非叶子节点不存data的优势是可以将非叶子节点的部分加载进内存，查询更快 3、B+树是mysql索引采用的底层数据结构。
