# Clock page replacement policy vs LRU page replacement policy, is Clock more efficient?

I'm currently learning about database systems and they mention a buffer management system which brings in pages from disk to memory. This buffer manager allows higher layers to operate as if the entire database on disk is actually in memory.

The video I am watching talks about LRU and Clock as the page replacement policies when a page doesn't exist in the buffer pool.

However what I am confused about is that this video mentioned that LRU was log n in efficiency, but Clock is a better algorithm.

Specifically, imagine the buffer pool being a hash table with page id as the key. The value is dependent on if we are doing LRU or Clock.

If LRU was implemented with a heap data structure, maintaining this structure would be O(log n). ie A read of a page is constant to see if it's in the hash table. If it is, the value points to somewhere on the LRU data structure, which needs an update since the 'last used' time has changed. This means every read, updates the LRU so this is O (log n).

For a clock page replacement policy, modifying a page's last used bit to 0 is constant time, because the page id is a key in the hash table and modifying it's value is O(1).

However for a clock replacement policy, finding a page with a last used bit = 0 requires scanning the buffer pool. That is o(n). For LRU, we just grab the root node which is O(1) and delete it which is log(n) and insert a new node which is log(n). So LRU should be O(log n) to replace a page.

So I'm confused why people would use a Clock page replacement policy and believe it is better than a LRU page replacement policy? Did the educational video I watch make an error in stating Clock is more efficient?

Or am I missing something?

• I would just like to comment how idiotic it is to analyze cache replacement algorithms asymptotically. The constant factor is so incredibly important here. – orlp Oct 9 '18 at 16:46
• What are the constant factors I'm missing? – Terence Chow Oct 9 '18 at 18:12
• Compare functions $T(n) = 5000$ and $T(n) = \log_2(n)$. The latter outperforms the former for any realistic $n$ yet the former is "$O(1)$" and thus "better". – orlp Oct 9 '18 at 18:42
• Yes, but I'm talking about accessing a hash value and setting it in my example of O(1). That's just changing a value in memory. I don't see any constants that are make the O(1) vs O(log n) comparison invalid. – Terence Chow Oct 11 '18 at 0:44