数据库索引是日常工作所必需的。如何建立索引以及如何使用索引可以提高数据查询的效率。而且在面试过程中，数据库的索引也是必问的知识点，比如：索引底层结构的选择，为什么选择B+树？不同存储引擎的索引有哪些表现形式？覆盖索引的左前缀匹配原则是什么？看看这些，你能说多少、懂多少？因此，我们需要探究其内在原理。什么是索引？索引的目的是加快数据检索。是一种去中心化存储（索引往往非常大，属于硬盘级别，所以是去中心化存储）的数据结构。原理是以空间换时间。快速检索的本质是数据结构。通过选择不同的数据结构，可以实现对各种数据的快速检索。索引包括散列索引和B+树索引。在选择索引的底层结构时，为什么选择B+树？归根结底，数据库索引的选择底层是为了提高检索效率，所以需要考虑几个问题：磁盘IO排序和预读是否存在算法时间复杂度注：考虑到磁盘IO是一个非常昂贵的手术。电脑操作系统做了一些优化。当一个IO执行时，不仅是当前磁盘地址的数据，还有相邻的数据都会被读入内存缓冲区，因为部分预读的原理告诉我们，当计算机访问某个地址的数据时，与它相邻的数据也将被快速访问。每个IO读取的数据称为一个页面。哈希表（HashTable，哈希表）哈希表是一种根据键（Key）直接访问内存存储位置的数据结构。这通过计算键值函数来加快查找速度，该函数将所需的查询数据映射到表中的某个位置以访问记录。虽然查询时间复杂度为O(1)，但是存在碰撞问题。在最坏的情况下，时间复杂度会急剧增加；而哈希表只适用于精确键（相等）检索，不适合范围检索。范围检索是一次把所有的数据都找出来加载到内存中，效率不高，所以不适合Mysql底层索引的数据结构。为了优化普通二叉搜索树的高效范围查询，且时间复杂度小，引入二叉搜索树二叉搜索树的时间复杂度为O(lgn)。由于数据已经排序，范围查询可以高效Query，但是会出现问题：左右子节点的深度可能相差很大，最极端的情况只有左子树或者右子树。此时查找效率为O(n)，检索性能急剧下降，所以没有适合Mysql底层索引的数据结构。平衡二叉树（AVL树）为了优化二叉树左右子树深度差过大的问题，我们引入了平衡二叉树，即左右子树深度差节点数不超过1。平衡二叉树貌似合适，实现了：范围搜索，数据排序查询性能好O(logn)注：上图中的一个磁盘块表示硬盘上的一个存储位置，但是我们还有一个更重要的因素需要考虑，磁盘IO和预读，而数据库查询数据的瓶颈就在磁盘IO上，当使用平衡二叉树根据索引进行搜索时，每读取一个磁盘就进行一次IO块读取，没有实现计算机的预读能力，导致检索效率下降。得出结论是平衡二叉树作为索引的问题太深了（也就是它只有两条路），深度越大，IO操作越多。它太小了。每次IO只查询一个磁盘块中的少量数据是IO的浪费。操作系统规定一次最小IO是4K，而Mysql的一次IO是16K，但是图中的磁盘块显然达不到4KB+树。为了优化磁盘IO和预读，减少IO操作，路径太少，所以换成多条路径。,那么你会想到使用B-tree和B+树，但是B-tree的每个节点限制最多存储两个key，这样也会造成过于频繁的IO操作，所以优化思路是：读取尽可能多的数据可能在一个磁盘IO中进入内存，那么B+树也应该出现：B+树的一个节点可以存储很多索引，只有B+树的叶子节点存储数据。相邻节点之间存在某种前继后继关系。叶节点按顺序排列。有：B+树对数据库和表的扫描能力更强。B树的数据存储在每个节点中，节点的物理地址是随机的，所以如果扫描表，进行随机IO。B+树的数据是存储在叶子节点中的，一个叶子节点中的数据是连续的，所以如果扫表，就是进行相对顺序的IO。B+树的磁盘读写能力更强，分支节点不保存数据，保存的关键字更多。一个IO可以读取更多关键字。B+树的排序能力更强。B+树的叶子节点中存储的数据就是索引已经排序的体现。索引在不同的存储引擎中是相同的。常见的有：Innodb引擎体现为聚集索引模式（索引和数据存储在同一个文件中）Myisam引擎体现为非聚集索引模式（索引和数据存储在两个文件中）聚集索引模式（InnoDB存储engine）在InnoDB存储引擎中，索引和数据存储在同一个文件中，属于聚簇索引。而且，InnoDB会自动建立主键ID索引树，所以在建表的时候之所以要指定主键。其中，主键索引（聚集索引）的叶子节点记录的是数据，而不是数据的物理地址。辅助索引的叶子节点存储主键key。所以在使用辅助索引查找数据的时候，实际上是对索引进行两次检查（辅助索引和主键索引）：先查询辅助索引树找到主键，然后根据主键索引树中的数据查询主键非聚集索引方式（Myisam存储引擎）在Myisam存储引擎中，索引和数据存储在两个文件中，属于非聚集索引。不管是主键索引还是辅助索引，其叶子节点记录的都是数据的物理地址。MySQL的索引类型MySQL索引可分为：普通索引（index）：加速搜索唯一索引：主键索引：主键：加速搜索+约束（不为空唯一）唯一索引：unique：加速搜索+约束（唯一）联合索引：primarykey(id,name)：联合主键indexunique(id,name)：联合唯一索引index(id,name)：联合普通索引full-textindexfulltext：搜索长文时，最好影响。其中主要了解联合索引、存储结构、查询方式等问题。联合索引联合索引，由多个列组成的索引称为联合索引，单列索引是一种特殊的联合索引。它的存储结构是这样的：对于联合索引，它的存储结构只是比单值索引多了几个列，而复合索引列的数据都记录在索引树上（不同的复合索引，B+树也不同），而存储引擎会先按照第一个索引列进行排序，然后依次对其他等值的列进行排序。注意：第一行叶子节点按顺序排序，第二列将根据第一列排序，第一列等于下一列再排序，以此类推。在联合索引查询方式中，存储引擎首先从根节点开始查找（一般常驻内存），然后依次在其他列中查找，直到找到该索引下的数据元素，即ID值，然后从主键索引树中找到最终数据。以及联合索引的选择原则：最左前缀匹配原则（常用列优先）优先选择分散度高的列，宽度小的列为最左前缀匹配原则最左前缀匹配原则及索引构建方法和联合索引结构的存储是相关的。根据以上的理解和分析，可以得出联合索引只有在从多列索引的第一列开始查找索引时才能生效。例如：假设user表上有一个联合索引(a,b,c)，那么select*fromuserwhereb=1andc=2是不会命中索引的，因为联合索引的存储引擎是排序的第一个字段在前，然后是第二个字段，然后依次排序。分散当索引中某一列的分散度太低时，优化器可能不会直接使用该索引。离散度的计算方法为：离散度=该列唯一数据量/该列覆盖该索引的数据总量。如果一个索引包含（或覆盖）所有需要查询的字段的值，则称为覆盖索引，即只需要扫描索引，不需要回表查询。覆盖索引可以减少数据库IO，变随机IO为顺序IO，提高查询性能。对于InnoDB辅助索引，该行的主键值保存在叶子节点中，所以如果辅助索引（包括联合索引）能够覆盖查询，就可以避免主键索引的二次查询。例如：--创建联合索引createindexname_phone_idxonuser(name,phoneNum);--此时是覆盖索引，原因是根据name查找，命中索引name_phone_idx，--它的关键字是name，phoneNum，里面已经包含了查询List。selectname,phoneNumwherename="ZhangSan";--如果id为主键，此时也称为覆盖索引，原因：辅助索引的叶子节点存放主键selectid,name,phoneNumwherename="张三”；总结MySQL在索引方面需要掌握的知识点非常多。学习了索引的底层存储结构、不同存储引擎中的索引、索引类型的基本原理分析。这样可以为后续的数据库优化提供理论知识支持，对优化方案的理解也会更好。
