We introduce a new approach to database disk buffering, called the LFU-K method. The LFU-K page replacement algorithm is an improvement of the Least Frequently Used (LFU) algorithm. A probability-theoretical model for a formal description of the LFU-K algorithm is proposed. Using this model, we obtain some estimates for the LFU-K parameters. An implementation of LFU-2 policy (called LFU-2m algorithm) is discussed. As we demonstrate with trace-driven simulation experiments, the LFU-2m algorithm performs better than the conventional buffering algorithm for the shared-nothing database system workloads.

• PostScript (in Russian) (1.51MB)
• PDF (in Russian) (1.27MB)



• PostScript. zip (in Russian) (345йB)
• PDF. zip (in Russian) (299йB)