谈谈数据库索引（转载）

今天来聊聊数据库里的索引，你知道的，网上这样的文章一抓一大把的， 基本都是从索引的原理说起，讲到索引的分类， 物理组织和存储形式，如何找到对应的记录，如何构建复杂的索引等等 ，如果我再写一篇这样的就没意思了，而且这些未必真的是大家（尤其是开发同学）关心的。所以我今天打算以一个不同的角度来讲下索引，而且针对B+tree索引，希望大家看了会有所帮助。

对于一个SQL，开发同学最关心的啥？ 我觉得并不是这个SQL在数据库里面是如何执行的，而是这条SQL是否能尽快的返回结果，前面我们在讲连接池的时候提到过，在SQL的生命周期里，每一个环节都有足够的优化空间，但是我们有没有想过，SQL优化的本质是啥？终极目标又是啥？其实优化本质上就是减少SQL对资源的消耗和依赖，正如数据库优化的终极大招是 Do nothing in database一样，SQL优化的终极目的也是Consume no resource。

资源有两个特性：首先资源是有限的，大家都抢着用就会有瓶颈的，所以SQL的瓶颈可能是由资源紧张产生的。其次资源是有代价的，并且代价各异，比如内存的时延100ns， SSD100us，sas盘10ms，网络更高，那么访问cpu l1/l2/l3 cache的代价就比访问内存的要低，访问内存资源的代价要比访问硬盘资源的代价低，所以SQL的瓶颈也可能是访问了代价比较高的资源导致的。现代计算机体系下，机器上粗粒度的资源就那么几种，无非就是CPU，内存，硬盘，和网络。那么我们来看下SQL需要消耗哪些资源：比较、排序、SQL解析、函数或逻辑运算需要用到CPU；缓存数据访问，临时数据存放需要用到内存；冷数据读取，大数据量的排序和关联，数据写入落盘，需要访问硬盘；SQL请求交互，结果集返回需要网络资源。那么我们在数据库里面对SQL的优化思路，自然是减少SQL的解析，减少复杂的运算，减少数据处理的规模，减少对物理IO的依赖，减少服务器和客户端的网络交互， 那么如果解释清楚了索引如何能够帮助做到这几点，这片文章的目的就达到了。

不过先不忙着解释这些，先让大家成为建索引的高手再说，哈哈，你没看错，成为索引高手就这么简单，三招速成，再多我也不会了，练完三招后上面这个问题也自然解释清楚了，好， 让我们拿下面的查询SQL来开始练招吧。

SELECT CNO, FNAME
FROM CUST
WHERE LNAME = :LNAME AND CITY = :CITY
ORDER BY FNAME

第一招就是构建一星索引，根据where后面等值的条件，或者范围的条件来构建索引，即index(LNAME,CITY) 。教科书上一般都说索引是为了能以最快的速度定位到想要的数据，即用空间来换时间，这当然没错，但是你有没有想过，快速定位了你想要的数据后，也就过滤掉了不必要的数据，所以一星索引的核心就是利用索引来尽可能的过滤不必要的数据，减少数据处理的规模，对于RDBMS来说是极为关键的，比如说CUST表有1000000行，CITY的过滤度是10%，LNAME的过滤度是0.1%，那么如果没有索引，你不得不把表里所有的一百万行数据都读出来，做处理，但是如果有了这个一星索引，需要处理的数据被极大的缩小了，只需要根据索引找到符合条件的索引叶子节点的范围，读取0.1%*10%*1000000=100rows就可以了，哪怕我们乐观的假定产生的都是逻辑IO， 而不是物理IO，单次的差别就已经很明显了，更别说是执行频率很高的时候了，我们线上很多烂SQL对DB造成了影响，一看机器逻辑读都好几百万了，基本上就可以定位是SQL索引缺失，或者不合理造成的。当理解了这个时候，你就一定不会产生一个误区，在硬件越好越好，时延越来越低的今天，是不是索引还有存在的必要。

