一.索引的数据结构

索引是帮助数据库高效获取数据的一种排好序的数据结构。我们一般常用的数据结构有：
二叉树、红黑树、B-Tree、HashMap
先说下结论，sql>mysql的索引不管存储引擎是innodb还是mylsam使用的都是B+Tree，为何使用B+Tree呢
主要是其它几种数据结构针对数据库这种场景都有一些“硬伤”。
先来看下二叉树的“硬伤”，这里推荐一个数据结构学习的网站，可以很形象的模拟各种常用的数据结构组织过程及查找过程，本文中使用的树的图都是使用该网站生成的。
数据结构学习网站:.
二叉树支持动态的插入和查找，保证操作在O(height)时间，这就是完成了哈希表不便完成的工作，动态性。
但是二叉树有可能出现worst-case，如果输入序列已经排序，则时间复杂度为O(N),出现O(N)的情况就是如下这种情况：

为了解决二叉树出现worst-case的情况，将查找的时间复杂度尽量保证在O(logN)范围内，于是就有了红黑树。
红黑树属于一种平衡二叉树，查找的性能比较高，其基于最长路径长度不会超过最短路近的2倍进行整个树的平衡。
当数据量巨大时，因为每个节点最多只有两个子节点，所以会导致树比较高。

那怎么解决大量数据时，树比较高的问题呢，如果每个节点的子节点可以大于2个呢，这样不就可以解决树的高度问题了，于是B树就应运而生了


使用B-Tree后，由于每个节点可以有多个字节点，则树的高度必然会大幅降低。树的高度降低会带来什么好处呢？
最大的好处就是会降低查找数据时需要的磁盘IO次数，从而提高查找数据的速度。innodb中最小存储单元是页，每页即对应一个节点。页的大小默认为16K。查找某条记录时，会从根节点开始依然往下查找，每定位到一个节点，就会将该节点存储的所有数据都从磁盘加载到内存中去进行比较。而磁盘IO的速度跟内存的读写速度相差几个数量级，所以降低磁盘IO的次数，是可以大幅降低查询数据的耗时。
sql>mysql没有使用B树而是使用B+树作为索引，主要的原因有以下几点：

1. B+树的磁盘读写代价更低,B+树的非叶子节点并没有存放数据，因此其内部节点相对B树更小，这样一个节点就能存放更多的索引，这样每次读取一页数据所包含的需要查找的索引字段也就越多，相对IO读写次数就降低了。

2. B+树的查询效率更加稳定,由于非叶子结点并不保存数据，而只是叶子结点中数据的冗余索引。所以任何数据的查找必须走一条从根结点到叶子结点的路。所有数据查询的路径长度相同，导致每一个数据的查询效率相当。

3. B+树更便于遍历,由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。

4. B+树更适合基于范围的查询,B树在提高了IO性能的同时并没有解决元素遍历效率低下的问题，B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低。

二.Innodb索引的实现

innodb每张表都会对应到磁盘上的两个文件（.frm和.ibd）

frm是表结构文件，ibd 是数据和索引文件。可以看出innodb的数据和索引是在同一个文件。表数据文件本身就是按B+Tree组织的一个索引结构文件。innodb的数据结构主要由两种索引结构组成，聚簇索引(主键索引)和稀疏索引(二级索引)。

聚簇索引-叶节点包含了完整的数据记录。

稀疏索引-叶子节点包含了该二级索引对应的主键id。

三. 阿里索引规约的解读

阿里巴巴开发手册专门用一个小节讲了索引规约，理解了前面讲解的索引结构，这些规约就比较好理解了。我们选几条来看一看。

解读：索引是按照字段从左到右每个字符的ASSIC码的大小排好序的，比如索引Alice和Alina，建索引时只需要取4位，就可以将它们排好序了，而没必要用全部字段建索引。

解读：索引是按照字段从左到右每个字符的ASSIC码的大小排好序的，like %KK和%KK% 都是没法走索引的。联合索引也是按照建立顺序，从左到右以第一个字段开始排序，比如联合索引a_b_c，像where b>? and c>? 这种，b_c是没法走索引的。

解读：普通索引的叶子节点之存放的索引对应的字段信息以及主键id，尽量使查找的内容都在该索引包含的字段内，就可以避免再次回表去聚簇索引里查找了。