索引是关系型数据库中为了加速对表中行数据检索的数据结构。索引是存在硬盘中的，不是内存中，因此索引占的空间比较大。如果没有索引，数据库全表扫描，逐一比对的话，时间复杂度是O(n)，所以要合理创建索引。
哈希索引
底层是数组+链表或红黑树的结构，时间复杂度为O(1)。在进行等值比较时非常高效，哈希取值后不能比大小，所以不支持范围查找。
注：Innodb存储引擎不支持用户级别的哈希索引。
树形索引
底层是二分的递归查找法，左小右大的排列。
二叉树结构大大减小查询范围，根节点是第一个插入的元素，如果是自增的序列，就会变成一个线性的链表结构，相当于遍历一遍了，效率极低，所以被淘汰了。
平衡二叉树是相对平衡的树，解决了线性链表的问题，作为索引，每查询一层树，增加一次io，数据太多，io次数过多，影响磁盘性能，io利用率低（单次io能真正使用到的内容的占比），不能够满足操作系统跟磁盘的交互特性。
多路平衡查找树（B-Tree）一个节点可以有n个子节点，完全平衡的树，左右的叶子节点都在一个水平线上，n个关键字对应n+1个子节点，节点固定在16KB大小，存储int数据时，第一层可以存储1000条数据，第二层1000×1001条，基于MySQL发出的io请求都是4×操作系统页的大小，io次数为3次-4次，io利用率是16kb，很好的满足操作系统跟磁盘的交互特性。
注意：在多变的列上面不要创建索引，会引发树的多次平衡。
在MySQL、Oracle的官方网站中建议用自增序列作为主键，那为什么身份证号码，手机号码不行？采用主键作为索引的话，在树的调整阶段，带来的影响小，只影响最右边的相关元素，树的结构的调整相对小。
MySQL索引机制是B+Tree，为什么不用b-tree？
B+Tree关键字:子节点=1:1，在根节点和子节点没有数据区的内容，只有最末尾的叶子节点有，在最末尾的叶子节点形成了天然的双向链表结构，在排序和范围查找有好处。
采用的数据布局和搜索方式是左闭合的方式，例如
X=1 -> 1 <=X<28 -> P1
X=28 -> 28<=X<66 -> P2
X=66 -> 66<=X -> P3
X=-1，直接跳过判断，不会进入搜索过程MySQL中的B+Tree每一次搜索都会到达叶子节点结束，叶子节点才有数据区，才能返回对应内容，根节点和支节点都没有数据区，单个节点的关键字会更多，io能力强于B-Tree结构。B+Tree有排序，适合范围查找。而且查询稳定，稳定的n次的io操作。基于索引进行数据全量扫描，B+Tree强于B-Tree，只需要扫描叶子节点就可以了，不需要把所有节点全部扫描一遍。
索引与离散度
索引选择离散度高的列，如果选择了重复度高的列，创建索引，比如性别，索引是为了做数据的大范围过滤的，唯一确定性不够，可能一半以上都满足条件，不如直接全表扫描。
离散度超过15%会强制不走索引，进行全表扫描。当离散度超过该值的情况下全表扫描可能反倒比索引扫描更有效。我们所追求的目标就是创建全表扫描所无法比拟的有效索引。
离散性计算公式：count(distinct col) : count(col)
比值越高离散性越好，列的选择性就越好，选择性好的列作为索引更合适，离散性很差的列作为索引可能适得其反。
