内容简介：作者 | 杨碧佳后端攻城狮，
作者 | 杨碧佳
后端攻城狮， 关注算法和中间件，喜欢探索各种技术。
引言：
我们常常会在工作中用到索引，因为我们觉得在大量的数据下，索引会让数据库查询变得更快，但是我们往往不知道，我们的索引还可以进行进一步的优化，让查询速度变得更快。本文会从一些基础理论讲起，提供一种近乎程式化建立索引的方法。
一、 索引相关定义
物理结构
表和索引都被存储在页中，页的大小一般为 4KB 或者 8KB。
当表和索引被加载或重组时，每个页会留出一定比例的空闲空间，以满足向其添加新的表行或索引行的需求。DBMS 的缓冲池和 I/O 活动都是基于 页 的。
每个 DBMS 都会根据对象类型（表或索引）及页的大小拥有多个缓冲池。每一个缓冲池都足够大，可能存放成千上万的页。缓冲池管理器将尽力确保经常使用的数据被保存在池中，可以避免一些不必要的磁盘 I/O。
这一策略的有效性对于 SQL 语句的性能表现至关重要。
谓词
简单谓词和复杂谓词
WHERE 字句中的每个条件称为一个谓词。
过滤因子
描述了谓词的选择性，即表中满足 谓词条件的记录行数 所占的 比例 。
多个匹配谓词组合成的 组合谓词的过滤因子 （由单个谓词的过滤因子乘积得到）越小越好，可以减少索引结果集的行数，增加查询效率。最差的过滤因子代表了索引查询响应的最长时间，我们一般使用最差的过滤因子来衡量组合谓词的可行性。
过滤因子（FF）= 结果集的数量 / 表行的数量 平均过滤因子 = 1 / 不同列值的数量
索引片及匹配列
第一个索引列定义一个 索引片 ，如果 WHERE 字句中有第二个列，而这个列也在索引上，从而使得这两个列能够一同定义一个更窄的 索引片 ，这两个列叫做 匹配列 ，定义的索引片叫窄索引。
这样不仅显著减少了索引的处理量，更是减少了对标进行同步读的次数。
索引过滤及过滤列
并不是所有的索引列都可参与索引片的定义。
所有的匹配列参与匹配过程 —— 定义索引片。
过滤列参与了索引片的过滤过程，无法参与匹配过程，只能使索引片更厚，因为范围谓词定义的索引片中有很多无用数据，加长了索引扫描时间。
如何判断一个谓词能否参与匹配和过滤呢？
-
范围谓词后面的列都是非匹配列，如果非匹配列足够简单则为**过滤列**
-
WHERE 子句中从左至右有一个足够简单的谓词与之对应，该列则称为**匹配列**
二、 三星索引
三星索引是对于一个查询语句可能最好的索引。通过三星索引，一次查询通常只需一次随机读（从磁盘读取到缓冲池）及一次窄索引的扫描。
SELECT CNO, FNAME
FROM CUST
WHERE LNAME BETWEEN :LNAME1 AND :LNAME2
AND
CITY = :CITY
ORDER BY FNAME
星级评定
-
索引中包含 WHERE 子句中所用到的所有列，查询相关的索引行是相邻的，标记上第一颗星。
这 最小化了必须扫描的索引片的宽度 。索引过滤可以确保回表访问只发生在所有查询条件都满足的时候。
构造 一星 索引满足条件：取出所有等值谓词的列（WHERE COL = …）作为索引最开头的列（任意顺序），我们将会有一个较窄的索引片，后面如果跟上范围谓词，将会使索引片更窄，范围谓词和等值谓词间就不能有其他索引列。
(CITY, LNAME, FNAME, …)
- 索引行的顺序与查询语句一致，标记上第二颗星。
这排除了 排序 操作。
构造 二星 索引满足条件：将 ORDER BY 的列放入索引中（不改变顺序，除去第一颗星加入的索引列）,这些列放在等值谓词前后都可以（因为这些列的索引可以使结果集以其顺序排列，而不需要额外排序），等值谓词值只有一个，也不会影响排序结果；但一定要放在范围谓词之前，范围谓词按顺序扫描后就变成了范围谓词的顺序，ORDER BY后的列就要进行排序操作。
(CITY, FNAME, LNAME, …)
-
索引行包含了查询语句中的所有列，标记上第三颗星。
这样列值都在索引中，不需要访问表，同步读也不会出现问题。
构造 三星 索引满足条件：将查询语句中剩余的列加到索引中去，列在索引中添加的顺序对查询语句的性能没有影响，但是将易变的列放在最后能够降低更新的成本。
(CITY, FNAME, LNAME, CNO)
可以看出，我们的理想索引一定能有第三颗星，但只能有第一颗或者第二颗星。因为第一颗星（等值谓词+范围谓词+其他索引列）和第二颗星的索引排列方式冲突（等值谓词+orderby列+范围谓词和其他索引列 or orderby列+等值谓词+范围谓词和其他索引列），所以只能选择一个。
设计最佳索引
Method A
1. 取出等值谓词作为起始列，任意顺序
2. 将选择性最好的范围谓词作为下一个列，只考虑不过分复杂的范围谓词
3. 以正确顺序添加 ORDER BY 列，有 DESC 则加上，忽略 1 和 2 步中已经添加的列
4. 以任意顺序将 SELECT 语句中其余的列添加至索引中，不易变的列放在前面
eg.
(CITY, LNAME, FNAME, CNO)
Method B
-
取出等值谓词作为起始列，任意顺序
-
以正确顺序添加 ORDER BY 列，有 DESC 则加上，忽略 1 步中已经添加的列
-
以任意顺序将 SELECT 语句中其余的列添加至索引中，不易变的列放在前面
eg.
(CITY, FNAME, LNAME, CNO)
-
Method A : 如果一个程序取出结果集的所有行，那么 A 可能和 B 一样快，甚至更快。
增加了排序操作，主要看数据排序时间的占 CPU 开销多少。数据量大的时候先减少索引片的厚度，再进行排序，后续的操作会在更小的数据量下进行，时间开销自然变小。
-
Method B : 如果一个程序只需获取能够填充满一个屏幕的数据量，比如只取查询语句结果数据的前 20 条数据，那么B可能会比A快很多。
访问过程中没有排序的话，数据库管理系统只要一次一次地读取数据行就行了。
三、 合适设计理想索引
并不是所有的查询语句都需要设计理想的最佳索引。
根据上面说的，为每个查询设计最佳索引的过程是机械式的，只要给出以下内容就可以自动完成整个过程：
-
查询语句
-
数据库统计信息（行数，页数，列值分布等等）
-
对于每一个简单谓词或组合谓词最差情况下的过滤因子
-
已经存在的索引（只是避免生成重复索引）
多余的索引
我们为查询语句设计了一个最佳索引后，去看一下已经存在的索引是很有必要的，我们不可能会完全按照机械式的方式去创建索引。有可能某一个已经存在的索引几乎和理想索引差不多好用，特别是打算在这个已有索引的最后添加一些列的情况下。
当分析一个已经存在的索引对一个新的查询有多大用处，是否真的需要新建理想索引时，可以从这三种多余索引来看，考虑一种新的折中的索引方式：
-
完全多余的索引
一个查询包含 WHERE A = :A AND B = :B，另一个查询包含 WHERE B = :B AND A = :A ，那么生成 (A, B) 和 (B, A) 两个索引，如果没有其他查询语句包含A列或B列上的范围谓词的话，那么这两个索引其中一个就是完全多余的。甚至我们能够去质问业务为什么要设计这样的SQL。
-
近乎多余的索引
假设已经存在索引 (CITY, LNAME, FNAME, CNO) ，如果有一个新的查询语句包含现在的 4 个索引列，后面还多跟了 10 个其他的列，那么在创建了新的索引后，原来的索引应该被删除。
例如，由于使用 14 个列的索引，从中取出 4 个列的数据，CPU时间增长不多，由于顺序读的处理过程主要也是受CPU时间的限制，在性能上不会有很大的影响。
-
可能多余的索引
一个新的查询语句的设计理想索引是 (A, B, C, D, E, F)，而表上已存在的索引是 (A, B, F, C)，一般会在已经存在的索引后加上新增的两列D和E，成为 (A, B, F, C, D, E)。
理想索引可能有两方面优势：使查询拥有更多匹配列和避免排序。但这两个优势都受需要在索引片上扫描的行数的影响，往往新的索引是不需要的，在现有索引后加上新的列就足够了。
建新索引的代价
如果一个表上有 100 个不同的查询，且为每一个索引都设计了最佳索引的话，那么即使没有重复索引，该表上最终也可能有非常多的索引。这样一来表的插入，更新和删除操作就会变得很慢。我们一般从三个方面来讨论，建立一个新的索引要付出的代价。
1. 响应时间
当我们向表中添加一行数据，它必须在每一个索引上都添加相应的行，在一个索引上添加一行耗时 10ms （从磁盘读取一个叶子页），在 10 个索引上每个索引添加 20 行就耗时 1.8s （主键索引维护在同一个索引页）。
所以从响应时间的角度来看，在一个拥有许多索引的大表上进行事务操作，可能是无法忍受的。
2. 磁盘负载
由于数据库的异步写不会影响到事务响应时间，但是这些写会增加磁盘负载。在缓冲区中被修改过的页是会迟早被写到磁盘上去的，当一张表插入或更新频率较高，缓冲区空闲空间变少或脏页过多，会使得从缓冲区写回磁盘的操作也会变频繁，这时带来的磁盘压力也会变大。而且当索引较多时，向表中插入或更新多行数据也会同时更新多个索引页上的行，磁盘繁忙时间会很久。
从磁盘负载的角度来看，一个插入频度较低的表，能够容忍在表上建许多索引，索引数量取决于插入事务对响应时间的要求。如果磁盘负载是问题，较明显的解决办法是 尝试合并索引 。显然，一个有 10 个列的索引比两个各有 6 个列的索引所引起的磁盘负载要小。
3. 磁盘空间
如果一张表中有 1000 万行以上的数据，多个索引的磁盘空间成本可能会成为一个问题。即使我们不考虑磁盘空间的成本问题，随着索引变大，缓冲池或磁盘缓存也应随之增大，否则存在磁盘上会使非叶子页的 I/O 量会增加，所以非叶子页的内存开销也不少。
结语：
虽然三星索引可以让我们建立一个确定的索引组织方式，但我们并不能完全依赖它，这只是一个方法论，对我们建立索引的实践起到指导作用。就比如可能会因为实际应用环境的数据的特殊性，而产生一种并非三星索引的特殊的索引排序方式，它会有更高的性能，所以我们在建立索引的过程中，对索引产生的性能优化进行一个大概的预估也是重要的一步。
全文完
以下文章您可能也会感兴趣：
我们正在招聘 Java 工程师，欢迎有兴趣的同学投递简历到 rd-hr@xingren.com 。
杏仁技术站
长按左侧二维码关注我们，这里有一群热血青年期待着与您相会。
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Designing Data-Intensive Applications
Martin Kleppmann / O'Reilly Media / 2017-4-2 / USD 44.99
Data is at the center of many challenges in system design today. Difficult issues need to be figured out, such as scalability, consistency, reliability, efficiency, and maintainability. In addition, w......一起来看看 《Designing Data-Intensive Applications》 这本书的介绍吧!
