Next: 排序 Up: 面向数据设计 Previous: 层级细节水平和隐式状态 Contents
知道为什么需要查找特定的数据，非常重要。如果没必要，可能就直接省下最大的一环。天真地去查找表中某一行是否存在，会很慢。可以手动添加一些查找助手，如二叉树、哈希表，或者只是在插入表时选择有序插入。如果想做后者，也有可能让其变慢：有序插入通常不是并发的；而且添加额外的辅助工具，通常是一项手动任务。本章中，我们会尝试解决所有这些问题。
长期以来，数据库管理系统种一直都有索引的概念。当 DBMS 注意到特定查询执行了很多次，就会自动添加索引。可以根据这个思路，在游戏中实现即时(just-in-time)索引系统，引入同类的性能优化。
SQL 中，每次要确认一个元素是否存在，或是生成一个子集 (如找到某范围内的所有实体), 就得创建一次查询操作。查询作为实体存在，能帮助建立在 DBMS 中的直觉。
可以把用于创建行、生成表的查询，当作是对象。它能挂起，以备不时之需，并且可以根据其在一段时间内的使用情况，适时变换。开始时只是简单的线性查询请求 (若数据还未被排序)。进程经由内部监测，可以发现它是否经常使用，并且能发现它是是否通常返回简单的可调整的结果集(如有序链表的前 N 项)。超过某些预定义阈值（如：操作次数、生命周期等）之后，如果能让查询对象将自己与其所引用的表挂钩，就会非常有价值。通过钩住插入、修改、删除等操作，查询本身可以更新结果，就不用在每次要访问结果时，重新完整运行。
这种智能对象，是面向数据能从 OOP 那边借鉴的。某些情况下，它能大大节省开支，并且因为是可选的，也可以很安全。
如果建立通用的后端，处理对这些表的查询，能带来多种好处。不仅能预期不再使用的索引被垃圾会收，还能让程序在某种程度上自我记录、归档。如果再研究一下日志，发现有哪些表要建立查询，就可以看到数据热点，找到改进的空间。甚至说，让代码自我记录并决定采取哪些优化步骤，也是可能的。
面向数据查找的第一步，是理解查找条件，并理解其依赖的数据间的不同。面向对象查找的方案，经常问询对象是否满足某些条件。对象被问到时，可能就需要大量代码，间接内存访问，缓存行被填满，但几乎未能充分利用。即使在面向对象代码库之外，仍然有很多无法充分利用内存带宽的情况。代码 ![[*]](crossref.png)
是一个简单的二分查找的例子：在简单的动画容器实现中，查找一个键。这类数据访问模式常见于动画库中，而且在许多人工编写的结构中也很常见，它们的条目都沿着某个维度排序。
![\begin{lstlisting}[caption={基于对象的二分查找}, label={lst:6.1}, capti...
...
l = m;
}
m = (l+h+1) / 2;
}
return keys[m];
}
};
\end{lstlisting}](img24.svg)
了解进程中的生产者和消费者的依赖关系，我们就能快速改进它。代码 即是快速重写后的例子，通过移出到部分数组结构，节约了大量内存请求。数据布局，源自于认识到满足程序所需的数据。
首先，要考虑什么能做输入，然后需要提供什么做输出。当前唯一的输入，是一个浮点数形式的时间值，而这个例子中要返回的唯一数值，是个动画键。要返回的动画键取决于系统内部的数据，而且我们也可以任意重排数据。已知，输入将与键中的 time 做比较，且与键中的其他数据无关。因而可以将其提取到单独的数组中。找到要返回的动画键时，并不是只要访问其中一部分，而是要返回整个键。鉴于此，将动画键数据保持为结构数组是有其意义的，这样在返回最终值时，访问的缓存行就会减少。
![\begin{lstlisting}[caption={基于值的二分查找}, label={lst:6.2}, captionp...
...
l = m;
}
m = (l+h+1) / 2;
}
return keys[m];
}
};
\end{lstlisting}](img25.svg)
这样在大多数硬件上都更快，但是为什么？大多数人的第一反应是，键被从返回的数据附近移开了，并确保在返回前只取一次数据。有时候，比起第一眼，最好想得更远一点。来看一下 AnimKeys 的数据布局。
| t | tx | ty | tz | sx | sy | sz | rs | cacheline | ||||||||
| ri | rj | rk | blackt | blacktx | blackty | blacktz | blacksx | |||||||||
| blacksy | blacksz | blackrs | blackri | blackrj | blackrk | t | tx | cacheline | ||||||||
| ty | tz | sx | sy | sz | rs | ri | rj | |||||||||
| rk | blackt | blacktx | blackty | blacktz | blacksx | blacksy | blacksz | cacheline | ||||||||
| blackrs | blackri | blackrj | blackrk | t | . | . | . |
主要是因为这里的处理都是根据 time 的值来定位键的索引。在提取 time 的代码中，不再通过结构数组中的某个成员来寻找整个结构。在查找阶段，缓存会被大量相关的数据填满，因此这样会更快。原来的布局中，每条缓存行只有一到两个 key.time。更新后，则有 16 次之多。
| t0 | blackt1 | t2 | blackt3 | t4 | blackt5 | t6 | blackt7 | cacheline | ||||||||
| t8 | blackt9 | t10 | blackt11 | t12 | blackt13 | t14 | blackt15 |
有些方法能更好地组织数据，但任何额外优化，都得在复杂度、空间、时间上做取舍。基本的二分查找能很快找到结果，但每一步都会读入新的缓存行。如果知道目标硬件的缓存行大小，就能在加载下一段缓存行之前，检查所有已加载的数值。达成这样的结果，大部分需求的数据都在缓存里，此时唯一要做的就是确保找到正确的结果。在会关注缓存行的引擎里，游戏代码可以调用这些优化过的查找算法，悄然完成工作。值得一提，每次进入更大的数据结构时，都会错失复用成熟代码的机会。
二分查找是最好的查找算法之一，它能用最少的指令寻找关键值。但如果想找到最快的算法，就必须看看究竟什么在花费时间，而通常不是指令。加载一整行缓存信息，并尽可能多地利用它们，会比使用最少指令数更有帮助。试想，一个算法分别用两种不同的数据布局，会不会比算法本身的影响都来得要大？
| times | keys | n | blacks0 | s1 | blacks2 | cacheline | ||||||||||
| s3 | blacks4 | s5 | blacks6 | s7 | blacks8 | s9 | blacks10 | |||||||||
为了对比前面查找动画键的代码，再来看第三种方案：尝试利用结构中剩余的缓存行空间。原有的结构体包含 numKeys，以及 keyTime 和 keys 两个指针，缓存行还有很多剩余。PS3 和 Xbox360 最大开销之一就是缓存行利用率![[*]](footnote.png)
低。现代 CPU 中，情况没那么糟，部分原因是缓存行比较小。但每次请求时，可以免费读取些什么，仍旧值得考虑。本例中，缓存行足以存储额外 11 个浮点值，用来存储类似于跳跃链表(skip-list)的内容。
![\begin{lstlisting}[caption={优化利用缓存行}, label={lst:6.3}, captionpos=...
...i;
}
if(i < 0)
return keys[0];
return keys[i];
}
};
\end{lstlisting}](img26.svg)
既然这些键必然会被加载到内存中，我们就能趁机免费查询一些数据。代码 中，可以看到它使用了线性查找，而非二分查找，但根据测试结果，仍要快于二分查找。在此我们假设，像现代机器上的大多数情况一样，是因为代码所采取的路径更好地利用了资源，而不是因为理论更优，或用了更少指令。
| i5-4430 | @ 3.00GHz | |||
| Average | 13.71ms | [Full anim key - 线性查找] | ||
| Average | 11.13ms | [Full anim key - 二分查找] | ||
| Average | 8.23ms | [Data only key - 线性查找] | ||
| Average | 7.79ms | [Data only key - 二分查找] | ||
| Average | 1.63ms | [Pre-indexed - 二分查找] | ||
| Average | 1.45ms | [Pre-indexed - 线性查找]
|
||
如果查询需求比较简单，如检查某项是否存在，那还有更快的方案。布隆过滤器(bloom filter)的查询时间为常数。尽管它有一定的误识别率，但对于超大集合，可以做些调整，直至达到可接受的正确率。尤其是，如果要检查某行在哪张表中，那布隆过滤器的效果就非常好。它能返回需要的结果，一般只有正确的表，但有时不止一份。Google 的工程师们在 BigTable 技术 [#!google2016!#] 中，用布隆过滤器降低写入前方法(write-ahead approach)的开销，并用它快速确定，数据请求应在最近变化的表中查找，还是应直接进入后备存储。
在关系数据库中，如果索引的存在有利于多个查询，就会在运行时将其添加到表中。对于面向数据方法，总有办法能加快查找速度，但只能通过查看数据。如果数据尚未排序，那就通过索引找到所需的特定项目。如果数据有序，但需求更快的访问速度，那针对缓存行大小优化过的查找树就有所帮助。
大多数数据没法那么简单就优化掉。重要的是，有大量数据时，通常很容易从其中学习到模式。很多时候，我们必须与空间数据打交道，但因为用对象，就很难事后再捆绑有效的空间参考容器(spatial reference container)。运行时，给外部定义的对象类添加空间参考容器几乎是不可能的。
如果数据是像行这样简单的格式，添加空间分区后，就能够生成空间容器、查询系统。它们易于维护，易于优化。由于面向数据变换本身固有的可复用性，我们进而也为上层程序员提供了超高优化的代码。
有时，其实不用真的去查找。如果是为了在某个范围内找到一些东西，如附近的食物、住所、掩体等，就不是查找问题，而是排序问题。在查询的前几次，可能真的会做一次查找以定位结果，但如果执行得够频繁，那为什么不把查询放进运行时更新的排序子集的表格数据中呢？如果需要最近的三个元素，那就保留最近三个的排序列表，当有元素更新、插入、删除时，就能根据信息，更新那三个元素。要对元素分布稀疏的集合做插入或修改，可以先检查该元素是否更近，并在添加新元素时pop出最小值，保证最佳排序。删除或修改时，想要从有序集合中找到一个元素，替代被删除的那个，就得快速检查其余元素，找到新的最佳集合。但如果保留的最佳值多于必要数量呢？估计这种情况永远不会发生。
![\begin{lstlisting}[caption={保存更多信息}, label={lst:6.4}, captionpos=b]
...
...y.findbest();
bestvalue.push( best );
return best;
}
}
\end{lstlisting}](img27.svg)
诀窍就是，在运行时找到方案需求的最佳值。于是，唯一要做的就是运行时检查数据。为此，要么保留日志，要么根据查询优化器的反馈，动态调整大小并测试。
有些表的数值变化非常频繁。为了确保树描述具备高性能，最好不要有大量修改，因为每次修改都可能导致重平衡。当然，如果在某个处理阶段做所有修改，然后再平衡，然后在另一处理阶段做所有读取，那么也仍可以使用树形态。
C++ 标准模板库中的 map 实现，即便一次性提交所有修改，可能也没法很好地帮到编译器。但一个考虑到缓存行的树实现(如 B-树)，可能会有所帮助。B-树的节点更宽，也更浅。由于每个节点容量都更大，插入和删除操作一次发生多个变动的概率也更低。通常，红黑树每隔一次插入或删除，就会触发某种形式的平衡。但大多数 B-树的实现中，可能会有与节点宽度相关的旋转，而节点可以非常宽。如，有些节点有 8 个子节点，并且很常见。
如果某些数据有许多不同查询，最终会有多个不同索引。条目变化的频率应该影响索引数据的存储方式。每次查询都保留一棵树开销可能很高，但许多实现中，反而会比哈希表开销更小。哈希表在有很多修改和查找穿插的情况下，开销更小；而树在数据基本静态时，或着说，至少在多次读取时，以某种形式存在一段时间，这种情况反而更优。
数据为常量时，完美哈希表能胜过树。完美哈希表会用预计算的哈希函数生成索引，除了用于存储常量、指针数组、到原始表的偏移量外，不需要额外空间。如果时间充足，就有可能找到完美哈希，返回实际的索引。虽然通常时间没那么充裕。
例如，要怎样根据某人的名字找到他的位置？通常不会按名字排序玩家，所以要发起一次从名字到玩家的查找。这个数据在游戏中基本不会变，所以最好能找个方法直接访问。单一的查找几乎总是会带出指针链，所以用哈希寻找数组条目或许再合适不过了。假设有个普通哈希表，条目里有目标和其他元素，并且提供方法计算出下一个要要查找的条目。若确定要做一次，且只有一次查找，就可以把哈希桶做得和缓存行一样大。这样就能免去额外的内存开销，何乐而不为。