-
- 说明
- 原理
- 解释
-
附录
- 查询大量特定数据
- 排序大量数据
说明
之前对Postgres/GP的索引测试见GP索引调优测试–基本篇.md和GP索引调优测试–排序篇，此文给出原理解释。
原理
建议先阅读“深入理解计算机系统(原书第2版)的第6章 存储器层次结构”，再了解B树，最后阅读数据库索引原理及优化，可以对索引的原理有很清楚的了解。
这里给出使用索引和不使用索引时，查询时间的复杂度，
| 查询类型 | 无索引复杂度 | 有索引复杂度 |
|---|---|---|
特定数据（=） |
O(n) (注：n次顺序读取) | O(lgn+1) (注：lgn次查找+1次随机读取) |
特定范围(range) |
O(n)(注：n次顺序读取) | O( lgn+m)(注：lgn次查找+m次随机读取，m为range的范围) |
| 排序 | O(nlgn) (注：这里认为排序的复杂度为nlgn) | O(lgn+n)(注：lgn次随机读取找到第一个值，之后往后读取) |
解释
故之前的测试结果可以给出解释，
1. 查找特定数据走索引，而且很快
随机读取虽然花费时间比较长，但次数很少，故走索引
2. 特定范围数据，数据量小时走索引，大时并不走
数据量小时m比较小，故走索引；数据量大时，比如为n，此时lgn+n>n，故不走索引（注意，复杂度中n为常量，m才是变量）！
3. 排序走索引
有索引的复杂度要低一些
附录
查询大量特定数据
实际上，在上述查找特定数据时，也可能是不走索引的。比如，来自高效使用PostgreSQL索引的一个例子，
从表中检索到的行数可以基于特定的常数值的查询检索而变化。（我注：即不同的常量值，会导致不同的结果行数）。因此，例如，查询计划器对于查询select * from foo where bar = 1使用索引可能是正确的，但对于查询select * from foo where bar = 2却可能不使用索引，这发生于对于bar值为2的行有比较多的话。发生这种情况时，顺序扫描实际上是最有可能比索引扫描快得多，因此，查询计划器实际上是判断正确的，这时顺序扫描的性能代价相比索引扫描更低。
即，实际上查询特定值的复杂度分别为O(n)(注：n次顺序读取)，O( lgn+m)(注：lgn次随机读取，m为该值重复的次数)，故当该值重复较多时并不走索引，与范围查询类似。更深入的分析见为什么我在Sql Server上创建的索引用不上？ - 知乎。
更多关于不走索引的情况分析见笔记–索引失效情况分析.md。
排序大量数据
实际上参见笔记–Postgres索引测试–基本篇.md，针对排序，在大量数据下使用索引反而可能变慢，参见11.4. 索引和ORDER BY，如下，
对于一个需要扫描表的大部分的查询， 明确的排序可能要比使用索引快的多，因为它使用顺序存取模式所以需要较少的磁盘I/O。 当只需要获取几行时，索引是更有效的。