索引看这篇就够了

索引是什么

索引是一种可以加快查询的数据结构。例如我们在读书，查新华字典的时候，我们不会一页一页的翻去找到我们要查找的内容。我们是在书的前几页的目录中首先找到我们要查找的内容在书中的第几页，然后直接翻到那一页就找到了我们的目标内容。

数据库中的索引

那么类似上面的例子，在数据库中面对千千万万的磁盘数据，当我们查找的时候也不可能一个一个磁盘块去查找数据，这样的效率是很低的。同样，伟大的前辈们创造了数据库的索引，这样我们在查找数据的时候，先在索引中找到我们的目标在磁盘上的位置，然后去查找，这样极大的节约了查找时间。

索引是怎样的一种数据结构

既然索引是为了提高查询效率，现如今最快的查找算法莫过于时间复杂度为 O(logN)二分查找算法了。二分查找随快，但是要求元素必须是有序的。数据库中的元素是不断的累加的上去的，如果要求有序，则每次插入数据就需要给元素排序。如果索引存储在数组的数据结构上，那么数据的插入和删除将是一个灾难。那么有没有一种数据结构是擅长插入和删除操作的呢？没错，就是链表，但是链表上面是做不了二分查找的（此处不用解释吧？不懂的小伙伴自行 Google）。那么增养才能做到，使用二分查找，又善于增/删操作呢，如此重任非二叉平衡搜索树莫属了。

二叉平衡搜索树

假如我们使用二叉平衡搜索树作为索引的数据结构，搜索一个目标数据的时间复杂度相较于 O(n)的算法，已经提升到了 O(logN)了。但这还不够，因为索引是存储在磁盘上的，I/O 操作是非常耗时间的，一次 I/O 操作的时间 CPU 可以执行几十万次指令了，是否还可以继续减少 I/O 的次数呢？B 树。

B 树

B 树二叉平衡树的变体，它是多路搜索树，通俗来讲就是叉路变多了，由于叉树变多了，则树的层数就会减少，层数减少则意味着 I/O 次数的减少。B 树将数据存储在节点中，搜索时将节点中的数据取出然后在内存中使用二分查找，找到对应的数据是很快的。哪还有没有可能继续减少 I/O 次数呢（树的层次减少一层，即可减少一次 I/O 的次数），减少 I/O，让 CPU 计算来加快整体的速度。B+ 树。

B+ 树

操作系统 I/O 操作的单位为页，根据操作系统的不同，页存储的数据大小不同。如果每个页里面存入更多的数据，意味着 I/O 的次数减少。B+ 树将所有数据元素存储在叶子节点上，则非叶子节点上就可以存储更多的指针数据，这样就可以分出更多的叉路，同时意味着树结构的层数更少，则 I/O 的次数变得更少，整体搜索速度得到了更大的提升。因此，mysql 的 innodb 采用了 B+ 树来作为索引。

覆盖索引

Mysql 的索引采用 B+ 树作为数据结构，数据库中数据全部都存储在了叶子节点上，索引字段的值会存储在树的节点上，因此就会有覆盖索引的说法。假如我们要查找的字段就包含在索引中，则查询的效率会更高，因为它避免了去叶子节点查找的步骤。

索引的最左匹配原则

最左匹配原则说的是搜索的时候，该 SQL 语句是否可以利用到索引来提升效率。假设我们在数据库中建立了联合索引（name，age，addres），那么我们在写 SQL 语句的时候，where 条件中 name，age，address 同时他们所在的表达式不是 全模糊/左模糊查询，则该查询可以使用索引，同时不论他们在 SQL 条件中的顺序，因为数据库会将他们优化成合适的顺序。但是假如你的条件中只有 name 和 addres，那么只有 name 可以使用索引，address 是使用不到的。

通过以上的学习你是否对索引有一定的了解了呢？欢迎留言与我讨论。
欢迎关注我的个人公众号一起学习。