数据库索引大家应该不陌生，在日常工作中大家应该会经常接触到。比如某一个 SQL 查询比较 慢，分析完原因之后，你可能就会说“给某个字段加个索引吧”之类的解决方案。但到底什么是索引，索引又是如何工作的呢？

索引的常见模型

索引的出现是为了提高查询效率，但是实现索引的方式却有很多种，所以这里也就引入了索引模 型的概念。比较常见得索引模型有哈希表、有序数组和搜索树等。

哈希表

哈希表这种结构适用于只有等值查询的场景，比如redis以及一些NoSql引擎。

有序数组

而有序数组在等值查询和范围查询场景中的性能就都非常优秀，有序数组索引只适用于静态存储引擎。

二叉搜索树

二叉搜索树是经典数据结构。为了维持 O(log(N)) 的查询复杂度，就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 O(log(N))。

树可以有二叉，也可以有多叉。N 叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中 了。

InnoDB 的索引模型

在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织 表。又因为前面我们提到的，InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中 的。

主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。 非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引。

即主键查询方式，则只需要搜索 ID 这棵 B+ 树；

普通索引查询方式，则需要先搜索 k 索引树， 得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。回到主键索引树搜索的过程称为回表。基于非主键索引的查询需要多扫描一棵索引树。

索引维护

B+ 树为了维护索引有序性，在插入新值的时候需要做必要的维护。

如果插入数据所在的数据页已经满了，根据 B+ 树的算法，这时候需要申请一个新 的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能自然会受影响。除了性能外，页分裂操作还影响数据页的利用率。

有分裂就有合并，当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。

覆盖索引

由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能 优化手段。

最左前缀原则

B+ 树这种索引结构，可以利用索引的“最左前缀”，来定位记录。不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。这个最左 前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。如果通过调整顺序， 可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。

索引下推

索引遍历过程中对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

关注公众号，发送 ztzl 免费下载《中台战略：中台建设与数字商业》。