就像有缓存无关和缓存优化算法一样，有没有寻求最优算法？

Question

缓存(不经意|最佳|感知)算法通常会在其模型中考虑寻道时间。如果没有，有没有考虑到寻道时间的模型的例子，并且在这个模型中有算法分析。

Answer 1

是的，我曾亲自编写过seek敏感算法。文件系统当然使用seek敏感数据结构(类似于算法)。

例如，NTFS (和许多其他文件系统)以B-tree格式存储数据，以最大限度地减少寻道和优化顺序读取。

不幸的是，在2014年，当固态硬盘和其他技术即将完全取代旋转介质时，您就会问这个问题。SSD确实遭受了一些寻道损失，但与旋转硬盘相比，它们每秒可以处理数万个寻道，而旋转硬盘可能每秒甚至不能处理100个寻道。这使得seeks的问题比过去几年要小得多。

一个类似且更相关的问题是CPU上的缓存线一致性。

例如，堆数据结构远比树更适合缓存。性能敏感的代码将选择使用堆而不是树，这是一个实际的选择。

至少在过去的十年中，这个缓存问题一直是一个压倒一切的性能问题。