This paper examines page replacement policies for B-trees under the assumptions that nonleaf tree nodes occupy a page and that keys are independently and randomly accessed. The latter assumption is a little bothersome for real systems, but that has not held back analysis in the past. With estimates of key access probabilities, it is a simple matter to sum probabilities and compute access probabilities for all pages of memory occupied by the B-tree. The policy, LAP, of replacing pages with the lowest access probabilities is, unsurprisingly, shown to be a better policy than LRU. What did surprise me a little is that the authors showed that LAP is not necessarily the optimal paging policy out of all policies that statically rank pages in a priority order. The authors give another policy LEC (Lowest Expected Cost) that, in some circumstances, achieves a lower expected fault rate. As their simulation shows, however, the difference is negligible. If you are happy with the initial assumptions, the paper has the effect of reinforcing one’s intuition as to how paging is or should be performed. If you are not happy with them, and if, for example, the key accesses are strongly correlated, you would be better off staying with a standard policy like LRU.