MySQL的InnoDB引擎設置有索引及數據緩存池，其中用到的LRU算法來維持緩存的命中率
這裡用到了順序表list來作為緩沖池，每個數據節點稱為block
該算法采用“中點插入法”：當插入一個新block時，移除表尾最近最少使用的block，在中點插入新block。
這個中點將鏈表分為兩部分：
1.靠近表頭的一部分，為young區，這裡的block是最近使用的節點
2.靠近表尾的一部分，為old區，這裡的block是最近少使用的
該算法通過鏈表中的block的使用熱度來維持各block的位置，其中old區的block為鏈表滿的時候移除的候選區
具體算法如下：
1.鏈表的3/8被設置為old區
2.中點不是鏈表的中間點，而是old區的表頭節點，即old區與young區的相鄰的那個節點
3.當讀取的數據不在緩沖池裡的時候，讀取到的block需要插入到鏈表中，插入點為中點，但是插入的新節點為old區的節點，如果此時old區滿了得話，移除表尾的block（LRU節點）
4.當讀取old區的block時，該節點將變成“young”節點：此節點移動到young區的表頭（young區的頭部那裡）
5.在數據庫操作中，被訪問的節點將移除到young的表頭，這樣一來，在young區中的未被訪問的節點將逐漸往表尾移動，當移動過中點，將變為old區的節點。而old區的節點若被訪問到將變為young節點移動到表頭，而old區中的為被訪問的節點依舊往表尾移動，當表滿時，表尾那個block將會被淘汰掉
這裡不涉及到具體代碼實現，只是簡單講了下原理，待實現出來後再貼上來
轉載請注明出處：http://www.cnblogs.com/iamsupercp/p/3682659.html 謝謝合作
