【性能优化】3.3 [外存查找] 排序索引
3.3 排序索引
外存中更常见的是排序索引。
哈希索引只能针对查找值做等值查找，即判断条件是相等，而不能做区间查找，即判断条件是被查找键在一个指定区间。而且，哈希索引在运气不好的时候还可能出现二轮哈希，其性能不够稳定。排序索引就能够解决这些问题。
排序索引的原理，就是在索引中将被查找键值有序存储，然后可以使用二分法找到查找值对应的目标值的物理位置。这种方案即可以做等值查找，也可以做区间查找。
物理实现时，也不能简单地直接针对索引做二分查找，仍然和哈希索引类似，将索引分成若干段，并为这些段建立一个小索引。先读出小索引，用二法找到同查找值对应的索引段，再读出索引段找出目标值的物理位置，小索引也可以常驻内存减少读取理。
同样的，当数据量很大时，索引也会再分级。不过排序索引可以事先确定每个索引段存储的记录数，不会出现哈希索引那种运气不好导致第二轮哈希的现象。如果每级存储 1K 个值，分到四级就可以对应 1K*1K*1K*1K=1T 条记录的庞大规模，已经足够用了，一般三级就够了。
排序索引做等值查找通常比哈希索引会稍慢一点，但差异不算很大，而因为它的适应面更广，所以绝大多数的外存索引都是排序索引，只有个别需要极端性能要求且只需要实现等值查找的场景才会使用哈希索引。本书以后再提到外存索引，如未声明都是指排序索引。
SPL 缺省的索引就是排序索引。
A |
|
1 |
=file("data.ctx").open() |
2 |
=file("data.idx") |
3 |
=A1.index(A2;ID) |
4 |
=A1.icursor(;ID==123456;A2).fetch() |
5 |
=A1.icursor(;ID>=123456 && ID<=654321;A2).fetch() |
index 函数中不指明哈希范围的就认为是建立排序索引，基于排序索引还可以执行区间查找。
为什么我们不把原数据表直接按被查找键排序而要做个排序索引呢？
这主要是空间问题，索引中只有被查找键和物理位置，相当于两个字段的数据表。而原数据表常常几十甚至上百字段，比索引要大得多，如果整个表都排序，要多占一倍的空间。
而且，即使数据有序，针对原数据表执行二分查找仍然没有使用索引的性能好。前面也说过，直接的二分法没有多级索引，也不能精确定位，还会有不少无效的读取动作。简单二分法通常在性能要求不是很高、同时不想维护索引的场景。索引虽然比原数据小，但空间占用仍然可观，而且在数据追加时还要同时更新。
索引的本质是排序，数据库中也是这个原理。所以在数据库中为大数据表建立索引是非常慢的动作，而且有了索引后的表再做增删改也会变慢很多，因为要同时保持一个有序的索引。理解了这个原理后，在数据库工程中就会有意识地建立和避免索引。
有时我们需要用两个字段作为被查找键，理论上这和单个字段并没有区别，只是比对动作复杂了一点。不过，理解索引的本质是排序后，还可以指导这种索引的建立。
比如有两个字段 A 和 B 作为被查找键，那么我们该怎样建立索引呢？针对 A 和 B 分别建立索引，还是要建立 (A,B) 的联合索引？建索引的成本并不低，要尽量少建索引。
对于 A 有序的一般不会对于 B 有序，而对于 (A,B) 有序的，则一定对于 A 有序，不一定对于 B 有序。我们能得到这样一些结论：
1)对 A 和 B 单独建索引，对于 (A,B) 联合查找会有帮助，但只能用到其中一个索引，比如用 A 的索引，在满足 A 相关条件的记录中再遍历 B 的条件，而不能在满足 A 相关条件后再使用 B 的索引。
2)对于 (A,B) 的联合索引，还可以用于针对 A 的查找，但不能用于针对 B 的查找，更不能用于针对 (B,A) 的查找。索引建立是有明确次序的。
如果可以建立两个索引，那应该针对 (A,B) 和(B,A)建立索引，这样针对 A,B,(A,B),(B,A)的查找条件都可以用上了，只建 A 和 B 的索引效果就差得多。
SPL 中实现了这些自动寻找最佳索引的策略，这些道理对于数据库也成立，好的商用数据库都能聪明地找到最该用的索引。
