在数据库缓冲池（内存池）的实现中，我有一个由内存中的页面组成的缓冲区。
这些页面有不同的大小（都是 512kb 的整数倍）。
假设我的驱逐策略是 LRU（最近最少使用），但我试图驱逐的页面的大小小于我需要替换的大小，如果我也想遵循 LRU，我应该驱逐尽可能多的 LRU 页面以适应我的新页面。
假设我需要n驱逐最近使用的页面。然而，这些页面在缓冲/内存池中不一定是连续的。
我想到的一个简单方法是合并这些n页面，这意味着我需要适当地重新排序缓冲池。
最简单的方法是复制整个缓冲区并覆盖永久缓冲区并适当地更新数据类型。然而，这假设我们有足够的 RAM 来为这个操作复制整个缓冲区。有没有一种聪明的方法，我不必复制整个缓冲区？
谢谢
一旦你必须移动缓冲区，我认为它不会是“高性能”，但是，这个怎么样：
您要驱逐的页面的总大小是k倍页面大小 512 kB，即传入页面的大小。
最坏情况的布局是这样的（四个字符（除了条|）== 512 kB）：
|X1 |1 |2 |X2 |3 |4 |
这两个Xes 是要驱逐的页面。现在的问题是，要使缓冲区连续，您需要移动到X2旁边X1（或相反）。我的方法是将页面X1向右移动（进入X2）到位。我们可以安全地覆盖X2，因为无论如何我们都想驱逐它。
这样，我们只需要更新 3 个页面大小，而不是复制整个缓冲区。
一个更复杂的问题是：
|X1 |1 |2 |X2 |3 |X3 |4 |5 |
人们仍然可以使用上面的朴素算法，但有可能的优化。例如，一个人可以在不接触的情况下安全地1进入，因为它适合那里。也是如此，可以移入.X222X3
所以事实上，你总是可以使用动态数组插入和交换已知的简单移动技术，但检查可能的优化可能是明智之举，在这种情况下，枚举必须由朴素算法移动的页面和首先尝试将它们直接放入待驱逐空间。只有在失败之后（如第一个例子）才应该使用移动。
只有在需要原子性时才需要复制整个缓冲区。在这种情况下，上面的优化方法也将起作用，但是一旦您无法将阻碍您的页面放入要被驱逐的页面中，您就会遇到麻烦。在这种情况下，您必须在逐出算法中递归以找到合适的位置，可能会逐出更多页面。