【性能优化】3.2 [外存查找] 哈希索引
3.2 哈希索引
使用二分法去查找时，还是需要多次读取原文件才能定位到目标值，而且过程中还有不少读取是多余的。如果我们有办法高效地获得目标值的物理位置，那就可以直接读出目标值。
建立一个被查找键值和目标值物理位置的关联表，用查找值从这个关联表中迅速获得物理位置然后再去读取目标值。这个关联表就是外存索引。
索引中有很多被查找键值，那么相当于针对索引也要执行和原本准备针对数据表一样的查找动作，不同的是，我们可以专门设计索引的结构以方便快速查找。
哈希索引将计算原数据表中被查找键值的哈希值，按哈希值依次将被查找键值及其对应的记录物理位置存储起来，相同哈希值的记录被存储到一起。
通常原数据表很大，索引也会很大而无法存储在内存中，这时还要为索引本身建立一个的小索引。哈希值的范围事先知道，可以确定地分成若干段来存储，比如哈希值在 1-100 的存为一段，101-200 再存一段，保证每一段都足够小而能装入内存。在索引头部保存一个长度固定的小索引，用以记录每一段存储的哈希值范围以及这一段的物理位置和长度。拿到查找值时，计算出其哈希值，先读出这个小索引查找出下一步应该再去哪一段查找。这时候可以使用内存查找技术，通常每段的哈希值为按次序存储的，就可以使用二分法，如果每段存储的哈希值数量固定，还可以用序号定位。然后再读出这一段后在其中查找到相应的目标值物理位置（这也是个内存查找技术）再去原数据表中读出。
总结一下，分三步：一读出头部的小索引，二读出查找值所在的索引段，三用物理位置读出目标值。这样，总共读取三次就可以找到目标值了，使用索引要比二分法有明显的优势。而且那个头部小索引可以读取一次后一直装载在内存后，再次查找时就不用再读了，还能进一步减少读取量。
当数据量非常大的时候，可能这个头部小索引也会大到很难全部装载进内存了，这时候就可能要为这个小索引再建立一级小小索引。也就是说，索引可能会分成多级。我们用加载次序来表示索引的级数，最初装载的最小索引部分称为一级索引，通过一级索引找到合适的二级索引，再找到三级、四级（四级已经足够大了），最后一级就能定位目标值的物理位置。每次查找最多读取的次数就是索引的总级数再加将目标读出那一次，第一级索引还可以常驻内存而不需要反复读入。
哈希索引还有个问题在于可能哈希函数的运气不好，导致某一片哈希值下对应的记录数太多而无法存储在一个索引段之内。这时候就需要再做第二轮哈希，换个哈希函数把这些记录重新分布一下。运气再不好可能还会有第三轮、第四轮、…。结果会导致，哈希索引的级数不是固定的，对某些查找值来讲有可能会有更多级。
整个过程并不太简单，外存任务确实比内存任务要麻烦得多。
SPL 对组表提供了索引功能：
A |
B |
|
1 |
=file("data.ctx").create(ID,…) |
|
2 |
=1000.sort(rand()) |
|
3 |
for A2 |
=10000.sort(rand()) |
4 |
>A1.append(B3.new(A3*10000+~-1:ID,…).cursor())) |
|
5 |
=file("data.ctx").open() |
|
6 |
=file("data.idx") |
|
7 |
=A5.index(A6:1000000;ID) |
|
8 |
=A5.icursor(;ID==123456;A6).fetch() |
|
先生成一个乱序的组表，A1 中 ID 字段前不要加 #。
A7 创建为组表 A5 创建索引，被查找键为 ID，索引文件是 data.idx。创建哈希索引时还需要给出哈希值的范围，这里是 1000000。在 A7 就可以使用相应的索引文件（这里是 A6）进行查找了。
和前面二分法不同，组表的索引查找总是假定返回数据量可能很大，所以用了游标。
理论上，我们也可以针对记录序号和物理位置建立索引，这样就可以逻辑上实现按序号定位的效果。但通过上面的分析会发现，外存查找的时间成本主要是在索引分段及相关多级索引的处理上，即使用序号定位也需要做这些事，而序号定位在内存运算中节省的时间已经感觉不到了，所以对于外存查找不再专门提出序号定位的方法了。
