【性能优化】3.7 [外存查找] 返回集合的查找
3.7 返回集合的查找
有时需要针对一个查找值可能查找多个目标值，比如通过用户 ID 查找出该用户的交易记录。
在用户 ID 上建立索引可以避免全遍历而提高查找性能，但仍然不够。如果多条目标值在外存数据表中的存储位置不连续，即使用索引能快速找到目标值的位置，实际读取数据时仍然会在硬盘中跳动不同的位置。而且，因为硬盘读取有最小单位，通常这个单位远大于一条记录占用的空间，结果造成大部分读取内容是无效的（如果是列存就更严重）。而且，机械硬盘上过多的跳动也会消耗很多时间，特别是这种查找常常还伴随时并发，会进一步加剧硬盘跳动。
解决的办法是事先把数据按被查找键排序存储，保证同一个查找值对应的目标值在物理上是连续存储的，这样，读取出的数据块几乎全部都是需要的目标值，也不会造成硬盘跳动，性能提升相当明显。
A |
B |
|
1 |
=file("data.ctx").create@r(#ID,…) |
|
2 |
for 10000 |
>A1.append((rand(1000)+1).new(A2:ID,…).cursor())) |
3 |
=file("data.ctx").open() |
|
4 |
=file("data.idx") |
|
5 |
=A5.index(A4;ID) |
|
6 |
=A5.icursor(;ID==3456;A4).fetch() |
|
重新产生一个对 ID 有序的组表，每个 ID 下可能有若干记录。建立索引后，查找方法与之前没有区别，但会获得好得多的性能，特别是在并发时更有优势。使用行存或者带值索引也会比直接使用列存的效果更好。读者可以尝试生成一个乱序的组表来对比性能差异。
再复习一遍：即使对于被查找键有序的数据表，再建立索引仍然是有意义的。索引能够直接定位到目标位置，不像外存的二分法那样会读出相邻的数据来尝试。
这类交易记录数据的产生次序通常是时间，而被查找键通常不是时间。这要把不断产生的（以时间为序的）新数据追加到现有数据表中还能保持按被查找键有序，才能获得高性能的查找效果。这就会用到我们在上一章中讨论过的将数据追加成有序组表的方法。