第二招就是构建二星索引， 针对上面的case, 我们构建索引如下index（LNAME,CITY,FNAME）,基本的想法就是利用索引的有序性，把消除ordby或者group by等需要排序的操作，因为大家都知道排序是非常消耗CPU资源的，大量的排序操作会把user cpu搞得很高，即使CPU吃得消，如果数据量比较大，需要排序的数据放不下内存的sort buffer，只能悲剧的和外存换进换出，性能下降的就不是一点两点了，这时候利用索引避免排序的优势就明显的体现出来了。

想必第三招你没学就已经会了，没错，第三招就是构建三星索引，即index（LNAME,CITY,FNAME,CNO)， 跟之前的二星索引的差别在于， 在索引中额外添加了要查询的列CNO，这就是所谓的索引覆盖，即在索引的叶子节点就能够读到查询SQL所需要的所有信息，而不需要回原表去查询了，在目前内存如此充足的情况下，很多时候，除了root节点和branch结构，甚至整个索引都是可以被放入内存的，这样能大概率的避免，至少是减少物理IO。

也许你会说，这招式都是最理想的状态，现实的SQL千变万化，有各种奇葩的条件，有很多动态的SQL，有多表关联的SQL，肯定不能拿上面说的三脚猫的招数硬往上套， 没错，实际情况下确实要考虑这样那样的因素，我们也没办法构建所有的索引都是三星的，我们只能根据实际情况， 构建最佳的索引，而非理想的索引，但是万变不离其宗，理解了这三招的原理，就能够见招拆招了，无招胜有招了。比如各种奇葩的条件，那我们选择那些过滤性最好的， 比如动态的SQL，我们就抓住主干的那些SQL，比如两表关联（MySQL）， 因为那就nest loop一种，那就用小表驱动大表，在关联字段各自尽可能的构建最优索引。

我们前面也提到了，索引其实是一种权衡，是一种拿空间来换时间的艺术，所以极左或者极右都是不恰当的，创建过多的索引所带来的空间损耗 ，和对DML所产生的负担，在某些极端场景下，都不能被忽视， 对于DML性能损耗的优化，除了只创建必要的索引外，有些NOSQL实现了二级索引，但是索引是采用异步方式维护，不在一个事务里，这是通过牺牲强一致性来提高性能， 但是RDBMS还做不到，另外在innodb上，我们会推荐使用业务无关的自增字段来作为主键，提高顺序插入性能的同时，还能避免过多的索引分裂，在现有的MySQL版本中， 索引分裂会锁住整棵树， 代价还是非常大的。对于空间成本上的优化，同样可以有些技巧，还是拿Innodb举例，我们推荐使用数字型主键，而不推荐使用大字段作为主键的重要原因在于，大字段主键会极大的增大二级索引所占用的空间，因为二级索引叶子节点包含指向的主键，另外在Oracle上，我们会定期rebuild index来节省索引所占用的空间。

同时B+tree索引，作为一种面向磁盘&SSD的数据结构，相对来说，查询和写入性能也是相对比较平衡的，读写的时间复杂度都在O(log2n)，写入上因为采用的是update-in-place的方式 ，每次写入的时候需要先通过随机查找来找到要写入的位置，性能会不是那么好，当然你也可以选择类似lsm_tree这样的实现（包括OB自己实现的Btree），通过牺牲一定程度的读性能，来提高写的性能。未来会不会出现一种能更完美的数据结构，能够同时更高效的支持读取和写入，是一件比较值得期待的事情。

说了这么多， 总结一下，我认为那么在不考虑业务层面优化的前提假设下，索引是最有效的药方，其他的优化方式与之相比都只能是看成偏方了，而且B-tree作为普遍采用的数据结构，基本上是通用于多种关系型数据库的，记得我从Oracle转MySQL的时候，索引的运用基本上能平滑过渡，所以希望大家都能了解到这些索引知识， 对平时的工作中写出更好更合理的SQL会很有帮助。