索引的本质是排序

索引是经常用到的技术，但有些程序员对索引的原理了解不深，发现数据查询性能有问题立刻想起建索引，当然经常也没啥效果，反而消耗资源。那么到底什么时候该用索引以及该怎么用？我们来分析索引清理背后的技术原理就知道了。 索引技术的初衷是为了快速从一个大数据表中找出某个字段等于确定值（比如按身份证号找出某个人）的记录。一个 N 行的数据表，遍历查找则需要比较 N 次，而如果数据按该字段值（在索引中称为键值）有序，那么就可以用二分法查找，只要比较 logN 次（以 2 为底），比如 10 亿行数据只要比较 30 次（10 亿约是 2^30），这显然能大大提高性能。有时可能还会有键值有重复的情况（按出生日期找人）或按键值区间的查找需求（按出生日期区间找人），比较次数会比 logN 大一些，但基本仍是这个数量级的。 索引的本质就是排序。

我们一般不会把原始数据表排序，而是用每条记录的键值和这条记录在存储器中的位置合成一个较小的表，也就是索引表。如果还有其它字段也要用于键值查找，则可以再建立更多索引。原始数据只有一份，索引可以有多个，如果每次建索引都直接对把原始数据排序，则会使数据被复制很多遍，占用空间过大。 还有一种衍生出来的 HASH 索引，用来索引的是键值的某种 HASH 值，这样查找时连二分比较也不用了，速度会更快。但这种方法只用来做键值的精确查找，不能用来实现区间查找，因为 HASH 函数一般都不单调，已经失去原来键值的大小信息了。不过这在许多场景下也够用（按身份证号找人）。HASH 索引本质上是键值的 HASH 值来排序。我们下面的讨论还是以普通键值排序索引为例，HASH 索引的情况可以类比。 从原理上看，显然索引不会提高大量数据遍历的运算性能。有些程序员不明就里时为了提高分组汇总运算的性能也建索引，就是滥用了。

理解了这个原理后，我们就能知道什么时候索引会有效。 只针对键值本身提条件的，如：身份证号等于某值的、出生日期在某个区间内的，这些都很有效。 针对键值的函数提条件的，大部分无效，小部分取决于数据库优化。 如：出生日期是星期几的，索引键是出生日期。索引就没法用，因为星期几对索引无序。 再如：年龄在某个区间的，索引键是出生日期。索引不能直接用，但年龄和出生日期之间是个单调函数，如果数据库优化做得好是可能利用的。但也有些数据库不行。 所以，书写查询条件时要尽量写成针对原始索引键值本身，不要使用函数或表达式。

如果我们为多个字段都建立索引，是否基于这些字段的组合条件查找也能变快呢？ 从上面的原理分析后结论比较悲催，多个索引经常只能用一个。 比如在字段 A 和 B 上都建有索引，查询条件是 A=1 AND B=2。索引 A 过滤出来的 A=1 的记录，对 B 并没有序，这时 B=2 的条件就只能硬遍历了；反过来也一样。 还可以把满足 A=1 和 B=2 的记录分别检索出来，再做交集运算，看起来就可以同时利用两个索引。但计算交集也需要比较，也是某种形式的遍历，不一定比计算 B=2 更快，要根据实际情况来决定。 如果建立 A,B 双字段索引，对 A,B 有序当然对 A 也有序，这样 A=1 就可以利用这个索引，同时 A=1 AND B=2 也能用到，这就会让索引的应用范围更广一点。 但是，这种索引对单独的 B=2 却无效，因为对 A,B 有序时对 B 则无序。这是许多程序员容易犯的错误，以为建一个多字段索引就会对这些字段上的条件都有效。 从这个分析看来，建立多字段索引的有效范围会比单字段更广，比如建立一个 A,B,C 多字段索引会对 A,A/B,A/B/C 条件都有效，那么是否应当尽量把索引字段搞得尽量多？从索引原理上似乎是这样，但这样会导致索引表也大一圈，增加 IO 成本，所以也不一定，需要权衡。

既然索引的本质是排序，如果数据在物理存储时就对某个字段有序，那么是不是就不必为这个字段建立索引也可快速查找了。 是的，没问题。 不过关系数据库并没有存储次序这个概念，能不能把数据的物理次序用作索引是个很难说的事情，看运气了。SPL 有存储次序的概念，就可以自动利用数据的物理次序作为索引。数据物理有序的意义远不只是能少建个索引，它对于分组、去重以及连接运算的性能提升都有非常重要的作用，我们以后再讲。