想必大家都知道关系型数据库如MySQL通过索引可以提升查询效率，但是这背后的原理到底是什么呢，让我们一起来分析吧~

  1. 如果没有索引，数据库引擎需要通过<mark>全表扫描</mark>来查找数据，这会产生大量的<mark>磁盘IO</mark>。

  2. 关系型数据库使用B+树构建索引来加速加快查询。<mark>B+树</mark>是一种二叉查找树（每个节点的键值必须：比保存在左子树的任何键值都要大，比保存在右子树的任何键值都要小），这样随机查找某个键值时可以通过从<mark>根节点执行二叉查找</mark>来加速查询，查询成本取决于树的层数。

  3. 针对<mark>范围查询和排序的优化</mark>：在每个叶子节点保存其下一个叶子节点的指针，这样当指定范围范围查询时，先从根节点根据范围的左值找到其叶子节点，之后通过向后遍历叶子节点即可找到对应范围右值，这样可以加速范围查询、排序、分组等数据库查询动作。

  4. 针对<mark>磁盘读写速度的优化</mark>：除了叶子节点之外的其他节点只保存键值，这样对磁盘的单次读写可以获取到尽可能多的数据。以MySQL为例，一个1000万行的表对应的B+树按照主键查找理论上只需要3次磁盘IO，这相对于全表扫描带来的磁盘IO是多个量级的性能提升。

  5. MySQL等数据库引擎在实际实现B+树索引的时候，针对磁盘读写做了优化：非叶子节点中只存放key值，叶子节点中除了key值也会存放数据，按照存放数据的不同索引区分为主索引（聚簇索引）和辅助索引：

    a) <mark>主索引</mark>的叶子节点中存放该key值对应的完整记录，使用主索引进行查找时，可以直接输出记录；一个表只能创建一个主索引。

    b) <mark>普通索引</mark>的叶子节点则存放对应主键的值，因此在使用辅助索引进行查找时，需要先查找到主键值，然后再到主索引中进行查找；一个表可以创建多个辅助索引。

  6. 除了B+树，关系型数据库一般也支持哈希索引，<mark>哈希索引能够非常高效地进行随机查找，但是对于范围查询、排序和分组都不支持</mark>。