1. 为什么要使用索引
数据库索引的目的在于提高检索效率，这就好像我们沿着一个树，从树根开始找，沿着主干、树干、到最后的末梢，走了其中的一条路径。这比查询一个链表的结构效率要高得多。
2. B树和B+树
2.1 B树
B树，即多路平衡树，每一个节点存储数据项key/data和指针，在同一个节点中数据是增序的，每个节点最多k个子节点，k的大小取决于磁盘页的大小，所有的叶子节点都在同一层。B树的结构可参考下图：
可以看到每个磁盘块包含数据项和指针，如磁盘块1包含数据项17和35，包含P1、P2、P3等三个指针，P1指向小于17的磁盘块，P2指向17和35之间的磁盘块，P3指向大于35的磁盘块。B树大大降低了二叉树的高度，所以也就极大地提升了搜索性能。
2.2 B+树
从B树图中可以看到每个节点中不仅包含数据项的key值，还有data值（表记录中除了主键的数据）。而存储空间是有限的，如果data值较大时将会导致每个磁盘块能存储的节点数量变小，这样会导致B树的高度变深，会增加查询时的磁盘I/O次数，因此会影响查询性能。而B+树叶子节点只存储数据节点，叶子节点之间通过双向链表链接，非叶子节点只存储指针和键值key。由于非叶子节点不存储data，有更多的空间存放key，所以B+树的出度一般比B树要大，深度就更小，因此以B+树的磁盘检索效率比B树高，B+树的结构示意图如下：
如图所示，如果要查找数据项87，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定87在P2指针，在内存中的查找时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，87在79之后，锁定磁盘块3的P3指针，通过指针加载磁盘块9到内存，发生第三次IO，同时内存中做二分查找到87，结束查询，总计三次IO。真实的情况是，3层的B+树可以存储上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常高。
2.3 为什么要使用B+树
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的时间成本要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中的磁盘I/O操作次数。换句话说，索引的结构要尽量减少查找过程中磁盘的I/O次数。在计算机体系结构中，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。
这样做的理论依据是计算机科学中著名的局部性原理：
当一个数据被用到时，其附近的数据也通常会马上被使用。
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。
页是InnoDB引擎管理数据库的最小磁盘单位，页大小默认是16K。一次至少读取一页的数据到内存，或者刷新一页的数据到磁盘。假设表的主键类型为BIGINT占8个字节，指针类型也一般为8个字节，也就是说一个页中大概存储16KB/(8B+8B)=1K个键值，三层B+树最多可以存储1K * 1K * 1K = 10亿条记录。InnoDB存储引擎将根节点常驻内存，在查找数据时一次页的查找代表一次IO，所以对于10亿内量级的表，通过主键索引查询通常只需要1-3次IO操作即可查找到数据。
3. MySQL索引实现
3.1 MyISAM引擎索引
MyISAM使用B+树作为索引的数据结构，叶子结点的数据域存放的是行记录的地址。如下图所示：
以Col1列作为主键索引的示意图，可以看到，叶子结点的data域存放的是数据记录的地址。如果我们在字段Col2上建一个索引（非主键索引），那么索引的结构如下：
MyISAM首先按照B+树的搜索算法查询索引，如果指定的key存在，则取出data域的值，然后用data域的地址查询数据记录。MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址（指针），因此MyISAM的索引方式也叫做非聚集的，之所以这么称呼是为了与InnoDB的聚集索引区分。这里的聚集是指索引和数据是否在一起。
3.2 InnoDB引擎索引
InnoDB的索引实现方式与MyISAM的区别有两个：
- InnoDB的数据文件本身就是索引文件。叶子结点保存了完整的数据记录，这种索引叫做聚集索引。聚集索引这种实现方式使得按主键搜索十分高效，直接能查出整行数据。由于InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形；
- InnoDB引擎叶子节点的data域存储的是相应记录的值而不是地址；
InnoDB的非主键索引（以其他列作为索引）data域存储相应记录主键的值。换句话说，InnoDB的所有非主键索引都引用主键的值作为data域。如下图所示：
由上可知，使用非主键索引搜索时需要检索两遍索引，首先检索非主键索引获得主键(Primary Key)，然后用主键到主键索引树中检索获得完整记录，这个过程叫做回表查询。
为什么非主键索引结构叶子节点存储的是主键值，而不像主键索引那样直接存储完整的一行数据，这样就能避免二次检索？显然，这样做一方面节省了大量的存储空间，另一方面数据冗余较少，更新数据的效率较高，不用担心数据一致性的问题。
到了这里也很容易明白为什么不建议使用过长的字段作为主键，因为所有的非主键索引都引用主键值，过长的主键值会让非主键索引变得过大。
4. 索引建立原则
- 若使用InnoDB存储引擎，如果没有特殊需要，请永远使用一个与业务无关的自增字段作为主键，而且这个字段长度不宜过大。为什么？InnoDB使用聚集索引，数据记录本身存放在主索引（B+树）的叶子结点上，这就要求同一个叶子结点（大小为一个内存页或磁盘页）的数据记录按主键顺序存放，每当一条新的记录插入时，数据库会根据其主键将其插入适当的节点和位置，如果页面达到装载因子（InnoDB默认为15/16），则开辟一个新的页。如果使用自增主键，那么每次插入新的记录，记录就会顺序插入到当前节点的下一个位置。这样就会形成一个紧凑的索引结构，每次插入不需要移动已有数据，因此插入效率很高；
- 如果使用非自增主键（例如身份证号或学号这种无序字符串），每次插入主键近似随机，每次记录都要插入到现有索引页的中间的某个位置，这时不得不移动元素来完成插入，就增加了很多开销；
- 为经常需要排序、分组和联合操作的字段建立索引；
- 为常作为查询条件的字段建立索引；
- 限制索引的数目，索引不是越多越好，太多的索引会使插入和更新变慢；
- 尽量选择区分度高的列作为索引，区分度的公式是count(distinct column)/count(*)，表示字段不重复的比例，比例越大我们扫描的记录数越少，唯一索引的区分度是1；
- 删除不再使用或很少使用的索引；
- 尽量的扩展索引，而不是新建索引，能使用组合索引就不要新建索引；
- 索引列不能参与计算，比如from_unixtime(create_time) = ’2019-05-21’就不能使用到索引，原因很简单，b+树中存的都是数据表中的字段值，但进行检索时，需要把所有元素都应用函数才能比较，显然成本太大。所以语句应该写成create_time = unix_timestamp(’2019-05-21’)；
5. 最左前缀匹配
InnoDB以index(name,age,phone)三列建立联合索引的时候，是按照从左到右的顺序来建立搜索树的，即相当于创建了name单列索引，(name,age)联合索引，和(name,age,phone)联合索引。比如当用(张三,20,18811721028)这样的数据来检索的时候，B+树会优先比较name来确定下一步的搜索方向，如果name相同再依次比较age和sex，最后得到检索的数据；但当(20,18811721028)这样的没有name列来搜索的时候，B+树就不知道下一步该搜索哪个节点了，必须要先根据name来搜索才能知道下一步去哪里查询。比如当用(张三,18811721028)这样的条件来检索时，B+树可以用name来指定搜索方向，但下一个字段age的缺失，所以只能把名字等于张三的数据都找到，然后再匹配性别是F的数据。这就是MySQL建立联合索引时会遵守的最左前缀匹配原则。
保持最左前缀匹配原则，MySQL会一直向右匹配，直到遇到范围查询(>、<、between、like)就停止匹配，比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的。
6. 参考资料
以上内容就是深入理解数据库索引的全部内容了，谢谢你阅读到了这里！
Author：zhaoyh