4. 自组织表¶
4.1. 介绍¶
虽然对表进行排序最常见的做法是按 键 值进行，但这并不是唯一可行的方案。 另一种组织表以加快查找的方法，是按预期的访问频率对记录排序。 虽然这样做的好处可能不如按键值排序那么大，但按访问频率（至少近似地）进行组织的代价可以低得多， 因此在某些情况下能够加快 顺序查找。
假设对于每个键 \(k_i\)，我们知道键为 \(k_i\) 的记录被请求的概率 \(p_i\)。 再假设表 \(\mathbf{L}\) 经过排序，使被请求最频繁的记录排在首位，其次是第二频繁的记录，依此类推。 对表的查找将从第一个位置开始顺序进行。 经过多次查找之后，一次查找所需的期望比较次数为
换句话说，访问 \(\mathbf{L}[0]\) 中记录的代价为 1（因为只需查看一个键值）， 其发生概率为 \(p_0\)。 访问 \(\mathbf{L}[1]\) 中记录的代价为 2（因为我们必须查看第一、第二条记录的键值）， 概率为 \(p_1\)，依此类推。 对于 \(n\) 条记录，假设所有查找针对的都是实际存在的记录， 那么概率 \(p_0\) 到 \(p_{n-1}\) 之和必须等于 1。
某些概率分布可以很容易地计算出结果。
几何概率分布可能会产生截然不同的结果。
在许多查找应用中，真实的访问模式遵循一条经验法则，即 80/20 法则。 80/20 法则指出，80% 的记录访问针对的是 20% 的记录。 80 和 20 这两个数值只是估计值；每种数据访问模式都有自己特定的数值。 然而，这种性质的行为在实践中出现得惊人地频繁 （这解释了用于加快网页访问而被 Web 浏览器广泛采用的 缓存 技术为何成功，以及利用 缓冲池 来加快访问存储于 较慢内存（如 磁盘驱动器）中的数据的做法）。 当 80/20 法则成立时，与对未排序表进行的标准顺序查找相比， 按访问频率排序的表可以预期显著改善查找性能。
这是一个潜在有用的观察：如果记录按频率排序，那么典型的"现实生活" 记录访问分布只需要我们在顺序查找时平均访问表的 10-15%。 这意味着，如果我们的应用程序使用顺序查找，并希望让它 （以一个常数倍）稍微快一点，我们可以在不对系统进行大规模重写 （比如实现搜索树这样的结构）的情况下做到这点。 但这一切只有在存在一种（至少近似地）按频率对记录排序的简单方法时才成立。
在大多数应用程序中，我们无法事先知道数据记录的访问频率。 更麻烦的是，某些记录可能在短时间内被频繁访问，然后此后很少再被访问。 因此，记录的访问概率可能随时间变化（在大多数数据库系统中，这是可以预期的）。 自组织表 试图同时解决这两个问题。
自组织表根据实际发生的记录访问模式来修改表中记录的顺序。 自组织表使用一种启发式策略来决定如何对表重新排序。 这些启发式策略类似于管理 缓冲池 的规则。 事实上，缓冲池就是一种自组织表。 按预期的访问频率对缓冲池排序是一个好的策略，因为通常我们必须查找缓冲区的内容， 以确定所需信息是否已在主存中。 当按访问频率排序时，位于表末端的缓冲区 将是需要读取新信息页时最适宜复用的那个。
4.1.1. 频度计数¶
管理自组织表有三种传统的启发式策略。
保持表按频率排序最直接的方法是存储每条记录的访问计数，并始终按此顺序维护记录。 这种方法被称为 频度计数，或简称"计数"。 频度计数类似于 最不经常使用 缓冲区替换策略。 每当一条记录被访问时，如果它的访问次数超过了它前面的一条记录， 它就可能向表的前面移动。 因此，频度计数会按迄今实际发生的频率顺序存储记录。 除了需要为访问计数占用空间之外，频度计数对访问频率随时间的变化反应也不够好。 一旦一条记录在频度计数系统下被访问了很大次数， 无论后续还有怎样的访问历史，它都会保持在表的前端附近。
4.2. 移到最前¶
当找到一条记录时，把它移到表的前端，同时把其他所有记录向后推一个位置。 这类似于 最近最少使用 缓冲区替换策略， 被称为 移到最前。 如果记录用链表存储，这种启发式策略很容易实现。 当记录存储在数组中时，把一条记录从数组靠近末端的位置移到前面， 会导致大量记录（轻微地）改变位置。 移到最前的代价是有界的，其含义是：当至少进行 \(n\) 次查找时， 对于 \(n\) 条记录，它至多需要 最优静态排序 所需访问次数的两倍。 换句话说，如果我们事先知道（至少 \(n\) 次）查找的序列， 并按访问频率存储记录以最小化这些访问的总代价，那么这个代价 至少是移到最前启发式策略所需代价的一半。 （这一点可以用 摊还分析 证明。） 最后，移到最前对访问频率的局部变化反应良好， 即如果一条记录在短时间内被频繁访问，那么在那一时期的访问期间它将位于表的前端附近。 当记录按顺序方式处理时，移到最前的表现很差， 尤其是当这种顺序随后被多次重复时。
4.3. 转置¶
把找到的任何一条记录与表中紧跟其前的记录交换位置。 这种启发式策略称为 转置。 转置适合基于链表或数组实现的表。 频繁使用的记录会随着时间的推移移到表的前端。 曾经被频繁访问但已不再使用的记录会慢慢向表的后端漂移。 因此，转置在访问频率变化方面似乎具有良好的性质。 遗憾的是，有些病态的访问序列会使转置表现不佳。 考虑表最后一条记录（记为 \(X\)）被访问的情况。 这条记录与倒数第二条记录（记为 \(Y\)）交换，使 \(Y\) 成为最后一条记录。 如果现在访问 \(Y\)，它会与 \(X\) 交换。 反复交替访问 \(X\) 和 \(Y\) 的序列会不断查找到表的末端， 因为这两条记录都不会向表的前端推进。 然而，这种病态情况在实践中并不常见。 转置的一种变体是按某个固定的步数把被访问的记录向前移动。
4.3.1. 一个例子¶
虽然自组织表的整体表现通常不如搜索树或已排序的表——两者都只需要 \(O(\log n)\) 的查找时间——但在很多情况下，自组织表被证明是一种有价值的工具。 显然，自组织表相对于已排序的表有一个优势：它们不需要排序。 这意味着插入新记录的代价很低，当插入频繁时，这完全可以弥补较高的查找代价。 自组织表比搜索树更容易实现，对于较小的表可能更高效。 它们也不需要额外的空间。 最后，在顺序查找已经"几乎"够快的应用中， 把未排序的表改成自组织表，可能只需增加少量代码的微小代价， 就能让应用提速到足够快。
作为应用自组织表的一个例子，考虑一种压缩和传输消息的算法。 [#]_ 该表通过移到最前规则进行自组织。 传输以单词和数字的形式进行，规则如下：
如果该单词之前出现过，就传输该单词当前在表中的位置。 把该单词移到表的前端。
如果该单词是第一次出现，就传输该单词。 把该单词放到表的前端。
发送方和接收方都按相同的方式（使用移到最前规则）跟踪单词在表中的位置， 因此它们对编码单词重复出现的数字含义有一致的理解。 考虑要传输的下面这条示例消息（为简单起见，忽略字母大小写）。
The car on the left hit the car I left
前三个单词之前没有出现过，所以必须以完整单词发送。 第四个单词是 "the" 的第二次出现，此时它在表中位于第三位。 因此，我们只需传输位置值 "3"。 接下来两个单词尚未出现过，必须以完整单词发送。 第七个单词是 "the" 的第三次出现，巧合的是它再次位于第三位。 第八个单词是 "car" 的第二次出现，它现在位于表的第五位。 "I" 是一个新单词，而最后一个单词 "left" 现在位于第五位。 因此，整次传输会是
The car on 3 left hit 3 5 I 5
这种压缩方法与 Ziv-Lempel 编码在思想上相似，后者是一类常用于文件压缩工具的编码算法。 Ziv-Lempel 编码把字符串的重复出现替换为指向该字符串在文件中首次出现位置的指针。 这些编码存储在一个自组织表中，以加快查找之前出现过的字符串所需的时间。
